Pavel Valtr

Diskrétní matematika

Přepsal Petr Baudiš v ak. roce 2004/2005

“Beauty is the first test. There is no permanent place in the world for ugly mathematics.” — G. H. HARDY

◯^{c} 2004/2005 Pavel Valtr, Petr Baudiš Verze 1.618/L:1.6. Tato verze není garantována, nemusí být kompletní a může obsahovat chyby. Aktuální verzi vždy najdete na http://math.or.cz/. Sazba v programu TEX.

Pavel Valtr — Diskrétní matematika Základní pojmy —

Základní pojmy

Množiny

Množina: soubor prvků.

Zápis:

• výčtem prvků: X = {a, b, c}
• vlastností: X = {i ∈ ℕ : ∃ j ∈ ℕ, i = j}

X = Y ⇔ (x ∈ X ⇔ x ∈ Y) ∀x

Je-li X konečná, |X| ⇔ len(X) (velikost, mohutnost).

X ⊆ Y ⇔ (x ∈ X ⇒ x ∈ Y) ∀x

P (X): Potenční množina množiny X — množina všech podmnožin množiny X (včetně ∅ a X). Je-li X konečná, |P (X)| = 2^{|X|}.

Symbolika: |X| ∩ |Y |, |X| ∪ |Y |, |X| \ |Y |, …

Relace

Neuspořádaná dvojice: {x, y} Uspořádaná dvojice: (x, y): (x, y) = (x′, y′) ⇔ (x = x′ ∧ y = y′); např. {{x}, {x, y}} Kartézský součin: X × Y = {(x, y) : x ∈ X, Y ∈ Y } Relace R mezi X, Y: R ⊆ X × Y Relace R na X: R ⊆ X × X Značení: (x, y) ∈ ℝ: xRy (jde-li o binární relaci)

Definice:

Relace R na množině X je:

• reflexivní: xRx ∀x ∈ X : xRx

• symetrická: xRy ⇒ yRx ∀x, y ∈ X

• tranzitivní: (xRy ∧ yRz) ⇒ xRz ∀x, y, z ∈ X • ekvivalence: reflexivní, symetrická, tranzitivní

Třídy ekvivalence

Určené prvkem x:

R[x] = {y ∈ X, xRy}

(díky symetrii platí i yRx).

Příklad:

X = {1, 2, 3, 4}

R = {(1, 1), (2, 2), (3, 3), (4, 4), (2, 4), (4, 2)}

\begin{aligned}R[1] & = \{1\} \\ R[2] = R[4] & = \{2, 4\} \end{aligned}

Tvrzení:

(i) x ∈ R[x] ∀x ∈ X
(ii) R[x] = R[y] ∨ R[x] ∩ R[y] = ∅ ∀x, y ∈ X

Základní pojmy — Uspořádání Pavel Valtr — Diskrétní matematika

DŮKAZ:

(i) Z reflexivity. (ii) Nechť x, y ∈ X:

(1) Předpokládejme xRy:

R[x] ⊆ R[y]: Mějme libovolné z ∈ R[x], tedy zRx →^{tranz.} zRy, to znamená z ∈ R[y]. Q.E.D.

R[y] ⊆ R[x] obdobně (symetrie).

R[x] = R[y]

(2) Předpokládejme, že neplatí xRy:

Pro spor nechť R[x] ∩ R[y] ≠ ∅. Mějme libovolné z ∈ R[x] ∩ R[y]. Pak jistě

xRz ∧ zRy ⇒^{tranz.} xRy. ♯̸ Spor

R[x] ∩ R[y] = ∅

Důsledek:

Množina (systém množin) {R[x] : x ∈ X} tvoří tzv. rozklad množiny X. ∀x ∈ X pak patří do právě jedné množiny z rozkladu.

Uspořádání

(Částečné) uspořádání: Relace na X, která je reflexivní, tranzitivní a antisymetrická (xRy ∧ yRx ⇒ x = y ∀x, y ∈ X).

Značení: ≤ či ⪯ Příklady: (ℕ, ⪯), (ℕ, |) (dělí), (P (X), ⪯) Lineární uspořádání: Takové uspořádání, že xRy ∨ yRx ∀x, y ∈ X. Pozn.: (P (X), ⪯) je lineární, pokud |X| ≤ 1.

Zobrazení

Definice:

Máme-li množiny X, Y, zobrazení z X do Y definujeme jako libovolnou relaci f ⊆ X × Y, která splňuje předpoklad, že ∀x ∈ X ∃! y ∈ Y takové, že xfy.

Značení: f: X → Y, f: x ↦ y, f(x) = y

Definice:

Máme-li f: X → Y a g: Y → Z, složené zobrazení g ∘ f značí zobrazení X → Z, definované předpisem:

(g ∘ f)(x) = g(f(x)) ∀x ∈ X

Poznámka:

g ∘ f je skutečné zobrazení z X do Z:

(g ∘ f)(x) = g(\underbrace{f(x)}_{∃! y}) = \underbrace{g(y)}_{∃! z} = z

Definice:

Říkáme, že zobrazení f: X → Y je:

Pavel Valtr — Diskrétní matematika Základní pojmy — Zobrazení

• prosté (injekce f: X ↔ Y), pokud x ≠ y ⇒ f(x) ≠ f(y) ∀x, y ∈ X.

• na (z X na Y) (surjekce f: X →> Y), pokud ∀y ∈ Y ∃ x ∈ X takové, že f(x) = y.

• vzájemně jednoznačné (bijekce f: X ↔> Y či f: X ⟷^{1–1} Y), pokud je prosté a na.

Pro konečné množiny platí: • prosté: |X| ≤ |Y |

• na: |X| ≥ |Y |

• bijekce: |X| = |Y |

Pozn.: Pojem funkce se používá ve významu “zobrazení” či “zobrazení do ℝ”.

Kombinatorika — Pavel Valtr — Diskrétní matematika

Kombinatorika

Permutace a faktoriál

Permutace konečné množiny X: Libovolná bijekce π: X ⟷^{1–1} X.

Příklad:

Mějme množinu X = {a, b, c, d}, definujme permutaci π(a) = b, π(b) = d, π(c) = c, π(d) = a. Matice permutace pak je

( \begin{matrix}a & b & c & d \\ b & d & c & a \end{matrix} ) ,

permutace tvoří uspořádání

(b, d, c, a)

a dá se vyjádřit na grafu jako

a * ---¿ * b ˙ — —“ — “ v

c *¡-“ * d “-/

n faktoriál: n! = 1 · 2 · 3 ⋯ n, 0! = 1

Tvrzení:

Počet permutací n-prvkové množiny je n!.

DŮKAZ:

n možností, kam se zobrazí první prvek. n − 1 možností, kam se zobrazí druhý prvek. …

VĚTA ():

|X| = n, |Y | = k. Pak existuje:

• k^{n} zobrazení X → Y.

• k(k − 1)(k − 2) … (k − n + 1) prostých zobrazení X → Y.

• k! = n! bijekcí X ⟷^{1–1} Y, pokud k = n.

• 0 bijekcí X ⟷^{1–1} Y, pokud k ≠ n.

Kombinační čísla

Definice:

Kombinační číslo (neboli binomický koeficient):

\binom{n}{k} = \frac{n!}{k!(n − k)!} = \frac{n(n − 1) … (n − k + 1)}{k(k − 1) … 1} n, k ∈ ℕ_{0}, n ≥ k

Alternativní definice:

Pavel Valtr — Diskrétní matematika Kombinatorika — Kombinační čísla

\binom{n}{k} je počet k-prvkových podmnožin n-prvkové množiny.

Tvrzení:

