Matematické Fórum

Yuyik · 08. 02. 2011 15:15

Potřebovala bych pomoct se dvěma věcmi z teorie grafů - konkrétně týkajících se úplného grafu a zadání grafu maticí:

1. Kolik různých kružnic délky 6 je v úplném grafu na 10 uzlech?
2. V úplném grafu na 10 uzlech mám 3 uzly označené A, B a C. Kolik existuje různých cest z A do C přes B takových, že délka cesty z A do B je 3 a délka cesty z B do C je 2?

Je to ze zápočtového testu, takže si přesně nepamatuju zadání. Určitě se to bude řešit kombinatoricky, ale to není moje silná stránka.
Pak jsem měla druhý problém, bohužel si to přesně nepamatuju.

Byl zadán graf maticí jedniček a nul. Jednička znamenala, že graf obsahuje hranu ij a 0 že neobsahuje hranu ij. Vím že jsme z toho měli získat skóre grafu a pak zjistit, jestli existuje. Já bohužel ztroskotala hned na té matici.

Profesor nám jaksi nevyložil zadání grafu pomocí matice, takže se tak trochu ztrácím.
Díky za pomoc

claudia

(Nejsem si jista správností.)

Ad 1) V úplném grafu libovolná šestice vrcholů tvoří kružnici délky šest. Je tam tedy tolik kružnic, jako je tam šestic vrcholů. A to je $\binom{10}{6}$ .

Ad 2) Z B do C vede cesta přes jediný vrchol. Je (10-3)=7 možností, jak jej vybrat. Pak z A do B vede cesta přes dva vrcholy a je 6 možností, jak vybrat první, a 5 možností, jak vybrat druhý. Dohromady tedy 7*6*5.

Ad skore) (Předpokládám neorientovaný graf.) Každý řádek (nebo sloupec) matice reprezentuje právě jeden vrchol. Z toho vede tolik hran, kolik je na tom řádku jedniček. Takže pro každý řádek sečteč počet jedniček a máš stupně vrcholů, které tvoří skore. Těžko si ale dokáži představit, že by graf zadaný maticí neexistoval. Jedině by matice nebyla symetrická podle hlavní diagonály. Pak by neplatilo ani to, co píši výše.

Yuyik · 08. 02. 2011 16:06

Díky moc, pokusím se ještě podívat na netu po nějakých řešených příkladech a snad to na tom třetím pokusu zvládnu :-)

Matematické Fórum

#1 08. 02. 2011 15:15

kružnice a cesty v úplném grafu, graf zadán maticí

#2 08. 02. 2011 15:29 — Editoval claudia (08. 02. 2011 15:37)

Re: kružnice a cesty v úplném grafu, graf zadán maticí

#3 08. 02. 2011 16:06

Re: kružnice a cesty v úplném grafu, graf zadán maticí

Zápatí