zkouška 25.6.

[stnicolaus]

dneska byly jenom 4 příklady - všechny za stejně bodů

1) Dokažte: platí-li deg(u) + deg(v) ≥ n + 1 pro libovolné dva vrcholy u ≠ v, potom G má Hamiltonovskou kružnici
2) Určete vrcholovou a hranovou souvislost grafu (C₁₂)³ (hrany jsou mezi vrcholy, jejichž vzdálenost v C₁₂ byla ≤ 3)
3) Rozhodněte zda existuje přirozené n takové, že sehraje-li n tenistů zápasy každý s každým, potom se mezi nimi najde 5 hráčů h₁, h₂, h₃, h₄, h₅ takových, že h_i prohrál s h_j pro každé i < j
4) Popsat Ford-Fulkersonův algoritmus a určit minimální řez na konkrétním grafu