Teorie grafů — podzim 2013 — 3. termín 1. (10 bodů) Použitím některého algoritmu založeného na standardních operacích s maticemi určete vzdálenosti mezi všemi dvojicemi vrcholů následujícího grafu. Přitom vrcholy v matici reprezentujte v pořadí vi, v2, v3, vA, v5. 3 4 5 ooo 3. (5 bodů) Dejte příklad ohodnoceného grafu g se šesti vrcholy, který splňuje x{g) = 3 a má právě čtyři různé minimální kostry. Pokud takový graf neexistuje, zdůvodněte proč. 4. (5 bodů) Dejte příklad grafu g se šesti vrcholy, který splňuje x'{g) > x{g) = 2 a je eulerovský i hamiltonovský. Pokud takový graf neexistuje, zdůvodněte proč. 5. (5 bodů) Dejte příklad souvislého grafu se šesti vrcholy, který není bipartitní a neobsahuje cestu délky čtyři. Pokud takový graf neexistuje, zdůvodněte proč. 6. (10 bodů) Určete, pro která přirozená čísla x a y je posloupnost (1,1,1,1,1,1,x,4,í/,2x + 1) skórem nějakého grafu, a svoje rozhodnutí zdůvodněte. Pro všechny takové hodnoty x a y dejte příklad grafu s tímto skóre. 7. (10 bodů) Najděte všechny vzájemně neizomorfní souvislé grafy g se sedmi vrcholy, které splňují x'{g) = 3, mají alespoň dva body artikulace a obsahují kružnici 8. (8 bodů) Rozhodněte, zda jsou následující dva grafy izomorfní. Svoje rozhodnutí zdůvodněte. 9. (7 bodů) Rozhodněte, zda následující graf je rovinný. Pokud rovinný je, doplňte jej na maximální rovinný graf. Pokud rovinný není, svoje rozhodnutí zdůvodněte. 10. (10 bodů) Nechť n > 1 je přirozené číslo a G je obyčejný graf tvořený dvěma disjunktními úplnými bipartitními grafy kn