Matematické Fórum

Saturday · 10. 11. 2007 15:12

Zadání: Kolik různých kružnic existuje na množině N vrcholů.

Moje úvahy:

- Řekl bych, že počtem různých grafů se rozumí takový počet grafů, kdy započítáváme množinu všech izoformních grafů k danému grafu za jeden graf.

- Pokud je délka kružnice N, pak by odpověďí mělo být, že existuje pouze jedna. Pokud však by se měly počítat i kružnice kratší délky, tak by to teoreticky mohlo být nějak takhle:

$\sum_{i=1}^n {n \choose i} = 2^n - 1$

Mohl by mi to prosím někdo zkontrolovat?

Lishaak · 10. 11. 2007 16:24

No me to prijde hlavne dost blbe zadane. Na mnozine N vrcholu samozrejme existuje jen jedna kruznice.

Pokud pocitame i kruznice kratsi delky, pak by se asi zadani dalo preformulovat tak, ze hledame, kolik ruznych mnozin kruznic delky < N existuje na N vrcholech. To uz je daleko slozitejsi otazka. Ten tvuj vzorec funguje pouze pokud pocitam jednoprvkove mnoziny kruznic, a ani tahdy vlastne ne, protoze zacinas sumu od jednicky, kdezto nejmensi kruznice ma tri vrcholy (tedy pokud neuvazujeme multigrafy).

Kdybys napsal, k jakemu probiranemu tematu se tenhle priklad vztahuje, mozna bychom mohli rozlustit, jak bylo zadani mineno...

Saturday · 10. 11. 2007 16:41

Je to cviceni z diskretni matematiky, teorie grafu - vic to specifikovat nejde

Pocital jsem jednoprvkove mnoziny kruznic, protoze jsme k tomu meli zatim jen jednu prednasku a nevim, jestli nekde necihaji nejaka omezeni.. Zatim jsme si stihli zadefinovat pojmy jako kruznice, biparitni graf a par dalsich..

pak to staci jen upravit na: $\sum_{i=3}^n {n \choose i} = 2^n - 1 - n - \frac{n(n-1)}{2}$

sonja · 13. 06. 2008 16:43

Saturday: téma přesunuto sem: http://forum.matweb.cz/viewtopic.php?id=3477

Kondr · 13. 06. 2008 18:33

Jsou dvě otázky, které nejsou ze zadání jasné:
a) počítají se izomorfní grafy pouze jednou?
b) musí kružnice obsahovat všech n vrcholů?

Podle dvojice odpovědí na tyto otázky se liší výsledky:
ne, ano - (n-1)! kružnic
ne, ne - $\sum_{i=3}^n{n\choose i}(i-1)!$
ano, ano - jedna kružnice
ano, ne - n-2 kružnic

Zřejmě je možno vymyslet další otázky a prostor možných řešení tak rozšířit. Osobně si myslím, že pokud by se izomorfní kružnice počítaly jen jednou, bylo by to v zadání explicitně napsáno. Jestli ale "na n vrcholech" znamená, že kružnice musí procházet všemi, nebo ne, to asi záleží na názoru.

Saturday · 13. 06. 2008 18:35

Dekuju, po zkouskach si to projdu, tenhle semestr DM nemam :-)

Matematické Fórum

#1 10. 11. 2007 15:12

Teorie grafů - kružnice

#2 10. 11. 2007 16:24

Re: Teorie grafů - kružnice

#3 10. 11. 2007 16:41

Re: Teorie grafů - kružnice

#4 13. 06. 2008 16:43

Re: Teorie grafů - kružnice

#5 13. 06. 2008 18:33

Re: Teorie grafů - kružnice

#6 13. 06. 2008 18:35

Re: Teorie grafů - kružnice

Zápatí