Obě definice jsou ekvivalentní. DŮKAZ:

Nechť |X| = n. Pak počet uspořádaných k-tic různých prvků z X je kombinatorickou úvahou

n(n − 1)(n − 2) … (n − k + 1) = \frac{n!}{(n − k)!}.

Zároveň však tento počet můžeme spočítat přes kombinační čísla jako (počet k-prvko-vých podmnožin X)(počet možných uspořádání) = \binom{|X|}{k}k! = \frac{n!}{(n − k)!} .

Q.E.D.

Značení:

Buď X množina. Pak \binom{X}{k} je množina všech k-prvkových podmnožin množiny X. Navíc

|\binom{X}{k}| = \binom{|X|}{k}.

Platí:

(i) Symetrie:

\binom{n}{k} = \binom{n}{n − k} n ≥ k ≥ 0

DŮKAZ:

Z definice kombinačního čísla (algebraicky nebo doplňky).

(ii) Sousední čísla:

\binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 1}{k}

DŮKAZ:

Z množinové definice kombinačního čísla:

|\binom{X}{k}| = \underbrace{|\binom{X \ \{x_{n}\}}{k − 1}|}_{počet k-prvkových podm. množiny X obs. x_{n}} + \underbrace{|\binom{X \ \{x_{n}\}}{k}|}_{počet k-prvkových podm. množiny X neobs. x_{n}}

Q.E.D.

Pascalův trojúhelník

Ve vrcholu △ je 1, okraje jsou lemovány nulami, každý prvek je součtem dvou prvků nad ním.

1

1 1
1 2 1
1 3 3 1
1 4 6 4 1

Kombinatorika — Kombinační čísla Pavel Valtr — Diskrétní matematika

Pohled přes kombinační čísla:

\binom{0}{0}
\binom{1}{0}  \binom{1}{1}
\binom{2}{0}  \binom{2}{1}  \binom{2}{2}
\binom{3}{0}  \binom{3}{1}  \binom{3}{2}  \binom{3}{3}
\binom{4}{0}  \binom{4}{1}  \binom{4}{2}  \binom{4}{3}  \binom{4}{4}

neboť \binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 1}{k} .

Binomická věta

Víme:

(x + y)^{2} = x^{2} + 2xy + y^{2} (x + y)^{3} = x^{3} + 3x^{2}y + 3xy^{2} + y^{3}

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k} n ∈ ℕ_{0}, x, y ∈ ℝ

DŮKAZ:

Indukcí podle n:

(1) n = 0, n = 1

\begin{aligned}(x + y)^{0} & = \binom{0}{0}x^{0}y^{0} = 1 \\ (x + y)^{1} & = \binom{1}{0}x^{0}y^{1} + \binom{1}{1}x^{1}y^{0} \end{aligned}

(2) n ⇒ n + 1

(x + y)^{n+1} = (x + y)^{n}(x + y) = (x + y) (\binom{n}{0}x^{0}y^{n} + ⋯ + \binom{n}{n}x^{n}y^{0}) =

= \binom{n}{0}x^{1}y^{n} + ⋯ + \binom{n}{n}x^{n+1} y^{0} + \binom{n}{0}x^{0}y^{n+1} + ⋯ + \binom{n}{n}x^{n}y^{1} =

= \binom{n + 1}{0}x^{0}y^{n+1} + \binom{n + 1}{1}x^{1}y^{n} + ⋯ + \binom{n + 1}{n}x^{n}y^{1} + \binom{n + 1}{n + 1}x^{n+1} y^{0} =

= ∑_{k=0}^{n+1} \binom{n + 1}{k}x^{k}y^{(n+1)−k}

Důsledek:

(1 + x)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}

Pavel Valtr — Diskrétní matematika Kombinatorika — Multinomická věta

Multinomická věta

∀n ∈ ℕ_{0}, ∀m ∈ ℕ, ∀x_{1}, …, x_{m} ∈ ℝ :

(x_{1} + x_{2} + ⋯ + x_{m})^{n} = ∑_{{k_{1} ,k_{2} ,...,k_{m}≥0 \atop k_{1} +k_{2} +···+k_{m}=n}} \binom{n}{k_{1}, k_{2}, …, k_{m}}(x_{1}^{k_{1}}x_{2}^{k_{2}} ⋯ x_{m}^{k_{m}})

Bez důkazu.

Poznámka:

Pro m = 2 odpovídá binomické větě.

Multinomický koeficient

\binom{n}{k_{1}, …, k_{m}} = \frac{n!}{k_{1}!k_{2}! ⋯ k_{n}!}

Počet způsobů zařazení čísel 1, …, n do m množin x_{1}, …, x_{m} tak, aby |x_{1}| = k_{1}, …, |x_{m}| = k_{m}.

Platí

\binom{n}{k} = \binom{n}{k, n − k}

Příklad:

200 dětí, 3 autobusy (80, 70, 50), počet možností rozmístění

\binom{200}{80, 70, 50}

Kombinatorika — Odhady faktoriálů a kombinačních čísel Pavel Valtr — Diskrétní matematika

Odhady faktoriálů a kombinačních čísel

Faktoriály

Věta

n^{n/2} ≤ n! ≤ (\frac{n + 1}{2} )^{n}

n^{n/2} = (\sqrt{n})^{n}

DŮKAZ:

(n!)^{2} = \underbrace{(1 · n)(2 · (n − 1)) ⋯ (n · 1)}_{(n! jednou popředu a k tomu podruhé odzadu)}
(n!)^{2} = z_{1} · z_{2} ⋯ z_{2n}

Z AG nerovnosti:

z ≤ (\frac{n + 1}{2} )^{2}

A protože

(i + 1)(n − i) = n + i(n − 1 − i) ≥ n

(pro i = 0, 1, ⋯, n − 1 ⇒ (i ≥ 0 ∧ (n − 1 − i) ≥ 0)), platí:

z ≥ n

Tedy:

(n^{n}) ≤ (n!)^{2} ≤ ((\frac{n + 1}{2} )^{2})^{n}

n^{n/2} ≤ n! ≤ (\frac{n + 1}{2} )^{n}

Q.E.D.

Přesněji

n! ≈ (\frac{n}{e})^{n} · \sqrt{2πn}

tj. lim_{n→∞} \frac{n!}{(\frac{n}{e})^{n} · \sqrt{2πn}} = 1

Bez důkazu.

Kombinační čísla

Můžeme přeformulovat jako odhad prostředního čísla v n-tém řádku Pascalova trojúhelníku.

Víme

\binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{n} = 2^{n}

Protože součet je počet podmnožin n-prvkové množiny. Alternativní výklad: Každá čísla v předcházejícím řádku přispějí 2× do dalšího řádku.

Pavel Valtr — Diskrétní matematika Kombinatorika — Odhady faktoriálů a kombinačních čísel

Zřejmě z první definice kombinačního čísla:

\binom{n}{0} < \binom{n}{1} < ⋯ < \binom{n}{⌊\frac{n}{2}⌋} = \binom{n}{⌈\frac{n}{2}⌉} > ⋯ > \binom{n}{n}

\frac{2^{n}}{n + 1} < \binom{n}{⌊\frac{n}{2}⌋} < 2^{n}

Přesněji:

\binom{n}{⌊\frac{n}{2}⌋} ≈ \frac{2^{n}}{\sqrt{πn/2}}

Platí také:

\binom{n}{0} + \binom{n}{1} + ⋯ + \binom{n}{k} ≤ (\frac{e · n}{k})^{k}

Bez důkazu. (Ve skriptech, nepovinný.)

