25.1.06

1. a)pocet prostych zobrazeni
   b)pocet podgrafu uplneho bipartitniho grafu se stejnym poctem vrcholu
   c)zda muze mit strom a 2-souvisly graf stejny skore
   2)veta o 5 barvach - dukaz
   3)pocet neizomorfnich grafu na 8 vrcholech ktery maj skore slozeny z 0,2,7
   4)pro ktery souvisly grafy plati:
   u,v,w libovolne ruzne vrcholy G pak d(u,v)<d(u,w)+d(w,v)
   d(x,y) je vzdalenost vrcholu x od y

Ahoj. Neviete niekto ako mala byt ta trojka a stvorka? Teda v tej trojke aspon kolko ich bolo,ak sa to tu uz neda nakreslit.. Dik!

sorry, az teraz som si vsimol,ze v tej trojke ani nebolo treba to kreslit.. :roll:

k trojce:
Prázdný graf, graf s 8 dvojkama a úplný na 8 vrcholech, to jsou 3 a každý je složen jen ze stejných číslic. A pak musíš rozmyslet kombinace. A protože k 7 už nic nepřihodíš, protože je úplný, zbývají ti kombinace 0 a 2 na 8 vrcholech. Buď nějak dopočítat nebo rozmyslet. Budou to kružnice a pak vždycky izolované vrcholy + třeba další kružnice (dva ctverecky nebo dva trojuhelnicky a 2 izolovane)

co se čtyřky týče, jako logická volba mi příjde kružnice.

Tak s tím grafem s 8 dvojkama jsem tě trochu mystifikoval, ono jich je sakra víc :) konkrétně jsem myslel kružnici. A taky existujou kombinace se 7 vrcholem. Bez těch možností se 7 je jich dvanáct, zkusim ještě zbytek

No a těch 7 musí být sudý počet, graf se 2 sedmama a zbytkem 2 je jen jeden a víc to nejde.

Takže celkem 13 grafů

Ta ctyrka plati jenom pro uplne grafy. Delka cesty mezi libovolnymi 2 vrcholy u,v musi byt 1, jinak by se dalo najit w lezici na ceste z u do v a platilo by d(u,v) = d(u,w)+d(w,v) coz je spor :!:

Munch wrote:Ta ctyrka plati jenom pro uplne grafy. Delka cesty mezi libovolnymi 2 vrcholy u,v musi byt 1, jinak by se dalo najit w lezici na ceste z u do v a platilo by d(u,v) = d(u,w)+d(w,v) coz je spor :!:

Aha, tak to jsem špatně přečetl zadání :?

Dakujem velmi pekne! Nemam velmi dobry pocit z toho, ze pozajtra idem na skusku a toto neviem.. ;)

Milí kolegové,
nějak mě to neleze do hlavy, nemáte někdo k dispozici nějaké řešené příklady? Budu vděčná za všechno.
Mirka