12.2. Král

[sHerpa]

1. Definujte pojem podgrafu. Kolik podgrafů má K3?
2. Popište problém minimální kostry, algoritmus pro jeho řesení a dokažte jeho správnost.
3. Mohou mít dva grafy G1 a G2 stejné skóre, jestliže
a. G1 je 2-souvislý, G2 není souvislý
b. G1 je strom, G2 je 2-souvislý
c. G1 není rovinný, G2 je kružnice
d. G1 není rovinný, G2 je strom

na většinu u trojky je odpověď ano, myslím kromě b

4. Které z následujících výroků jsou správné?
a. Grafy G a H jsou izomorfní, právě když existuje bijekce f: E(G) -> E(H)
b. Jestliže jsou grafy G a H izomorfní, pak existuje bijekce f: V(G) -> V(H) taková, že každý vrchol u z V(G) má stejný stupeň jako f(u).

[christius]

1. definice souvisleho grafu + nejvetsi mozny pocet hran grafu s n vrcholy a t komponentami, ktery nemá kruznici.
2. Veta o max. poctu hran v n-vrcholovém grafu bez K_3 + dukaz
3. pocet permutaci pismen A,D,K,O,P,S,T,V bez slov KOP, PAST, VODA
4. Dokázte: má-li souvisly G vsechny stupne sudé, neobsahuje most.
(most= hrana e take, ze G\e je nesouvisly)