Kombinatorika — Princip inkluze a exkluze (PIE) Pavel Valtr — Diskrétní matematika

Princip inkluze a exkluze (PIE)

Příklad:

|A_{1} ∪ A_{2}| = |A_{1}| + |A_{2}| − |A_{1} ∩ A_{2}|

|A_{1} ∪ A_{2} ∪ A_{3}| = |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} ∩ A_{2}| − |A_{1} ∩ A_{3}| − |A_{2} ∩ A_{3}| + |A_{1} ∩ A_{2} ∩ A_{3}|

VĚTA (PIE):

Jsou-li A_{1}, A_{2}, …, A_{n} konečné množiny:

| ⋃_{i=1}^{n} A_{i}| = ∑_{k=1}^{n} \underbrace{(−1)^{k+1}}_{(parita)} · ∑_{I∈\binom{\{1,..,n\}}{k}}| ⋂_{i∈I} A_{i}|

(Ve vnořené sumě sčítáme přes všechny k-prvkové podmnožiny množiny 1..n.)

DŮKAZ:

Nechť x je libovolný prvek z A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n}. Pro n = 1, n = 2 viz diagramy množin, nakreslit si, kam který prvek přispívá: +1 − 1 + 1 ⋯

Kolikrát je počítán x vlevo, kolikrát vpravo? Vlevo jednou — triviální.

Vpravo Nechť j označuje počet množin A_{i}, do kterých patří x. Příklad:

x ∈ A_{1}, …, A_{j}
x ∉ A_{j+1} , …, A_{n}

Pak platí:

#x = \binom{j}{1} − \binom{j}{2} + \binom{j}{3} − ⋯ + (−1)^{j−1} \binom{j}{j}

= ∑_{i=1}^{j}(−1)^{i−1} \binom{j}{i} + 1 − 1

Obracíme znaménko a paritu:

= 1 − ∑_{i=0}^{j}(−1)^{i}\binom{j}{i}

= 1 − (−1 + 1)^{j}

= 1

Q.E.D.

Příklad:

|X| = {1, …, n}, |Y | = {1, …, l}, n ≥ l

Kolik existuje zobrazení z X na Y? Všech zobrazení z X do Y je l^{n}. Nechceme počítat ta, ve kterých se na nějaký prvek Y

nezobrazuje žádný prvek z X:

∃ y ∈ Y : ∀x ∈ X, f(x) ≠ y.

Pavel Valtr — Diskrétní matematika Kombinatorika — Princip inkluze a exkluze (PIE)

Pro všechna i = 1, …, l platí:

A_{i} = {j: X → Y | ∀x ∈ X, f(x) ≠ i} = {j: X → Y − {i}}

|A_{i}| = (l − 1)^{n}

Pro i_{1} ≠ i_{2}:

A_{i_{1}} ∩ A_{i_{2}} = {f: X → Y − {i_{1}, i_{2}}}
|A_{i_{1}} ∩ A_{i_{2}}| = (l − 2)^{n}

Pro \{i_{1}, …, i_{k}\} ∈ \binom{\{1, …, l\}}{k}:

A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}} = {f: X → Y − {i_{1}, …, i_{k}}} {A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}}} = (l − k)^{n}

Počet zobrazení z X na Y je:

l^{n} − | ⋃_{i=1}^{l} A_{i}| =

= l^{n} − (\binom{l}{1}(l − 1)^{n} − \binom{l}{2}(l − 2)^{n} + \binom{l}{3}(l − 3)^{n} − ⋯ +

+(−1)^{l−2} \binom{l}{l − 1}(l − (l − 1)^{n}) + (−1)^{l−1} \binom{l}{l}(l − l)^{n}) =

= ∑_{k=0}^{l−1}(−1)^{k}\binom{l}{k}(l − k)^{n}

Kombinatorika — Vánoční besídka (šatnářka) Pavel Valtr — Diskrétní matematika

Vánoční besídka (šatnářka)

n dárců dostane nazpět n dárků. Každá z n! možností je stejně pravděpodobná. Jaká je pravděpodobnost, že nikdo nedostane zpátky svůj dárek?

Matematická formulace

Hledáme \frac{š(n)}{n!} , š(n) = počet permutací π množiny \{1, …, n\} bez pevného bodu. Pevný bod: i je pevný bod, pokud π(i) = i.

VĚTA (Šatnářka):

š(n) = n! (1 − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!} + ⋯ + (−1)^{n} \frac{1}{n!})

Příklad:

š(1) = 1! (1 − \frac{1}{1!}) = 0

š(2) = 2! (1 − \frac{1}{1!} + \frac{1}{2!}) = 1

š(3) = 3! (1 − \frac{1}{1!} + \frac{1}{2!} − \frac{1}{3!}) = 2

DŮKAZ:

S_{n} = množina všech permutací {1, …, n}
A_{i} = {π ∈ S_{n}, i = 1, …, n : π(i) = i}

|A_{i}| = (n − 1)! (Prvek i stojí, ostatní se propermutují.)

Pro I = {i_{1}, …, i_{k}} ⊆ {1, …, n} platí:

\underbrace{⋂_{i∈I} A_{i}}_{A_{i_{1}} ∩···∩A_{i_{k}}} = množina vsech permutací π

množiny {1, …, n} takových, že π(i_{1}) = i_{1}, …, π(i_{k}) = i_{k}.

| ⋂_{i∈I} A_{i}| = (n − k)! (t prvků stojí, ostatní se propermutují.)

š(n) = |S_{n}| − | ⋃_{i=1}^{n} A_{i}| =

= n! − ∑_{k=1}^{n}(−1)^{k−1} · ∑_{I∈\binom{\{1,...,n\}}{k}} \underbrace{| ⋂_{i∈I} A_{i}|}_{(n−k)!}

= n! − ∑_{k=1}^{n}(−1)^{k−1} · \underbrace{\binom{n}{k}(n − k)!}_{\frac{n!}{k!}}

= n! · (1 − ∑_{k=1}^{n} \frac{(−1)^{k−1}}{k!} )

Pavel Valtr — Diskrétní matematika Kombinatorika — Vánoční besídka (šatnářka)

Q.E.D. Tedy pravděpodobnost, že nikdo nedostane zpět svůj dárek, je:

\frac{š(n)}{n!} = 1 − \frac{1}{1!} + \frac{1}{2!} − ⋯ ± \frac{1}{n!} → \frac{1}{e} ≈ 0.36787 …

Grafy — Pavel Valtr — Diskrétní matematika

Grafy

Definice

Graf G je uspořádaná dvojice (V, E), kde V je libovolná konečná množina (obecněji zcela libovolná) a E ⊆ \binom{V}{2}.

Úplný graf (na n vrcholech):

K_{n} = (V, \binom{V}{2})

Kružnice:

C_{n} = ({v_{1}, …, v_{n}}, {{v_{1}, v_{2}}, {v_{2}, v_{3}}, …, {v_{n−1}, v_{n}}, {v_{n}, v_{1}}}) n ≥ 3

Cesta:

P_{n} = ({v_{0}, …, v_{n}}, {{v_{0}, v_{1}}, {v_{1}, v_{2}}, …, {v_{n−1}, v_{n}}})

Sled: v_{0}, e_{1}, v_{1}, e_{2}, …, e_{m}, v_{m}, kde e_{i} = {v_{i−1}, v_{i}}. (Cesta je tedy speciální druh sledu, kde jedním vrcholem neprojdeme vícekrát.)

Úplný bipartitní graf K_{n,m} = (V, E)

V = {u_{1}, …, u_{n}, v_{1}, …, v_{m}}
E = {{u_{i}, v_{j}} : i = 1, …, n; j = 1, …, m}
|V | = n + m, |E| = n · m

