Zpět na stránku cvika

10. cvičení

Definice. Roviný graf je graf, který má rovinné nakreslení.

Definice. Dělení grafu $G$ je graf $G'$, který vyrobíme z grafu $G$ tak, že některé jeho hrany nahradíme cestami.

Kuratovského věta. Graf je rovinný, právě když neobsahuje jako svůj podgraf dělení $K_{3,3}$ ani $K_5$.

Věta (Eulerova formule). Mějme souvislý rovinný graf $G(V,E)$ a jeho nakreslení, které má $F$ stěn ($F$ podle anglického "faces"). Pak $|V|-|E|+|F|=2$.

Věta. $G(V,E)$ budiž rovinný graf na alespoň 3 vrcholech. Pak $|E|\leq 3|V|-6$. Pokud v $G$ navíc neexistuje trojúhelník, pak dokonce $|E|<2|V|-4$.

Důsledek. V každém rovinném grafu existuje vrchol, jehož stupeň je nejvýše 5.

Příklad 1. Dokažte, že $Q_4$ není rovinná. $Q_n$ je obecně graf $K_2^n$ (ve smyslu kartézského násobení grafů z domácího úkolu), alternativně $Q_n(\mathcal P([n]),\{\{a,b\}\mid |a\triangle b|=1\})$, neboli také $n$-rozměrná krychle.

Příklad 2. Odvoďte ekvivalent Eulerovy formule pro nesouvislé grafy (tj. přidejte 4. proměnnou určující počet komponent).


Definice. Vnějškově rovinný graf je graf, který má rovinné nakreslení takové, že v něm všechny vrcholy leží na jedné stěně.

Definice. Graf je $d$-degenerovaný, pokud každý jeho podgraf obsahuje vrchol stupně nejvýše $d$.

Příklad 3. Rozmyslete si, že pokud je graf $d$-degenerovaný, tak je $k$-degenerovaný pro každé $k\geq d$.

Definice. Degenerovanost grafu $G$ je nejnižší $d$ takové, že $G$ je $d$-degenerovaný.

Příklad 4. Určete (nejvyšší možnou) degenerovanost:

  1. Stromu
  2. Rovinného grafu
  3. Vnějškově rovinného grafu
  4. Grafu $G$, v němž mají všechny vrcholy stupeň v intervalu $[k,m]$ pro nějaká přirozená čísla $k$ a $m$ (a jak stupeň $k$, tak $m$ je v grafu zastoupen).

Příklad 5. Odvoďte ekvivalent Kuratowského věty pro vnějškově rovinný graf.

Zobraz nápovědu Skryj nápovědu

Ukažte, že graf je vnějškově rovinný, právě když k němu můžeme přidat vrchol spojený se všemi ostatními vrcholy a výsledný graf je rovinný.

Příklad 6. (hvězdičkový) Dokažte, že v každém rovinném grafu lze zorientovat hrany tak, aby měl každý vrchol výstupní stupeň nejvýše 3.

Zobraz nápovědu Skryj nápovědu

Pro spor nechť to nejde. Podívejte se na podgraf indukovaný množinou vrcholů, kam se dá dostat po orientovaných cestách z vrcholu s výstupním stupněm 4. Aplikujte výše uvedenou nerovnost na to, abyste dokázali, že je v něm vrchol výstupního stupně 2.

Příklad 7. (hvězdičkový) Navrhněte co nejrychlejší algoritmus na hledání orientace zmíněné v předchozím příkladu.

Zobraz nápovědu Skryj nápovědu

Jde to lineárně hladovým algoritmem. Bude se hodit výsledek příkladu 3.3 a fakt, že v každém rovinném grafu existuje pro každý vrchol nakreslení takové, že právě tento vrchol je na vnější stěně..

Definice. Duální graf (multi)grafu $G$ je multigraf takový, že jeho vrcholy jsou stěny původního grafu, a jeho hrany jsou právě tam, kde měly původní stěny společnou hranu.

Poznámka. I duální graf normálního grafu může být multigraf. Duální graf grafu nemusí být určen jednoznačně, může záležet na nakreslení. Pokud však mezi opakováním operace "Najdi duál" nebudeme nakreslení měnit, platí, že duál duálu souvislého rovinného grafu $G$ je opět $G$.

Příklad 8. Najděte graf, jehož dvě různá nakreslení vedou na dva různé neizomorfní duály.

Příklad 9. Může existovat 3-regulární graf, jehož všechny stěny budou šestiúhelníky? A pětiúhelníky?

Příklad 10. Dokažte, že pro každý graf $G$ na jedenácti vrcholech buď $G$ nebo $\overline G$ není rovinný.