# 12.2. Král

<{ForumPost(poster="sHerpa", timestamp=2007-02-12 18:19:33)}>
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).
<{/ForumPost}>

<{ForumPost(poster="christius", timestamp=2007-02-12 19:19:52)}>
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)
<{/ForumPost}>