Příklad:

K_{2,3}:

*-“ * /-* “ X X / *-ˆ -*

Bipartitní graf

Graf G = (V, E) takový, že:

V = \underbrace{U ∪^{.} W}_{{V =U∪W, \atop U∩W =0}}

E ⊆ {{u, w} : u ∈ U, w ∈ W }

Isomorfismus

“Přejmenování vrcholů” G | G′ (G, G′ jsou izomorfní), pokud existuje bijekce f: V (G) ⟷^{1–1} V (G′) taková, že:

{x, y} ∈ E(G) ⇔ {f(x), f(y)} ∈ E(G′)

Pozn.: Izomorfismus je ekvivalence (reflexivní, symetrická, tranzitivní).

Podgraf: Graf G′ je podgrafem grafu G (G′ ⊆ G), pokud V (G′) ⊆ V (G) a E(G′) ⊆ E(G).

Pavel Valtr — Diskrétní matematika Grafy —

Indukovaný podgraf

Graf G′ je indukovaným podgrafem grafu G, pokud V (G′) ⊆ V (G) a E(G′) = E(G) ∩ \binom{V (G′)}{2}.

Pozorování

Graf G na n vrcholech má 2^{n} indukovaných podgrafů (každá podmnožina V indukuje indukovaný podgraf).

Souvislý graf

Graf G je souvislý, pokud ∀x, y ∈ V (G) existuje v G cesta z x do y: x ∼_{G} y. ∼_{G} je ekvivalence na množině V (G).

DŮKAZ:

Reflexivita a symetrie je zřejmá.

Tranzitivita:

x ∼_{G} y ∧ y ∼_{G} z ⇒ ∃ sled z x do z

Nejkratší sled z x do z je cesta ⇒ x ∼_{G} z. Q.E.D.

Poznámka:

G souvislý ⇔ ∀x, y ∈ V (G) ∃ sled z x do y (v G)

Komponenta grafu G

Podgraf indukovaný třídami ekvivalence ∼_{G}. Pozn.: G souvislý ⇔ má jednu komponentu.

Vzdálenost v grafu

x, y ∈ V (G), d_{G}(x, y) = vzdálenost x, y v G = délka nejkratší cesty z x do y

Poznámka:

d_{G}(x, y) má vlastnosti metriky (vzdálenosti):

d_{G}(x, y) ≥ 0
d_{G}(x, y) = 0 ⇔ x = y
d_{G}(x, y) = d_{G}(y, x)
d_{G}(x, y) + d_{G}(y, z) ≥ d_{G}(x, z)

Sousedi v grafu: y je soused x v G, pokud {x, y} ∈ E(G) (⇔ d_{G}(x, y) = 1). Matice sousednosti:

G = (\{v_{1}, …, v_{n}\}, E) : A_{G} = (a_{i,j})_{i,j=1}^{n} , a_{i,j} = \{ \begin{matrix}1 & \{v_{i}, v_{j}\} ∈ E(G) \\ 0 & jinak \end{matrix}

Stupeň vrcholu: Stupeň vrcholu x v G jest deg_{G}(x) = deg(x) = počet hran obsahujících x = počet sousedů.

Grafy — Věta o sudosti (princip sudosti) Pavel Valtr — Diskrétní matematika

Věta o sudosti (princip sudosti)

∀G = (V, E) : ∑_{v∈V} deg_{G}(v) = 2|E|

DŮKAZ:

Vlevo každá hrana přispěje 2×. Q.E.D.

Důsledek:

∀G: počet vrcholu každého stupně je sudý.

Poznámka:

Neplatí pro nekonečné grafy (o-o-o-o-⋯).

o / “

o ----- o ----- o ----- o

Skóre grafu

G = ({v_{1}, …, v_{n}}, E), skóre grafu G = D(G) = (deg_{G}(v_{1}), …, deg_{G}(v_{n}))

Dvě skóre považujeme za stejná, pokud se liší pouze pořadím prvků.

Příklad:

o / “

o ----- o ----- o ----- o má skóre (1, 2, 2, 2, 3).

o / “ o - o - o - o

k němu není izomorfní.

Věta o skóre:

D = (d_{1}, …, d_{n}, 0 ≤ d_{1} ≤ ⋯ ≤ d_{n})

D je skóre nějakého grafu, právě když

D′ = (d_{1}, …, d_{n−d_{n}−1}, d_{n−d_{n}} − 1, …, d_{n−2} − 1, d_{n−1} − 1)

je skóre nějakého grafu.

Příklady použití:

Je (1, 2, 3, 3, 3, 4, 4) skóre nějakého grafu? (1, 2, 2, 2, 2, 3) skóre nějakého grafu?

Pavel Valtr — Diskrétní matematika Grafy — Skóre grafu

(1, 2, 1, 1, 1)
(1, 1, 1, 1, 2)
(1, 1, 0, 0) ⇔ (0, 0, 1, 1)
(0, 0, 0)

je skóre grafu.

Je (1, 1, 1, 2)?

(1, 0, 0)
(0, 0, 1)
(0, −1)

není.

Je (0, 1, 2, 3, 4, 4)?

(0, 0, 1, 2, 3)
(0, −1, 0, 1)

DŮKAZ:

“⇐”

G′ má skóre D′. Přidáme ke G′ nový vrchol v_{n} a spojíme ho hranou s vrcholy v_{n−1}, v_{n−2}, …, v_{n−d_{n}}. Dostáváme tak graf se skóre D.

“⇒”

Předpokládáme, že G = ({v_{1}, …, v_{n}}, E) má skóre D. Označme d = d_{n} = degv_{n}. První případ: Z v_{n} vedou hrany do vrcholů v_{n−1}, v_{n−2}, …, v_{n−d}. Odstraněním

v_{n} pak z těchto hran dostaneme graf se skóre D′.

Druhý případ: Neplatí první případ, tedy potom je vrchol v_{n} propojen s jinými vrcholy, než je posledních d_{n}, neboli:

i < n − d ≤ j : {v_{i}, v_{n}} ∈ E, {v_{j}, v_{n}} ∉ E

Ale protože degv_{i} (= d_{i}) ≤ degv_{j} (= d_{j}), existuje v_{k} (k ≠ i, j) takový, že {v_{j}, v_{k}} ∈ E, {v_{i}, v_{k}} ∉ E (tedy existuje zase nějaký vrchol v_{k} takový, který je spojený s v_{j}, ale ne v_{k} a tím se stupeň kompenzuje).

Přidáme do E hrany {v_{i}, v_{k}}, {v_{j}, v_{n}}, odebereme z E hrany {v_{i}, v_{n}}, {v_{j}, v_{k}}. Skóre tak zůstává D, ale zmizela neposedná hrana mimo posledních d_{n} prvků (vrcholy v_{i}, v_{j} jsme místo přes v_{n} spojili přes v_{k}). Převedli jsme tedy situaci na první případ.

Q.E.D.

Grafy — Kreslení grafu jedním tahem Pavel Valtr — Diskrétní matematika

Kreslení grafu jedním tahem

Sled: v_{0}, e_{1}, v_{1}, e_{2}, …, e_{n}, v_{n}; e_{i} = {v_{i−1}, v_{i}} Tah: Sled, e_{i} ≠ e_{j} (pro i ≠ j) Uzavřený tah: Tah, v_{0} = v_{m} “Cesta”: Tah, v_{i} ≠ v_{j}

Eulerovský graf

G = (V, E) je Eulerovský (lze nakreslit jedním uzavřeným tahem), pokud existuje uzavřený tah v_{0}, e_{1}, …, e_{m}, v_{m} takový, že:

∀e ∈ E ∃! i : e = e_{i} ∧ ∀v ∈ V ∃ i : v = v_{i}

VĚTA ():

G je eulerovský graf, právě když je G souvislý a všechny stupně jsou sudé.

DŮKAZ:

“⇒”

Uzavřený eulerovský tah dává souvislost (mezi každými 2 vrcholy existuje tah, tedy i sled) i sudé stupně (degv = 2|{i ∈ {1, …, m} : v = v_{i}}|).

“⇐”

Pozorování: Pokud jsou všechny stupně sudé, každou hranou vede uzavřený tah.

Důkaz: Nejdelší tah danou hranou je nutně uzavřený. Q.E.D. G = (V, E) souvislý, všechny stupně sudé. Ukážeme (sporem), že nejdelší

uzavřený tah T v G je eulerovský.

Co by bylo, kdyby nebyl: Ze souvislosti víme, že existuje v ∈ V (T), e ∈ E \ E(T), v ∈ e. V grafu G′ = (V, E \ E(T)) jsou všechny stupně sudé, tedy v G′ existuje uzavřený tah T′, obsahující e.

Ve vrcholu v propojíme T, T′ do jednoho tahu. Schematicky: T-O-D-O: Fig. D0

⇒ nový delší tah, ale T měl být nejdelší! ♯̸ Spor Pavel Valtr — Diskrétní matematika Grafy — Operace (lokální úpravy) na grafech

Operace (lokální úpravy) na grafech

Definujeme si G = (V, E).

(i) Odebrání hrany e ∈ E: G → G − e = (V, E \ {e}). (ii) Přidání hrany e ∈ \binom{V}{2} \ E: G → G + e = (V, E ∪ \{e\}). (iii) Odebrání vrcholu v ∈ V: G → G − v = (V \ {u}, {e ∈ E, v ∉ e}). (iv) Dělení hrany e = {x, y} ∈ E:

G → G % e = (V ∪ {z}, (E \ {e}) ∪ {{x, z}, {y, z}})

G′ je dělení grafu G, pokud: G′ dostaneme z G postupným opakováním operace dělení hrany. Ekvivalentně — G′ dostaneme z G nahrazením hran cestami délek ≥ 1.

Příklad:

o ------ o o ----- o

— “ — “

— “ ---¿ o o

—  “  —  “
o  o  o  o

Grafy — 2–souvislost Pavel Valtr — Diskrétní matematika

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:

“⇒”

Pavel Valtr — Diskrétní matematika Grafy — 2–souvislost

△ 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).

