Zpět na stránku cvika

9. cvičení

Příklad 1. Rozmyslete si, že graf má kostru, právě když je souvislý.

Příklad 2. Pro která $n \in \mathbb N_0$ existuje graf s právě $n$ kostrami? Pozor, v této úloze $n$ nijak nesouvisí s počtem vrcholů grafu.

Příklad 3. Ukažte, že každý strom na alespoň 3 vrcholech, který neobsahuje vrchol stupně 2, má více listů než vnitřních vrcholů.

Příklad 4. Mějme les na $n$ vrcholech, který má $m$ hran. Víme, že všechny lesy jsou bipartitní. Kolika způsoby lze (v závislosti na $n$ a $m$ rozdělit jeho vrcholy do dvou partit? Rozdělení lišící se pouze prohozením partit považujeme za stejná.

Příklad 5. Hranový graf grafu $G(V,E)$, který má alespoň jednu hranu, je graf $L(G)(E,E')$ tak, že $e_1e_2 \in E' \Leftrightarrow e_1\cap e_2\neq \emptyset$, tedy vrcholy jsou původní hrany a hrany spojují vrcholy reprezentující hrany, co měly společný vrchol. Pro jaké grafy platí, že $L(G)$ je strom? A pro jaké grafy platí, že $L(G)=G$? Najděte dva různé souvislé grafy jímž odpovídá tentýž hranový graf.

Příklad 6. Nechť $n$ je přirozené číslo. Určete počet různých koster následujících grafů: Pozor, různé kostry skutečně musí být různé, ale nevadí, když jsou izomorfní.

  1. Strom na $n$ vrcholech.
  2. Úplný bipartitní graf $K_{n,2}$.
  3. Úplný bipartitní graf $K_{n,3}$.

Příklad 7. Mějme strom $G(V,E)$ a nějaký jeho automorfismus $f$. Dokažte, že buď existuje vrchol $v$ takový, že $f(v)=v$, nebo dva vrcholy $u$, $v$ takové, že $f(u)=v$ a $f(v)=u$.

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

Hledejte $u$ a $v$ takové, že $\{u,v\}\in E$.

Příklad 8. Mějme strom $G$ a několik (alespoň 2) jeho souvislé podgrafy $G_1(V_1,E_1),G_2(V_2,E_2),\dots,G_n(V_n,E_n)$. Dokažte,

  1. Že průnik všech $G_i$ je buď strom nebo prázdný graf.
  2. Že když pro každé dvě $k$, $\ell$ platí, že $V_k\cap V_\ell \neq \emptyset$, pak také $$\bigcap_{i=1}^{n}V_i\neq\emptyset.$$
  3. Že kdyby $G$ nemusel být strom, předchozí tvrzení nemusí platit.