— — Stromy

Stromy

Strom: Souvislý graf bez kružnic. List: Vrchol stupně 1.

LEMMA:

Každý strom s alespoň 2 vrcholy má alespoň 2 listy.

DŮKAZ:

Koncové vrcholy nejdelší cesty jsou listy:

o - o - o - o - o - o - o - o - o - o / /— / “ / o o o o o o

— o

Pokud by nebyly listy, existovala by hrana vedoucí do jiného vrcholu na cestě (ale pak by to byl cyklus), nebo do nového vrcholu, ale pak by původní graf nebyl souvislý.

Pozorování:

G graf, v ∈ V (G) list. Pak:

G strom ⇔ G − v strom

DŮKAZ:

G souvislý ⇔ G − v souvislý

(zřejmé)

G má kružnici ⇔ G − v má kružnici

(kružnice obsahuje samé vrcholy stupně alespoň 2) Q.E.D.

Důsledek:

G strom (|V (G)| ≥ 1) ⟺ z G dostaneme K_{1} = • postupným odebíráním bodů.

VĚTA ():

Nechť G = (V, E) je graf. Pak následující tvrzení jsou ekvivalentní:

(i) G je strom (ii) ∀x, y ∈ V: existuje právě jedna cesta z x do y (iii) G je souvislý, ale G − e není souvislý pro ∀e ∈ E (iv) G nemá kružnici a G + e má kružnici pro ∀e ∈ \binom{V}{2} \ E

(v) G je souvislý a |V | = |E| + 1

DŮKAZ:

(i) ⇒ (ii)

G souvislý ⟹ existuje cesta z x do y

G bez kružnic ⟹ neexistují 2 cesty z x do y Předpokládám P_{1}, P_{2} různé cesty z x do y:

\begin{aligned}P_{1} & = xe_{1}v_{1}e_{2}v_{2} ⋯ y \\ P_{2} & = xe′_{1}v′_{1}e′_{2}v′_{2} ⋯ y \end{aligned}

Nechť i je minimální, pro které platí e_{i} ≠ e′_{i}. Nechť j ≥ i je minimální, pro které ∃ k takové, že v′_{j} = v_{k}. Pak v_{i−1} = v′_{i−1}, v′_{i}, …, v′_{j} = v_{k}, v_{k−1}, …, v_{i} tvoří kružnici. ♯̸ Spor

(ii) ⇒ (iii) e = {x, y} G − e není souvislý, jinak by existovaly dvě cesty z x do y (jedna v G − e, druhá e).

(iii) ⇒ (iv)

Tvrdíme, že G nemá kružnici. Pro spor tedy předpokládejme, že kružnici má. Potom vynecháním libovolné hrany kružnice se neporuší souvislost. To je ale spor s (iii).

G + e (e = {x, y}) má kružnici: G je souvislý, tedy existuje cesta z x do y v G a přímá hrana dotvoří kružnici.

(iv) ⇒ (i) G souvislý: x, y ∈ V, existuje cesta z x do y v G?

(a) {x, y} ∈ E: platí

(b) {x, y} ∉ E: G + {x, y} má kružnici, která nebyla v G, tedy nutně prochází hranou {x, y}. Ostatní hrany kružnice tvoří cestu z x do y v G.

(i) ⇒ (v)

|V | = |E| + 1: z předchozího důsledku. Odebráním listu odebereme právě jednu hranu, platnost rovnice se tedy nemění.

Opakováním dostaneme jednovrcholový strom K_{1} = •, pro ten rovnice platí.

(v) ⇒ (i)

G = (V, E) souvislý, |V | = |E| + 1. G nemá kružnici: nechť G má kružnici; odebereme jednu její hranu, neporušíme

souvislost. Má-li stále ještě nějakou kružnici, opět z ní odebereme hranu. To opakujeme, až dostaneme graf G′ = (V, E′) souvislý bez kružnic (tedy strom |V | = |E′| + 1), |E′| < |E|. Ale předpoklad zněl, že |V | = |E| + 1.

♯̸ Spor