Grafy — Stromy Pavel Valtr — Diskrétní matematika

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 Pavel Valtr — Diskrétní matematika Grafy — Stromy

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 Grafy — Minimální kostra grafu Pavel Valtr — Diskrétní matematika

Minimální kostra grafu

Kostra grafu

Kostra souvislého grafu G = (V, E) je libovolný strom T = (V, E′), kde E′ ≤ E.

Poznámka:

Každý souvislý graf má kostru: dokud v G existuje kružnice, odebíráme z G hranu kružnice, dostaneme tak nakonec kostru grafu.

Příklad:

Prasátko. (Na onom grafu se vysvětluje i minimální kostra.)

Graf s ohodnocenými hranami: G = (V, E), w: E → ℝ^{+} .

Problém minimální kostry:

Pro daný souvislý graf G = (V, E), w: E → ℝ^{+} máme nalézt minimální kostru, tj. kostru K = (V, E′) takovou, že její váha w(K) = w(E′) = ∑_{e∈E′} w(e) je minimální.

Kruskulův (hladový) algoritmus

Mějme souvislý G = (V, E), w: E → ℝ^{+} . Předpokládejme, že E = {e_{1}, e_{2}, …, e_{m}}, přičemž

w(e_{1}) ≤ w(e_{2}) ≤ ⋯ ≤ w(e_{m})

1. E_{0} = ∅

2. Pro i = 1, 2, …, m pokládáme

