Proszę o rozwiązanie zadania i poprowadzenie mnie przez rozumowanie.
Ile jest wszystkich grafów zwykłych o wierzchołkach 1,2, .. n?
Thx
Ile jest grafów.
-
miodzio1988
Ile jest grafów.
zakładam, że wierzchołki nie są numerowane
dla 1 :
mamy sam wierzchołek
dla 2:
możemy miec niespojny graf z dwoma wierzchołkami lub drogę prostą\(\displaystyle{ K_{2}}\), czyli dwa są takie grafy
dla 3:
możemy miec niespojny graf z trzema wierzchołkami lub drogę prostą z jednym oddzielnym wierzchołkiem lub \(\displaystyle{ K_{3}}\)
dla 4:
możemy miec niespojny graf z czterema wierzchołkami lub drogę prostą z dwoma oddzielnym wierzchołkami itd
Czujesz już konstrukcję?
btw musisz trochę sprecyzowac zadanie.-- 28 czerwca 2009, 16:49 --zakładam, że wierzchołki nie są numerowane
dla 1 :
mamy sam wierzchołek
dla 2:
możemy miec niespojny graf z dwoma wierzchołkami lub drogę prostą\(\displaystyle{ K_{2}}\), czyli dwa są takie grafy
dla 3:
możemy miec niespojny graf z trzema wierzchołkami lub drogę prostą z jednym oddzielnym wierzchołkiem lub \(\displaystyle{ K_{3}}\)
dla 4:
możemy miec niespojny graf z czterema wierzchołkami lub drogę prostą z dwoma oddzielnym wierzchołkami itd
Czujesz już konstrukcję?
btw musisz trochę sprecyzowac zadanie.
dla 1 :
mamy sam wierzchołek
dla 2:
możemy miec niespojny graf z dwoma wierzchołkami lub drogę prostą\(\displaystyle{ K_{2}}\), czyli dwa są takie grafy
dla 3:
możemy miec niespojny graf z trzema wierzchołkami lub drogę prostą z jednym oddzielnym wierzchołkiem lub \(\displaystyle{ K_{3}}\)
dla 4:
możemy miec niespojny graf z czterema wierzchołkami lub drogę prostą z dwoma oddzielnym wierzchołkami itd
Czujesz już konstrukcję?
btw musisz trochę sprecyzowac zadanie.-- 28 czerwca 2009, 16:49 --zakładam, że wierzchołki nie są numerowane
dla 1 :
mamy sam wierzchołek
dla 2:
możemy miec niespojny graf z dwoma wierzchołkami lub drogę prostą\(\displaystyle{ K_{2}}\), czyli dwa są takie grafy
dla 3:
możemy miec niespojny graf z trzema wierzchołkami lub drogę prostą z jednym oddzielnym wierzchołkiem lub \(\displaystyle{ K_{3}}\)
dla 4:
możemy miec niespojny graf z czterema wierzchołkami lub drogę prostą z dwoma oddzielnym wierzchołkami itd
Czujesz już konstrukcję?
btw musisz trochę sprecyzowac zadanie.
Ile jest grafów.
Dzięki za odpowiedź, ale tak się zastanawiam, zdaje mi się, że autorowi zadania chodziło właśnie o jeden graf numerowany, dlatego napisał, że ma wierzchołki: 1,2,..n (czyli podał ich numerację). To bardzo upraszcza zadanie: ile jest grafów zwykłych o n wierzchołkach (numerowanych). Rozwiązaniem jest zdaje się:
\(\displaystyle{ {n \choose 2}}\) - liczba możliwych krawędzi
\(\displaystyle{ 2^{n \choose 2}}\) - tyle jest podzbiorów zbioru \(\displaystyle{ {n \choose 2}-elementowego}\), czyli szukanych grafów.
Dzięki bardzo za pomoc
\(\displaystyle{ {n \choose 2}}\) - liczba możliwych krawędzi
\(\displaystyle{ 2^{n \choose 2}}\) - tyle jest podzbiorów zbioru \(\displaystyle{ {n \choose 2}-elementowego}\), czyli szukanych grafów.
Dzięki bardzo za pomoc