Skip to content

3.1 Základní pojmy

Strom, Les, List

Definice 3.1 (Strom)

Strom

Graf \(G\) nazveme stromem, pokud je souvislý a neobsahuje žádnou kružnici (čili je acyklický).

Definice 3.2 (Les)

Les

Graf \(G\) nazveme lesem, pokud neobsahuje žádnou kružnici.

Definice 3.3 (List)

List

Vrchol v grafu \(G\) nazveme listem, pokud \(deg_{G}(v) = 1\).

Věta 3.1 (o existenci listů)

Věta o existenci listů

Každý strom \(T\) s aspoň \(2\) vrcholy obsahuje aspoň dva listy.

Důkaz Věty 3.1
  1. Nechť \(P\) je nejdelší cesta v \(T\).
  2. Nechť \(u\) a \(v\) jsou její koncové vrcholy.
  3. Sporem ukážeme, že \(u\) a \(v\) jsou listy.
  4. Kdyby z \(u\) vedly aspoň dvě hrany, jedna z nich bude patřit do \(u\)-\(v\)-cesty \(P\) a zbývat bude ještě aspoň jedna hrana \(e = \{u, w\}\).
  5. Kdyby \(w \in V(P)\), byla by v \(T\) kružnice.
  6. Kdyby \(w \notin V(P)\), cesta \(P\) by šla prodloužit a nebyla by tedy nejdelší.
  7. To samé platí pro koncový vrchol \(v\) - SPOR.

Důsledek

Protože cesty jsou stromy, existují stromy, mající právě dva listy.

Listy, kružnice a souvislost v grafech

  • Uvažujme graf \(G = (V, E)\), ve kterém existuje list \(v\). Označme \(w\) jeho souseda v \(G\). Pak odebrání listu \(v\) z \(G\) je operace, kterou vznikne graf \(G − v = (V \setminus \{v\}, E \setminus \{\{w, v\}\})\).
  • Uvažujme graf \(G = (V, E)\) a zvolme \(w \in V\) . Pak přidání listu \(v\) k vrcholu \(w, v \notin V\) , ke grafu \(G\) je operace, kterou vznikne graf \(G + v = (V \cup \{v\}, E \cup \{\{w, v\}\})\).

Věta 3.2 (o trhání listů)

Věta o trhání listů

Nechť \(G = (V, E)\) je graf na aspoň 2 vrcholech a nechť \(v \in V\) je jeho list. Pak jsou následující tvrzení ekvivalentní:

  1. \(G\) je strom.
  2. \(G − v\) je strom
Důkaz Věty 3.2

(1) \(G\) je strom \(\implies\) (2) \(G − v\) je strom:

(1) \(G − v\) je souvislý:

  • Zvolme libovolně dva vrcholy \(x, y \in V \setminus \{v\}\) a cestu \(P\) mezi nimi v \(G\) (ta existuje, protože \(G\) je souvislý).
  • \(P\) nemůže obsahovat jiné vrcholy stupně 1 než \(x\), \(y\); tedy speciálně neobsahuje \(v\)
  • Dostáváme tedy \(P \subseteq G − v\) a tedy \(G − v\) je souvislý.

(2) \(G − v\) je bez kružnic:

  • \(G − v\) je podgraf \(G\) a tedy neobsahuje kružnici.

Tedy \(G − v\) je strom

(2) \(G - v\) je strom \(\implies\) (1) \(G\) je strom:

(1) \(G\) je bez kružnic:

  • Vrácením listu \(v\) do grafu \(G\) (přidáním listu ke stromu \(G − v\))
    zjevně nevytvoříme kružnici.

(2) \(G\) je souvislý:

  • Mezi každými dvěma \(x, y \in V \setminus \{v\}\) vede cesta v \(G − v\).
  • Cesta v \(G\) z libovolného vrcholu \(x\) do \(v\) vznikne prodloužením cesty mezi \(x\) a \(w\) do vrcholu \(v\), kde \(w\) je (jediný) soused listu \(v\).

Tedy \(G\) je strom