E_{i} = \{ \begin{matrix}E_{i−1} ∪ \{e_{i}\} & pokud (V, E_{i−1} ∪ \{e_{i}\}) nemá kružnici \\ E_{i−1} & jinak \end{matrix}

3. (V, E_{m}) → výstup (minimální kostra)

VĚTA (kostra nalezená algoritmem je minimální):

DŮKAZ:

(V, K) nechť je výsledná kostra. Budiž (V, L) libovolná jiná kostra, pak chceme w(L) ≥ w(K). Indukcí podle \underbrace{d = |KΔL| = |(K \ L) ∪ (L \ K)|}_{mohutnost symetrické diference} :

(d = 0) K = L, platí

(d > 0) Předpokládáme, že tvrzení platí pro všechny menší hodnoty d.

d > 0 ⟹ K ≠ L, |K| = |L| ⟹ ∃ e ∈ L \ K

(V, L \ {e}) pak má dvě komponenty (graf s hranou byl strom). Obrázek. (V, K) kostra ⟹ (V, K ∪ {e}) má (jedinou) kružnici C obsahující e. Exi-

stuje e′ ≠ e ∈ C:

\begin{aligned}|e′ ∩ V_{1}| & = 1 \\ |e′ ∪ V_{2}| & = 1 \end{aligned}

Tvrdíme:

w(e′) ≤ w(e)

(jinak w(e) < w(e′), algoritmus tedy uvažoval e dříve než e′, ovšem pokud ho nezařadil, mohl ho odmítnout jedině kvůli C (to je jediná kružnice v K ∪ e), ale e′ ∈ C nebylo ještě uvažováno).

Pavel Valtr — Diskrétní matematika Grafy — Minimální kostra grafu

L′ = (L \ {e}) ∪ {e′}

Tvrdíme, že (V, L′) je kostra. (Viz náš virtuální obrázek. Měli jsme dvě komponenty spojené hranou e, teď je jen spojíme místo toho jinou hranou e′.)

|L′ΔK| < |LΔK|
w(L) ≥ w(L′) ≥^{ind. předp.} w(K)

Q.E.D.

Jarníkův algoritmus na minimální kostru

1. V_{0} := {v}, kde v je libovolný vrchol z V.

2. Pro i = 1, 2, …, n − 1 (n = |V |) nechť e_{i} je hrana minimální váhy vedoucí z V_{i−1} do V \ V_{i−1}. Obrázek. V_{i} = V_{i−1} ∪ e_{i} (přidáme koncový vrchol hrany e_{i}).

3. s trom(V, {e_{1}, …, e_{n−1}}) je výstup (minimální kostra grafu).

Borůvkův algoritmus

Předpokládáme, že libovolné dvě hrany mají různou váhu: w(e) ≠ w(e′) ∀e ≠ e′.

1. Spojíme každý vrchol hranou s nejbližším sousedem: (obrázek).

2. Spojme každou komponentu hranou s nejbližší jinou komponentou: (obrázek). Opakujeme, dokud nedostaneme jednu komponentu — to je výstup.

Grafy — Rovinné grafy Pavel Valtr — Diskrétní matematika

Rovinné grafy

Oblouk: Množina bodů {γ(x) : x ∈ [0, 1]}, přičemž γ: [0, 1] → ℝ^{2} (rovina) je prosté a spojité zobrazení.

Definice:

Graf G = (V, E) je rovinný, má-li rovinné nakreslení: Vrcholy odpovídají různým bodům v ℝ^{2}, hrany odpovídají obloukům spojujícím příslušné

dvojice vrcholů tak, že mají-li dva oblouky společný bod, potom je tento bod pro oba oblouky koncový.

Příklady:

(i) K_{4} je rovinný (ii) C_{n} je rovinná (iii) Libovolný strom

Je známo: Každý rovinný graf má rovinné nakreslení, v němž hrany odpovídají úsečkám. (Důkaz těžký.)

Definice:

Stěny rovinného nakreslení: Maximální souvislé oblasti množiny ℝ^{2}\X, kde X je množina bodů ležících na obloucích nakreslení. (Souvislost bereme intuitivně.)

Příklad:

Vezmeme-li K_{4}, pak stěny jsou vlastně všechny oblasti mezi úsečkami i kolem celého grafu (má tedy 4 stěny).

Vnější stěna: Jedna neomezená stěna, která existuje pro každý rovinný graf. Vnitřní stěny: Ostatní stěny.

Definice:

Topologická kružnice: Uzavřený “oblouk” (tj. γ(0) = γ(1)).

Příklad:

Obrázky. (Šneci a měňavky. ;-)

VĚTA (Jordanova věta o kružnici):

Libovolná topologická kružnice rozděluje rovinu na dvě souvislé oblasti (vnitřek a vnějšek dané kružnice).

(Důkaz těžký.)

VĚTA (Nerovinnost K_{5}):

Graf K_{5} není rovinný.

DŮKAZ:

Sporem. Nechť V = {1, 2, 3, 4, 5}. Obrázek: vezměme si vrcholy 1, 2, 3 a hrany mezi nimi. Ty vytvoří topologickou kružnici K.

(a) v_{4} leží uvnitř K: Pak ho umístíme do středu, ale pak kam s vrcholem V_{5}? Žádná stěna nemá na hranici všechny vrcholy 1, 2, 3, 4.

(b) v_{4} leží vně K: Můžeme převést na isomorfní graf s v_{4} uvnitř.

Pavel Valtr — Diskrétní matematika Grafy — Rovinné grafy

Q.E.D.

VĚTA (Nerovinnost K_{3,3}):

Graf K_{3,3} (úplný bipartitní graf o 3 + 3 vrcholech) není rovinný.

DŮKAZ:

V = {1, 2, 3, 1′, 2′, 3′} Spousta obrázků.

o 1 / “ / 3 “ 2’ o - -o- - o 1’ “ / “ / o 2

Kam s 3′? Q.E.D.

Pozorování:

G rovinný ⇔ každé dělení G je rovinné.

DŮKAZ:

Obrázkem K_{4}. Libovolně rozdělíme hrany, ale tím se nám nijak nezmění rovinnost.

VĚTA (Kuratowski):

G je rovinný ⇔ G neobsahuje dělení K_{5} ani dělení K_{3,3}.

DŮKAZ:

“⇒”

Zřejmá.

“⇐”

Těžká.

Q.E.D.

Eulerův vztah

G souvislý rovinný graf, |V | ≥ 1, s = počet stěn nějakého rovinného nakreslení G. Potom

|V | − |E| + s = 2

(Tudíž počet stěn nezávisí na volbě nakreslení.)

DŮKAZ:

Indukcí podle |E|:

(1) |E| = 0: s = 1, |V | = 1 (kvůli souvislosti), 1 − 0 + 1 = 2.

(2) |E| ≥ 1:

(a) G neobsahuje kružnici: G je strom. Tedy |V | = |E| + 1, s = 1, tedy platí.

(b) G obsahuje kružnici C:

e buď libovolná hrana na C. G−e splňuje Eulerův vztah (indukční předpoklad), má o hranu a stěnu méně, tedy G splňuje Eulerův vztah.

Q.E.D.

Tvrzení:

G buď rovinný, 2-souvislý. Pak hranice libovolné stěny v libovolném nakreslení G odpovídá kružnici v G.

Příklad:

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

Ale ne:

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

— o-o — — — “

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

DŮKAZ:

Stačí ukázat, že tvrzení:

(i) platí pro trojúhelník (ii) nepřestane platit podrozdělením nebo přidáním hrany Jednoduše z obrázku.

Tvrzení:

G = (V, E) rovinný graf, |V | ≥ 3. Potom:

(i) |E| ≤ 3|V | − 6 (ii) G neobsahuje Δ ⇒ |E| ≤ 2|V | − 4

DŮKAZ:

(i) Přidáváme hrany, dokud nedostaneme nějaký maximální rovinný graf, pro který platí, že po přidání jakékoliv hrany do něj již získáme graf, který není rovinný. Takový graf určitě bude 2-souvislý. Souvislý bude, poněvadž kdyby měl více komponent, určitě bychom mohli přidat

nějakou hranu, kterou komponenty spojíme, a tím by nebyla narušena rovinnost.

2-souvislý bude, jinak můžeme přidat hranu, která podruhé spojí nějaké dvě komponenty.

Každá stěna odpovídá kružnici, dokonce trojúhelníku: (obrázek) — každou kružnici můžeme rozkouskovat na trojúhelníky tak, že stále budeme mít rovinné zobrazení.

Počet incidentních dvojic hrana—stěna = 3s = 2|E|:

3s = 2|E|

3|E| = 3|V | + 3s − 6  (Eulerův vzorec)
|E| = 3|V | − 6

To platí pro každý maximální rovinný graf (rovinná triangulace). (ii)

Pozor!

Tento důkaz nefunguje — proti (a) lze najít triviální protipříklad. Opravy budu konzultovat s doc. Valtrem (asi půjde o moji chybu při přepisování), pokud potřebujete tvrzení umět dokázat teď, zkuste vymyslet důkaz (bez záruky!), jehož idea je:

Využijme (i) — to platí pro maximálně pro triangulovaný graf, odstraňme z něj tedy trojúhelníky. Trojúhelníků je právě tolik co stěn, tedy 2/3|E|. Vyberme z množiny stěn disjunktní dvojice sousedních trojúhelníků a ty spojme — tím, že odstraníme hrany, které je rozdělují. Zbyde nám polovina stěn, žádná z nich nebude trojúhelník (a rozmysleme si, že každý hustší graf už trojúhelník obsahuje). Polovina znamená 1/3|E|, odebrali jsme tedy třetinu stěn. To je dle (i) |V | − 2, tedy pro náš nový graf bez trojúhelníků |E| ≤ 2|V | − 4. Q.E.D.

Připomínám, že toto je pouze idea, a to bez záruky. Také tento důkaz není proveden dvojím počítáním. Hodí se tedy zejména pro nouzové případy, kdy nevíte, kudy kam ;-).

Následuje původní (rozbitý) důkaz:

(a) Výsledný graf není 2-souvislý: pak to musí být hvězda.

Pokud můžeme přidat hranu, byl nesouvislý a spojili jsme dvě komponenty, tím trojúhelník určitě nevytvoříme. Pokud byl souvislý (ale ne 2-souvislý), každá hrana již nutně vytváří trojúhelník (nevytváří!).

Hvězda:

|E| = |V | − 1 ≤ 2|V | − 4

(b) Výsledný graf je 2-souvislý.

Každá stěna je ohraničena kružnicí délky ≥ 4 Počet incidenčních dvojic hrana— stěna = 2|E| ≥ 4s:

2s ≤ |E|
2|E| = 2|V | + 2s − 4
|E| ≤ 2|V | − 4

Důsledky

(1) K_{5} ani K_{3,3} nejsou rovinné.

K_{5} : z(i) = 10 ≰ 3 · 5 − 6

K_{3,3} : z(i) = 9 ≰ 2 · 6 − 4

(2) Každý rovinný graf má alespoň jeden vrchol stupně nejvýše 5. Sporem: Kdyby všechny vrcholy byly stupně alespoň 6 ⇒

