Matematické Fórum

↑ Tomas5:

Ahoj, řekl bych, že ne, bude jich o dost víc.
Jaks to počítal?

↑ Tomas5:

Aha, tak to ses asi nedopočítal.

Možná sis neuvědomil, že na nějaké množině vrcholů může těch kružnic být více, než jenom jedna.

Zkus spočítat, kolik je v onom grafu kružnic nějaké konkrétní délky (třeba délky 6 - to znamená takových kružnic, že všechny vrcholy na ní leží)

↑ Tomas5:

Ne, to znamená, že sestává z 6 vrcholů (a tedy i 6 hran)

↑ Tomas5:

To právě že ne. ; ))

Uvaž například kružnice 1-2-3-4-5-6(-1) a 1-3-2-5-4-6(-1). To jsou zřejmě dvě různé grafové kružnice, obsažené v grafu K6.

↑ Tomas5:
ještě zkus přidat,... schválně je zkus vypsat. Až se dostaneš k číslu 60, tak budeš mít ty délky 6;)

↑ Tomas5:

to tipuješ? : ))

tak rozeberme trochu ten případ "všech šest vrcholů leží na kružnici".
Príma věc s úplnými grafy je, že každé dva vrcholy jsou spojeny hranou. Takže kolika různými způsoby můžu vybrat souseda vrcholu 1 v kružnici?

↑ Tomas5:

Ano. předpokládejme, že jsme nějakého takového souseda s zvolili. Kolika způsoby můžeme nyní vybrat druhého souseda vrcholu s v kružnici?

↑ Tomas5:

Ano. Takže to jsme napočítali kolik "orientovaných kružnic"?

↑ Tomas5:

Jo. resp. dělí.

Jde o to, že takto jsme započítali něco vícekrát, konkréntně dvakrát:

takto jsme třeba "zkonstrovali" kružnici
1-2-3-4-5-6(-1)
ale taky kružnici
1-6-5-4-3-2(-1)

což je stejná kružnice.

Lze nahlédnout, že takto jsme shodné kružnice zahrnovali "právě po párech" - více než dvakrát jsme žádnou kružnici započítat nemohli a méněkrát také ne.

Tedy toto číslo je třeba vydělit dvěma.

Nyní to zkus stejně pro kružnice délky pět, čtyři, tři. Nezapomeň, že množinu 5 (resp. 4,3) vrcholů, na nichž budeme počítat kružnice, lze také zvolit více způsoby.

Až to dopočteš, tak ti ještě nabídnu jeden způsob jak se dopočítat k výsledku. V podstatě je myšlenka stejná jako ti nabízí ↑ OiBobik:, jen početně jednodušší. Bez pochopení toho co bylo napsáno by ti ale moc nepomoh.

↑ Tomas5:

Délky 5 souhlasím. // EDIT: taky špatně - viz ↑ Wotton:

Délky 4 ne - jak přesně jsi k tomu došel?
Délky 3 taky ne - zde zřejmě stačí pouze spočítat, kolika způsoby lze vybrat onu trojici vrcholů, na nichž budu kružnici uvažovat - na těch třech vybraných je už zřejmě kružnice určena jednoznačně.

↑ OiBobik:
Nesouhlasím ani s délkou 5. Podle mně by jich mělo být 72.