— — 2–souvislost

2–souvislost

Definice:

Graf G = (V, E) je (vrcholově) 2–souvislý, pokud |V | ≥ 3 a G − v je souvislý pro ∀v ∈ V.

Příklad:

o - o

— ¿ o 2--souvislý

o - o

o o / “ / “ o o o není 2--souvislý (ale je hranově 2--souvislý) “ / “ / o o

Pozorování:

G je 2–souvislý ⇒ \{ \begin{matrix}G + e & 2–souvislý pro ∀e ∉ E. \\ G − e & souvislý pro ∀e ∈ E. \\ G % e & 2–souvislý pro ∀e ∈ E. \end{matrix}

DŮKAZ:

(a) zřejmé

(b) e = {x, y} ∈ E G − x souvislý ⇒ y je v G − e v jedné komponentě se všemi vrcholy v ≠ x, y. G − y souvislý ⇒ x je v G − e v jedné komponentě se všemi vrcholy v ≠ x, y. Tedy G − e má určitě jednu komponentu, takže je souvislý.

(c)

e x ----- y --¿ x - z - y .

G G’

G′ − v souvislý ∀v ≠ z. G′ − z = G − e souvislý podle (b).

Q.E.D.

Definice:

Grafy G = (V, E) je hranově 2–souvislý, pokud G je souvislý a G − e je souvislý pro ∀e ∈ E.

VĚTA ():

G je 2–souvislý ⇔ G vznikne z K_{3} = △ postupným přidáváním a dělením hran. T-O-D-O: Obrázek úplného trojúhelníčku s vrcholem uprostřed a jeho odvození z trojúhel-

níčku.

DŮKAZ:

“⇒”

△ je 2–souvislý, přidávání a dělení hran uchovává 2–souvislost.

“⇐”

Nebudeme dělat.

Q.E.D.

VĚTA ():

V 2–souvislém grafu leží každé 2 vrcholy na společné kružnici.

DŮKAZ:

Podle předchozí věty stačí dokázat:

(i) Věta platí pro △. Triviální. (ii) Věta platí pro G ⇒ platí i pro G + e (triviální). (iii) Věta platí pro G ⇒ platí i pro G % e:

Nechť u ∈ V (G), z ∈ V (G′) \ V (G) (vytvořený na e = (x, y)). Leží u, z na společné kružnici? (Ostatní případy jsou triviální.)

C = kružnice v G společná pro x, u.

(1) y ∈ C — T-O-D-O: Obrázek D1

(2) y ∉ C — T-O-D-O: Obrázek D2

P = nejkratší cesta z y do V (C) v G − x. Pak nová kružnice vede z x přes z do y, pak po P až k nějakému vrcholu C a poté po C až zpět k x.

Poznámka:

V 2–souvislém grafu též každé 2 hrany leží na společné kružnici. (Bez důkazu).