2|E| = ∑_{v∈V} degv ≥ 6|V |

(spor s (i)).

Grafy — Barvení map a grafů Pavel Valtr — Diskrétní matematika

Barvení map a grafů

Politická mapa (obrázek). Tři barvy obecně nestačí.

Předpoklady

(1) Každý stát je souvislý.

(2) Státy sousedící pouze v jednotlivých bodech nebudeme považovat za sousední.

Problém čtyř barev

Stačí čtyři barvy na obarvení libovolné politické mapy? Ano, ale důkaz je extrémně těžký.

Definice:

G = (V, E) lze (řádně) obarvit k barvami, pokud existuje zobrazení b: V → {1, 2, …, k} takové, že {x, y} ∈ E ⇒ b(x) ≠ b(y).

Definice:

Barevnost grafu G = χ(G) = min{k : G lze obarvit k barvami }.

Příklady:

(i) χ(C_{2k}) = 2 (ii) χ(C_{2k+1} ) = 3 (iii) χ(K_{n}) = n (iv) χ(K_{m,n}) = 2 (m, n ≥ 1)

(v) χ(T) = 2 (T strom na ≥ 2 vrcholech)

Vztah mezi barvením map a rovinných grafů

(náznak) V každém státě vybereme za vrchol hlavní město, pospojujeme hranami hlavní města soused-

ních států, jistě to lze udělat tak, že graf, který dostaneme, je rovinný. Řekneme, že mapa je k-obarvitelná ⇔ rovinný graf je k-obarvitelný.

Problém čtyř barev II.

Jiná formulace: χ(G) ≤ 4 pro každý rovinný graf G?

VĚTA (o pěti barvách):

χ(G) ≤ 5 pro každý rovinný graf G = (V, E).

DŮKAZ:

Indukcí podle |V |:

(1) |V | ≤ 5: zřejmé.

(2) |G| rovinný, |V | ≥ 6 a předpokládáme, že věta platí pro rovinné grafy s menším počtem vrcholů. G má vrchol x, degx ≤ 5 (Eulerův vztah).

(a) degx ≤ 4: Obarvíme G − x pěti barvami podle indukčního předpokladu, poté dobarvíme x barvou, která se nevyskytuje na jeho sousedech.

Pavel Valtr — Diskrétní matematika Grafy — Barvení map a grafů

(b) degx = 5: Nechť sousedé jsou označeni u_{1}, …, u_{5}. G je rovinný, tudíž neobsahuje podgraf K_{5} — to ale znamená, že nemůžou být všichni sousedé vzájemně pospojováni hranami. Bez újmy na obecnosti nechť např. {u_{4}, u_{5}} ∉ E.

* u2 * u5 “ / x * -- * u3 / “

* u4 * u1

V grafu G − x ztotožníme u_{4} a u_{5} (tím nám nevznikne žádné křížení):

* u2 —˙ ˙ // u * * u3 //

˜˜ — * u1

Podle indukčního předpokladu existuje obarvení b_{0} pěti barvami. Obarvení G − x pak můžeme definovat jako:

b(v) := b_{0}(v) v ≠ u_{4}, u_{5}
b(u_{4}) = b(u_{5}) := b_{0}(u)

Dobavíme vrchol x barvou různou od b(u_{1}), b(u_{2}), b(u_{3}), b(u_{4}) = b(u_{5}).

Q.E.D. Pozor: Důkaz neprobíhá tak, že vezmu rovinný graf a přidám vrchol. Naopak vezmu

libovolný graf, o kterém pouze vím, že libovolný menší graf je rovinný.

Alternativní důkaz:

Indukcí podle |V |:

(1) |V | ≤ 5: zřejmé.

(2) |V | ≥ 6: Nechť v je vrchol nejmenšího stupně. Dle Eulerova formule ⇒ degv ≤ 5. G − v lze obarvit pěti barvami (dle ind. předpokladu).

* a * c “ / v * -- * b / “

* e * d

Vrchol v vyhodíme:

* a * c

* b

* e * d

Bez újmy na obecnosti: a, b, c, d, e mají různou barvu.

f(a) = modrá
f(b) = červená
f(c) = žlutá
f(d) = zelená

Neexistuje žluto–zelená cesta z c do d nebo neexistuje modro–červená cesta z a do b.

Pokud by existovaly, musely by se křížit — buď mimo vrchol (to nesmějí) nebo ve vrcholu (ale jak ho pak obarvit?).

Bez újmy na obecnosti nechť neexistuje cesta c ∼ d. Přebarvíme barvy v žluto–zelené komponentě obsahující d (prohodíme žlutou a ze-

lenou). I toto obarvení je korektní, neboť komponenta je maximální a její sousedé mají všichni jiné barvy.

Teď má ale c a d stejnou barvu, takže v můžeme obarvit barvou nevyskytující se na sousedech.

⟨písnička⟩ Q.E.D.

Pavel Valtr — Diskrétní matematika Grafy — Počítání dvěma způsoby

Počítání dvěma způsoby

Princip sudosti

∀G = (V, E) : ∑_{v∈V} degv = 2|E|

DŮKAZ:

Dvojím způsobem spočítáme počet dvojic (v, e), kde v ∈ V, e ∈ E, v ∈ e. — jednou podle vrcholů a pak podle hran.

∑_{v∈V} degv = \underbrace{∑_{e∈E} 2}_{2|E|}

Q.E.D.

Nezávislý systém množin

Definice:

Mějme množinu X, M ⊆ P (x) nazýváme nezávislý systém množin, pokud

∀A, B ∈ M : A ≠ B ⇒ A ⊄ B

VĚTA (Spernerova):

X buď množina velikosti n. Potom maximální velikost nezávislého systému množin 𝕄 ⊆ P (x) je rovna \binom{n}{⌊\frac{n}{2}⌋} (např. v Pascalově △ je to v řádku, jehož součet je 2^{n}, největší číslo).

Příklady:

(i) n = 3:

\begin{aligned}X & = \{1, 2, 3\} \\ M_{1} & = \{\{1, 2\}, \{1, 3\}, \{2, 3\}\} \\ M_{2} & = \{\{1\}, \{2\}, \{3\}\} \end{aligned}

jsou nezávislé systémy množin velikosti

\binom{3}{1} = 3

(ii) obecné n:

M := množina ⌊n/2⌋ -prvkových podmnožin množiny X = {1, 2, …, n}. Pak M bude nezávislý systém velikosti \binom{n}{⌊n/2⌋}.

DŮKAZ:

(1) Maximální velikost ≥ \binom{n}{⌊\frac{n}{2}⌋}: z předchozího příkladu.
(2) Maximální velikost ≤ \binom{n}{⌊\frac{n}{2}⌋}:

X, M podle předpokladů.

Maximální řetězec: R = \{0, \{x_{1}\}, \{x_{1}, x_{2}\}, …, \underbrace{\{x_{1}, x_{2}, …, x_{n}\}}_{X}\} kde x_{1}, …,

x_{n} je libovolná permutace prvků X. Maximálních řetězců je n!, navíc kdykoliv si Grafy — Počítání dvěma způsoby Pavel Valtr — Diskrétní matematika

vezmeme libovolné dvě množiny z maximálního řetězce, jedna bude vždy podmnožinou druhé.

Spočítáme dvěma způsoby počet dvojic (R, M) takových, že M ∈ R. R buď maximální řetězec, M pak množina z M.

Tento počet je:

(a) ≤ (#maximálních řetězců) = n! Kdyby do jednoho R patřily dvě M, nepatřily by obě do nezávislého systému množin.

(b) = ∑_{M∈M} \underbrace{|M|!(n − |M|)!}_{# max. řetězců obsahujících M}.

Tedy:

n! ≥ ∑_{M∈M} |M|!(n − |M|)!

1 ≥ ∑_{M∈M} \frac{|M|!(n − |M|)!}{n!} = ∑_{M∈M} \frac{1}{\binom{n}{|M|}} ≥ ∑_{M∈M} \frac{1}{\binom{n}{⌊\frac{n}{2}⌋}} = |M|\frac{1}{\binom{n}{⌊\frac{n}{2}⌋}}

|M| ≤ \binom{n}{⌊\frac{n}{2}⌋}

Q.E.D.

Grafy bez K_{2,2} (C_{4})

VĚTA (o počtu hran na n vrcholech):

Nechť G = (V, E) je graf na n vrcholech neobsahující K_{2,2}. Potom

|E| ≤ \frac{n\sqrt{n} + n}{2}

DŮKAZ:

Využijeme Cauchy-Schwarzovu nerovnost:

∑_{i=1}^{n}x_{i}y_{i} ≤ \sqrt{∑_{i=1}^{n}x_{i}^{2}} · \sqrt{∑_{i=1}^{n}y_{i}^{2}}

pro libovolné x_{1}, …, x_{n}, y_{1}, …, y_{n} ∈ ℝ. Počítáme dvěma způsoby počet podgrafů (cest) u - v - u’. Tento počet je:

(a) ≤ \binom{n}{2}: pro ∀u, u′ ∈ V, u ≠ u′ existuje nejvýše jeden v ∈ V takový, že {u, v}, {u′, v} ∈ E — jinak dostaneme K_{2,2}:

*-* u X *-* u’

(b) = ∑_{v∈V} \binom{deg v}{2}: pro ∀v ∈ V máme právě \binom{deg v}{2} vidliček * - v - *.

Pavel Valtr — Diskrétní matematika Grafy — Počítání dvěma způsoby

Tedy:

∑_{n∈V} \binom{degv}{2} ≤  \binom{n}{2}  ≤ \frac{1}{2}n^{2}
\frac{1}{2} ∑_{n∈V}((degv) − 1)^{2} ≤  ∑_{v∈V} \binom{degv}{2}  ≤ \frac{1}{2}n^{2}
\underbrace{∑_{v∈V}((degv) − 1) · 1}_{2|E|−n} ≤ \underbrace{\sqrt{∑_{v∈V}((degv) − 1)^{2}}}_{≤\sqrt{n^{2}}}· \underbrace{\sqrt{∑_{v∈V} 1^{2}}}_{\sqrt{n}} ≤n\sqrt{n}

|E| ≤ \frac{1}{2}(n\sqrt{n} + n)

Q.E.D.

Grafy — Orientované grafy Pavel Valtr — Diskrétní matematika

Orientované grafy

Orientovaný graf: \overrightarrow{G} = (V, \overrightarrow{E}), kde V je libovolná konečná množina a \overrightarrow{E} ⊆ V × V.

Definice:

deg^{+} v = vstupní stupeň v = počet hran vedoucích do v. deg^{−} v = výstupní stupeň v = počet hran vedoucích z v.

Příklad:

\overrightarrow{G} = (\{a, b, c\}, \{(a, b), (b, b), (a, c), (c, a)\})

¡“ ˙ *-/ /— b

/ a /

* -----¿ * c ¡-----

deg^{+} a = 1  deg^{+} b = 2
deg^{−} a = 2  deg^{−} b = 1

Definice:

\overrightarrow{G} je slabě souvislý, pokud ∀x, y ∈ V existuje (neorientovaná) cesta z x do y.

x• → • ← • → • ← •y

\overrightarrow{G} je slabě souvislý, pokud ∀x, y ∈ V existuje orientovaná cesta z x do y.

x• → • → • → • → •y

Definice:

Orientovaný graf \overrightarrow{G} je eulerovský, pokud lze nakreslit jedním uzavřeným orientovaným tahem.

⋯ → • → • → ⋯

VĚTA (podmínka eulerovského grafu):

\overrightarrow{G} = (V, \overrightarrow{E}) je eulerovský ⟺ \overrightarrow{G} je slabě souvislý a \underbrace{∀v ∈ V : deg^{+} v = deg^{−} v}_{(∗)}.

DŮKAZ:

“⇒”

Zřejmé.

“⇐”

LEMMA: Každou hranou grafu splňujícího (∗) vede uzavřený orientovaný tah.

Pavel Valtr — Diskrétní matematika Grafy — Orientované grafy

DŮKAZ:

Nejdelší orientovaný tah danou hranou je uzavřený. Když ho totiž vedeme, postupně umazáváme hrany a nakonec nám podle rovnosti v (∗) zbyde jen poslední hrana, která vede do v.

Q.E.D.

Nejdelší uzavřený orientovaný tah v \overrightarrow{G} je eulerovský. Jinak (obdobně jako v neorientovaném případě, schematicky):

/¡-“

— * nejdelší uzavřený orientovaný tah “-¿/

Po použití lemmatu a odstranění hran tahu bychom však našli ještě další jiný uzavřený orientovaný tah, díky souvislosti má alespoň jeden společný vrchol. Pak ale můžeme oba tahy propojit do jednoho delšího uzavřeného tahu.

♯̸ Spor Grafy — Počet koster K_{n} Pavel Valtr — Diskrétní matematika

Počet koster K_{n}

VĚTA (Cayleyho formule):

∀n ≥ 2: počet koster grafu K_{n} je n^{n−2} (tedy počet stromů na {1, …, n}).

Příklad:

n = 2: {• \atop 1} − {• \atop 2}

2^{0} = 1 kostra. n = 3: {• \atop 1} − {• \atop 2} − {• \atop 3}, {• \atop 2} − {• \atop 1} − {• \atop 3}, {• \atop 1} − {• \atop 3} − {• \atop 2}

3^{1} = 3 kostry. n = 4: 12 koster typu housenka, 4 kostry typu vějíř.

DŮKAZ:

Slunce: Strom, v němž všechny hrany jsou zorientovány směrem od jediného vrcholu (středu slunce).

Pozorování 1:

Počet stromů na {1, …, n} je roven

\frac{počtu sluncí na \{1, …, n\}}{n}

DŮKAZ:

Každý strom odpovídá n sluncím (máme v každém stromu n možností volby středu). Q.E.D.

Sousluní: Orientovaný graf, kde každá komponenta je slunce.

Pozorování 2:

Po odstranění libovolných k hran ze slunce dostaneme sousluní s k+1 komponentami (slunci).

DŮKAZ:

Zřejmý z obrázku. Vyhozením hrany ze slunce se slunce rozpadne na 2 další slunce. Q.E.D.

Pozorování 3:

Přidáním orientované hrany do sousluní dostaneme opěr sousluní, právě když přidaná hrana vede do středu libovolné jiné komponenty (slunce).

DŮKAZ:

Z obrázku.

Důkaz věty:

Z grafu izolovaných vrcholů 1,…,n dostaneme slunce na {1, …, n} postupným přidáváním n − 1 orientovaných hran právě, když přidaná hrana vždy vede z libovolného vrcholu do středu jiné komponenty.

Máme n(n − 1) možností volby první hrany. Možností volby druhé hrany máme n(n − 2). Pro třetí hranu máme n(n − 3) možností. … Pro (n − 1). hranu máme n · 1 možností.

Celkem máme n^{n−1}(n − 1)! možností, jak zvolit 1. až (n − 1). hranu. Každé slunce dostaneme (n − 1)!-krát. Sluncí tedy dostaneme n^{n−1} a stromů tak bude n^{n−2}.

Q.E.D.