DM2-Skripta

! "# $% &''()&''*

“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 —

+,-./012 34567

89:;<9=

Množina: soubor prvků.

>?@ABC

• výčtem prvků: X = {a, b, c}
• vlastností: X = {i ∈ N : ∃ j ∈ N, 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 |, . . .

DEFGHE

Neuspořádaná dvojice: {x, y}

Uspořádaná dvojice: (x, y): (x, y) = (x0, y0) ⇔ (x = x0 ∧ y = y0); 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) ∈ R: xRy (jde-li o binární relaci)

IJKLAMJC

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í

NOPQR JSTATUVJLMJ

Určené prvkem x:

R[x] =

{y ∈ X, xRy}

(díky symetrii platí i yRx).

WOPSVUQC

X =

{1, 2, 3, 4}

R =

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

R[1] =

{1}

R[2] = R[4] =

{2, 4}

NTXYJLPC

(i) x ∈ R[x]

∀x ∈ X

(ii) R[x] = R[y] ∨ R[x] ∩ R[y] = ∅

∀x, y ∈ X

1

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] 6= ∅. Mějme libovolné z ∈ R[x] ∩ R[y]. Pak jistě

xRz

∧ zRy

tranz.

⇒ xRy. 6 ] Spor

R[x]

∩ R[y] = ∅

IZBVJQJSC

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.

[\]:^_`_9a

(Čá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: (N, ą), (N, | ) (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.

b:cdGeE9a

IJKLAMJC

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 7→ y, f(x) = y

IJKLAMJC

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

WfYL?gSUC

g

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

(g ◦ f)(x) = g(f(x)

| {z }

∃! y

) = g(y)

|{z}

∃! z

= z

IJKLAMJC

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

2

Pavel Valtr — Diskrétní matematika

Základní pojmy — Zobrazení

• prosté (injekce f: X ↔ Y ), pokud x 6= y ⇒ f(x) 6= 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 R”.

3

Kombinatorika —

Pavel Valtr — Diskrétní matematika

h46ij1/k4lj-/

mEdnopGHE G qGrp:d<_F

Permutace konečné množiny X: Libovolná bijekce π: X

1–1

←→ X.

WOPSVUQC

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

π(d) = a. Matice permutace pak je

µ

a

b

c

d

b

d c

a

¶

,

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

NTXYJLPC

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 6= n.

s:nc<9Gt9a ta\FG

IJKLAMJC

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

µn

k

¶

=

n!

k!(n

− k)!

=

n(n

− 1) . . . (n − k + 1)

k(k

− 1) . . . 1

n, k

∈ N0, n ≥ k

uVvJXLUvATLP QJKLAMJC

4

Pavel Valtr — Diskrétní matematika

Kombinatorika — Kombinační čísla

µn

k

¶

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

NTXYJLPC

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) =

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í) =

µ|X|

k

¶

k! =

n!

(n − k)!

.

Q.E.D.

>LUwJLPC

Buď X množina. Pak

µX

k

¶

je množina všech k-prvkových podmnožin množiny X. Navíc

Ż

Ż

Ż

Ż

µX

k

¶Ż

Ż

Ż

Ż

=

µ|X|

k

¶

.

Platí:

(i) Symetrie:

µn

k

¶

=

µ

n

n

− k

¶

n

≥ k ≥ 0

DŮKAZ:

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

(ii) Sousední čísla:

µn

k

¶

=

µn − 1

k

− 1

¶

+

µn − 1

k

¶

DŮKAZ:

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

Ż

Ż

Ż

Ż

µX

k

¶Ż

Ż

Ż

Ż

=

Ż

Ż

Ż

Ż

µX \ {xn}

k

− 1

¶Ż

Ż

Ż

Ż

|

{z

}

počet

k-prvkových podm.

množiny

X obs. xn

+

Ż

Ż

Ż

Ż

µX \ {xn}

k

¶Ż

Ż

Ż

Ż

|

{z

}

počet

k-prvkových podm.

množiny

X neobs. xn

Q.E.D.

WUBMUVZT vXfxyzJVLPS

Ve vrcholu 4 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

5

Kombinatorika — Kombinační čísla

Pavel Valtr — Diskrétní matematika

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

µ0

0

¶

µ1

0

¶

µ1

1

¶

µ2

0

¶

µ2

1

¶

µ2

2

¶

µ3

0

¶

µ3

1

¶

µ3

2

¶

µ3

3

¶

µ4

0

¶

µ4

1

¶

µ4

2

¶

µ4

3

¶

µ4

4

¶

neboť

µn

k

¶

=

µn − 1

k

− 1

¶

+

µn − 1

k

¶

.

{ALfgAMS? T|vU

}PgJC

(x + y)2 = x2 + 2xy + y2
(x + y)3 = x3 + 3x2y + 3xy2 + y3

(x + y)n =

n

X

k=0

µn

k

¶

xkyn−k

n

∈ N0, x, y ∈ R

DŮKAZ:

Indukcí podle n:

(1) n = 0, n = 1

(x + y)0 =

µ0

0

¶

x0y0 = 1

(x + y)1 =

µ1

0

¶

x0y1 +

µ1

1

¶

x1y0

(2) n ⇒ n + 1

(x + y)n+1 = (x + y)n(x + y) = (x + y)

µµn

0

¶

x0yn +

· · · +

µn

n

¶

xny0

¶

=

=

µn

0

¶

x1yn +

· · · +

µn

n

¶

xn+1y0 +

µn

0

¶

x0yn+1 +

· · · +

µn

n

¶

xny1 =

=

µn + 1

0

¶

x0yn+1 +

µn + 1

1

¶

x1yn +

· · · +

µn + 1

n

¶

xny1 +

µn + 1

n + 1

¶

xn+1y0 =

=

n+1

X

k=0

µn + 1

k

¶

xky(n+1)−k

IZBVJQJSC

(1 + x)n =

n

X

k=0

µn

k

¶

xk

6

Pavel Valtr — Diskrétní matematika

Kombinatorika — Multinomická věta

8oFp<9:n<Hr_ ~pG

∀n ∈ N0, ∀m ∈ N, ∀x1, . . . , xm ∈ R :

(x1 + x2 + · · · + xm)

n =

X

k1,k2,...,km≥0

k1+k2+···+km=n

µ

n

k1, k2, . . . , km

¶

(xk1

1 x

k2

2 · · · x

km

m )

Bez důkazu.

WfYL?gSUC

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

8oFp<9:n<Hr€ r:EH<E9p

µ

n

k1, . . . , km

¶

=

n!

k1!k2!

· · · kn!

Počet způsobů zařazení čísel 1, . . . , n do m množin x1, . . . , xm tak, aby |x1| = k1, . . . , |xm| = km.

WVUvP

µn

k

¶

=

µ

n

k, n

− k

¶

WOPSVUQC

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

µ

200

80, 70, 50

¶

7

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

Pavel Valtr — Diskrétní matematika

‚`ƒG`= qGrp:d<_F„ G r:nc<9Gt9aHƒ ta\EF

…USvfXA?VR

}|vU

nn/2

≤ n! ≤

ł n + 1

2

´n

nn/2 =

ˇ

√

n

˘n

DŮKAZ:

(n!)2 = (1 · n)(2 · (n − 1)) · · · (n · 1)

|

{z

}

(n! jednou popředu a

k tomu podruhé odzadu)

(n!)2 = z1 · z2 · · · z2n

Z AG nerovnosti:

z

≤

µ 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:

(nn) ≤ (n!)

2 ≤

õ

n + 1

2

¶2!n

nn/2

≤ n! ≤

µ n + 1

2

¶n

Q.E.D.

WOJBL|xA

n!

≈

ł n

e

´n

·

√

2πn

tj. lim

n→∞

n!

ˇ n

e

˘n

·

√

2πn

= 1

Bez důkazu.

†fg‡ALUwLP wPBVU

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

}PgJ

µn

0

¶

+

µn

1

¶

+ · · · +

µn

n

¶

= 2n

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.

8

Pavel Valtr — Diskrétní matematika

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

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

µn

0

¶

<

µn

1

¶

<

· · · <

µ n

Ą n

2

¦

¶

=

µ n

§ n

2

¨

¶

>

· · · >

µn

n

¶

2n

n + 1

<

µ n

Ą n

2

¦

¶

< 2n

Přesněji:

µ n

Ą n

2

¦

¶

≈

2n

p

πn/2

Platí také:

µn

0

¶

+

µn

1

¶

+ · · · +

µn

k

¶

≤

ł e

· n

k

´k

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

9

Kombinatorika — Princip inkluze a exkluze (PIE)

Pavel Valtr — Diskrétní matematika

md<9H<] <9rFoeE G EˆrFoeE ‰mŠ‹Œ

WOPSVUQC

|A1 ∪ A2| = |A1| + |A2| − |A1 ∩ A2|

|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| − |A1 ∩ A2| − |A1 ∩ A3| − |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|

VĚTA (PIE):

Jsou-li A1, A2, . . . , An konečné množiny:

|

n

[

i=1

Ai

| =

n

X

k=1

(−1)

k+1

|

{z

}

(parita)

·

X

I∈

({1,..,n}

k

)

|

\

i∈I

Ai

|

(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 A1 ∪ A2 ∪ · · · ∪ An. 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 Ai, do kterých patří x.
Příklad:

x

∈ A1, . . . , Aj

x /

∈ Aj+1, . . . , An

Pak platí:

#x =

µj

1

¶

−

µj

2

¶

+

µj

3

¶

− · · · + (−1)

j−1

µj

j

¶

=

j

X

i=1

(−1)

i−1

µj

i

¶

+ 1 − 1

Obracíme znaménko a paritu:

= 1 −

j

X

i=0

(−1)

i

µj

i

¶

= 1 − (−1 + 1)

j

= 1

Q.E.D.

WOPSVUQC

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

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

nezobrazuje žádný prvek z X:

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

10

Pavel Valtr — Diskrétní matematika

Kombinatorika — Princip inkluze a exkluze (PIE)

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

Ai =

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

|Ai| = (l − 1)

n

Pro i1 6= i2:

Ai

1 ∩ Ai2 = {f : X → Y − {i1, i2}}

|Ai

1 ∩ Ai2 | = (l − 2)

n

Pro {i1, . . . , ik} ∈

µ{1, . . . , l}

k

¶

:

Ai

1 ∩ · · · ∩ Aik = {f : X → Y − {i1, . . . , ik }}

{Ai

1 ∩ · · · ∩ Aik } = (l − k)

n

Počet zobrazení z X na Y je:

ln

− |

l

[

i=1

Ai

| =

= ln −

õ

l

1

¶

(l − 1)

n −

µ l

2

¶

(l − 2)

n +

µ l

3

¶

(l − 3)

n − · · · +

+(−1)

l−2

µ

l

l

− 1

¶

(l − (l − 1)

n) + (−1)l−1

µl

l

¶

(l − l)

n

!

=

=

l−1

X

k=0

(−1)

k

µ l

k

¶

(l − k)

n

11

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

Pavel Valtr — Diskrétní matematika

_9:t9a cE\a`rG ‰ŽGp9_^rGŒ

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?

UvJgUvAMS? fXg‘VUMJ

Hledáme

š(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 −

1

1!

+

1

2! −

1

3!

+ · · · + (−1)

n 1

n!

¶

WOPSVUQC

š(1) = 1!

µ

1 −

1

1!

¶

= 0

š(2) = 2!

µ

1 −

1

1!

+

1

2!

¶

= 1

š(3) = 3!

µ

1 −

1

1!

+

1

2! −

1

3!

¶

= 2

DŮKAZ:

Sn = množina všech permutací

{1, . . . , n}

Ai =

{π ∈ Sn, i = 1, . . . , n : π(i) = i}

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

Pro I = {i1, . . . , ik} ⊆ {1, . . . , n} platí:

\

i∈I

Ai

| {z }

Ai

1 ∩···∩Aik

= množina vsech permutací π

množiny {1, . . . , n} takových, že π(i1) = i1, . . . , π(ik) = ik.

|

\

i∈I

Ai

| = (n − k)! (t prvků stojí, ostatní se propermutují.)

š(n) = |Sn| − |

n

[

i=1

Ai

| =

= n! −

n

X

k=1

(−1)

k−1 ·

X

I∈

({1,...,n}

k

)

|

\

i∈I

Ai

|

| {z }

(n−k)!

= n! −

n

X

k=1

(−1)

k−1 ·

µn

k

¶

(n − k)!

|

{z

}

n!

k

!

= n! ·

Ă

1 −

n

X

k=1

(−1)k−1

k!

!

12

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:

š(n)

n!

= 1 −

1

1!

+

1

2! − · · · ±

1

n!

→

1
e

≈ 0.36787 . . .

13

Grafy —

Pavel Valtr — Diskrétní matematika

’l/“7

IJKLAMJ

Graf G je uspořádaná dvojice (V, E), kde V je libovolná konečná množina (obecněji zcela

libovolná) a E ⊆

ˇV

2

˘.

Úplný graf (na n vrcholech):

Kn = (V,

µV

2

¶

)

Kružnice:

Cn = (

{v1, . . . , vn}, {{v1, v2}, {v2, v3}, . . . , {vn−1, vn}, {vn, v1}})

n

≥ 3

Cesta:

Pn = (

{v0, . . . , vn}, {{v0, v1}, {v1, v2}, . . . , {vn−1, vn}})

Sled:

v0, e1, v1, e2, . . . , em, vm, kde ei =

{vi−1, vi}. (Cesta je tedy speciální druh sledu, kde

jedním vrcholem neprojdeme vícekrát.)

”@VL• ‡A@UXvAvLP –XU

Kn,m = (V, E)

V =

{u1, . . . , un, v1, . . . , vm}

E =

{{ui, vj} : i = 1, . . . , n; j = 1, . . . , m}

|V | = n + m, |E| = n · m

WOPSVUQC

K2,3:

*-\ * /-*

\ X X /

*-^-*

{A@UXvAvLP –XU

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

V = U

.

∪ W

| {z }

V =U ∪W,

U ∩W =0

E

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

—BfgfXKBg‘B

“Přejmenování vrcholů”
G

| G0 (G, G0 jsou izomorfní), pokud existuje bijekce f: V (G)

1–1

←→ V (G0) taková, že:

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

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

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

14

Pavel Valtr — Diskrétní matematika

Grafy —

—LQ‘SfTUL• @fQ–XU

Graf G0 je indukovaným podgrafem grafu G, pokud V (G0) ⊆ V (G) a E(G0) = E(G) ∩

ˇV (G0)

2

˘.

WfYfXfT?LP

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

indukovaný podgraf).

˜f‘TABV• –XU

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.

WfYL?gSUC

G souvislý

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

†fg@fLJLvU –XU‘

G

Podgraf indukovaný třídami ekvivalence ∼G.

Pozn.: G souvislý ⇔ má jednu komponentu.

}YQ?VJLfBv T –XU‘

x, y

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

WfYL?gSUC

dG(x, y) má vlastnosti metriky (vzdálenosti):

dG(x, y)

≥ 0

dG(x, y) = 0

⇔ x = y

dG(x, y) = dG(y, x)

dG(x, y) + dG(y, z)

≥ dG(x, z)

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

Matice sousednosti:

G = (

{v1, . . . , vn}, E) : AG = (ai,j)

n

i,j=1, ai,j =

˝ 1 {v

i, vj

} ∈ E(G)

0 jinak

Stupeň vrcholu: Stupeň vrcholu x v G jest deg

G(x) = deg(x) = počet hran obsahujících x =

počet sousedů.

15

Grafy — Věta o sudosti (princip sudosti)

Pavel Valtr — Diskrétní matematika

pG : \o`:\p< ‰]d<9H<] \o`:\p<Œ

∀G = (V, E) :

X

v∈V

deg

G(v) = 2|E|

DŮKAZ:

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

IZBVJQJSC

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

WfYL?gSUC

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

o

/

\

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

™ršdE ›dGqo

G = (

{v1, . . . , vn}, E), skóre grafu G = D(G) = (degG(v1), . . . , degG(vn))

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

WOPSVUQC

o

/

\

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

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

o

/

\

o - o - o - o

k němu není izomorfní.

}|vU f BSœXJC

D = (d1, . . . , dn, 0

≤ d1 ≤ · · · ≤ dn)

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

D0 = (d1, . . . , dn−d

n

−1, dn−dn − 1, . . . , dn−2 − 1, dn−1 − 1)

je skóre nějakého grafu.

WOPSVUQR @f‘AvPC

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?

16

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:

“⇐”

G0 má skóre D0. Přidáme ke G0 nový vrchol vn a spojíme ho hranou s vrcholy vn−1,

vn−2, . . ., vn−d

n .

Dostáváme tak graf se skóre D.

“⇒”

Předpokládáme, že G = ({v1, . . . , vn}, E) má skóre D. Označme d = dn = deg vn.

První případ: Z vn vedou hrany do vrcholů vn−1, vn−2, . . . , vn−d. Odstraněním

vn pak z těchto hran dostaneme graf se skóre D0.

Druhý případ: Neplatí první případ, tedy potom je vrchol vn propojen s jinými

vrcholy, než je posledních dn, neboli:

i < n

− d ≤ j : {vi, vn} ∈ E, {vj, vn} /

∈ E

Ale protože deg vi (= di) ≤ deg vj (= dj), existuje vk (k 6= i, j) takový, že {vj, vk} ∈

E,

{vi, vk} /

∈ E (tedy existuje zase nějaký vrchol vk takový, který je spojený s vj, ale

ne vk a tím se stupeň kompenzuje).

Přidáme do E hrany {vi, vk}, {vj, vn}, odebereme z E hrany {vi, vn}, {vj, vk}. Skóre

tak zůstává D, ale zmizela neposedná hrana mimo posledních dn prvků (vrcholy vi, vj
jsme místo přes vn spojili přes vk). Převedli jsme tedy situaci na první případ.

Q.E.D.

17

Grafy — Kreslení grafu jedním tahem

Pavel Valtr — Diskrétní matematika

sdE\FE9a ›dGqo žE`9an pGƒEn

Sled: v0, e1, v1, e2, . . . , en, vn; ei = {vi−1, vi}

Tah: Sled, ei 6= ej (pro i 6= j)

Uzavřený tah: Tah, v0 = vm
“Cesta”: Tah, vi 6= vj

Ÿ‘VJXfTBS• –XU

G = (V, E) je Eulerovský (lze nakreslit jedním uzavřeným tahem), pokud existuje uzavřený

tah v0, e1, . . . , em, vm takový, že:

∀e ∈ E ∃! i : e = ei ∧ ∀v ∈ V ∃ i : v = vi

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ě (deg v = 2|{i ∈ {1, . . . , m} : v = vi}|).

“⇐”

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 G0 = (V, E \ E(T )) jsou všechny stupně sudé, tedy v

G0 existuje uzavřený tah T 0, obsahující e.

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

D0

⇒ nový delší tah, ale T měl být nejdelší!
6 ] Spor

18

Pavel Valtr — Diskrétní matematika

Grafy — Operace (lokální úpravy) na grafech

‚]EdGHE ‰F:r_F9a ]dG~=Œ 9G ›dGqEHƒ

Definujeme si G = (V, E).

(i) Odebrání hrany e ∈ E: G → G − e = (V, E \ {e}).

(ii) Přidání hrany e ∈

ˇ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}})

G0 je dělení grafu G, pokud:

G0 dostaneme z G postupným opakováním operace dělení

hrany. Ekvivalentně — G0 dostaneme z G nahrazením hran cestami délek ≥ 1.

WOPSVUQC

o ------ o

o ----- o

| \

| \

|

\

---> o

o

|

\

|

\

o

o

o

o

19

Grafy — 2–souvislost

Pavel Valtr — Diskrétní matematika

ˇ˘\:o~<\F:\p

IJKLAMJC

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

WOPSVUQC

o - o
|

> o

2--souvislý

o - o

o

o

/ \ / \

o

o

o

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

\ / \ /

o

o

WfYfXfT?LPC

G je 2–souvislý

⇒






G + e

2–souvislý pro ∀e /∈ E.

G

− e souvislý pro ∀e ∈ E.

G % e

2–souvislý pro ∀e ∈ E.

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 6= x, y.

G

− y souvislý ⇒ x je v G − e v jedné komponentě se všemi vrcholy v 6= x, y.

Tedy G − e má určitě jednu komponentu, takže je souvislý.

(c)

e

x ----- y

-->

x - z - y

.

G

G’

G0

− v souvislý ∀v 6= z. G0 − z = G − e souvislý podle (b).

Q.E.D.

IJKLAMJC

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 K3 = 4 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:

“⇒”

20

Pavel Valtr — Diskrétní matematika

Grafy — 2–souvislost

4 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 4. 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 (G0) \ 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.

WfYL?gSUC

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

21

Grafy — Stromy

Pavel Valtr — Diskrétní matematika

™pd:n=

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ý.

WfYfXfT?LPC

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 K1 = • 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 ∈

ˇ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

22

Pavel Valtr — Diskrétní matematika

Grafy — Stromy

Předpokládám P1, P2 různé cesty z x do y:

P1 = xe1v1e2v2

· · · y

P2 = xe01v01e02v02 · · · y

Nechť i je minimální, pro které platí ei 6= e0i.

Nechť j ≥ i je minimální, pro které ∃ k takové, že v0j = vk.

Pak vi−1 = v0i−1, v0i, . . . , v0j = vk, vk−1, . . . , vi tvoří kružnici.

6 ] 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 K1 = •, 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 opaku-
jeme, až dostaneme graf G0 = (V, E0) souvislý bez kružnic (tedy strom |V | = |E0| + 1),
|E0| < |E|. Ale předpoklad zněl, že |V | = |E| + 1.

6 ] Spor

23

Grafy — Minimální kostra grafu

Pavel Valtr — Diskrétní matematika

8<9<n_F9a r:\pdG ›dGqo

†fBvXU –XU‘

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

WfYL?gSUC

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.

WOPSVUQC

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

Graf s ohodnocenými hranami: G = (V, E), w: E → R+.

WXf‡VŁg gALAg?VLP SfBvXRC

Pro daný souvislý graf G = (V, E), w: E → R+ máme nalézt minimální kostru, tj. kostru

K = (V, E0) takovou, že její váha w(K) = w(E0) =

P

e∈E0 w(e) je minimální.

†X‘BS‘VZT ¤zVUQfT•Ą UV–fXAvg‘B

Mějme souvislý G = (V, E), w: E → R+. Předpokládejme, že E = {e1, e2, . . . , em},

přičemž

w(e1)

≤ w(e2) ≤ · · · ≤ w(em)

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

Ei =

˝

Ei−1 ∪ {ei} pokud (V, Ei−1 ∪ {ei}) nemá kružnici
Ei−1

jinak

3. (V, Em) → 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 d = |K∆L| = |(K \ L) ∪ (L \ K)|

|

{z

}

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 6= 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 e0 6= e ∈ C:

|e0 ∩ V1| = 1
|e0 ∪ V2| = 1

Tvrdíme:

w(e0)

≤ w(e)

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

ale e0 ∈ C nebylo ještě uvažováno).

24

Pavel Valtr — Diskrétní matematika

Grafy — Minimální kostra grafu

L0 = (L

\ {e}) ∪ {e0}

Tvrdíme, že (V, L0) 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
e0.)

|L0∆K| < |L∆K|

w(L)

≥ w(L0)

ind. předp.

≥

w(K)

Q.E.D.

¦UXLPSZT UV–fXAvg‘B LU gALAg?VLP SfBvX‘

1. V0 := {v}, kde v je libovolný vrchol z V .
2. Pro i = 1, 2, . . . , n − 1 (n = |V |) nechť ei je hrana minimální váhy vedoucí z Vi−1

do V \ Vi−1.

Obrázek.
Vi = Vi−1 ∪ ei (přidáme koncový vrchol hrany ei).

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

{fXZTSZT UV–fXAvg‘B

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

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.

25

Grafy — Rovinné grafy

Pavel Valtr — Diskrétní matematika

D:~<99§ ›dGq=

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

zobrazení.

IJKLAMJC

Graf G = (V, E) je rovinný, má-li rovinné nakreslení:
Vrcholy odpovídají různým bodům v R2, 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ý.

WOPSVUQRC

(i) K4 je rovinný

(ii) Cn 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ý.)

IJKLAMJC

Stěny rovinného nakreslení: Maximální souvislé oblasti množiny R2\X, kde X je množina

bodů ležících na obloucích nakreslení. (Souvislost bereme intuitivně.)

WOPSVUQC

Vezmeme-li K4, 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.

IJKLAMJC

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

WOPSVUQC

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 K5):

Graf K5 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) v4 leží uvnitř K:

Pak ho umístíme do středu, ale pak kam s vrcholem V5? Žádná stěna nemá na
hranici všechny vrcholy 1, 2, 3, 4.

(b) v4 leží vně K:

Můžeme převést na isomorfní graf s v4 uvnitř.

26

Pavel Valtr — Diskrétní matematika

Grafy — Rovinné grafy

Q.E.D.

VĚTA (Nerovinnost K3,3):

Graf K3,3 (úplný bipartitní graf o 3 + 3 vrcholech) není rovinný.
DŮKAZ:

V =

{1, 2, 3, 10, 20, 30}

Spousta obrázků.

o 1

/ \

/ 3

\

2’ o - -o- - o 1’

\

/

\ /

o 2

Kam s 30?
Q.E.D.

WfYfXfT?LPC

G rovinný

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

DŮKAZ:

Obrázkem K4. 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í K5 ani dělení K3,3.

DŮKAZ:

“⇒”

Zřejmá.

“⇐”

Těžká.

Q.E.D.

Ÿ‘VJXZT TYvUz

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í.

27

Grafy — Rovinné grafy

Pavel Valtr — Diskrétní matematika

(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.

NTXYJLPC

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

kružnici v G.

WOPSVUQC

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.

NTXYJLPC

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ě kom-

ponenty.

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|

28

Pavel Valtr — Diskrétní matematika

Grafy — Rovinné grafy

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

IZBVJQSR

(1) K5 ani K3,3 nejsou rovinné.

K5 : z(i) = 10

6≤ 3 · 5 − 6

K3,3 : z(i) = 9

6≤ 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| =

X

v∈V

deg v ≥ 6|V |

(spor s (i)).

29

Grafy — Barvení map a grafů

Pavel Valtr — Diskrétní matematika

¨Gd~E9a nG] G ›dGq„

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

WOJQ@fSVUQR

(1) Každý stát je souvislý.
(2) Státy sousedící pouze v jednotlivých bodech nebudeme považovat za sousední.

WXf‡VŁg wvRO ‡UXJT

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

IJKLAMJC

G = (V, E) lze (řádně) obarvit k barvami, pokud existuje zobrazení b: V

→ {1, 2, . . . , k}

takové, že {x, y} ∈ E ⇒ b(x) 6= b(y).

IJKLAMJC

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

WOPSVUQRC

(i) χ(C2k) = 2

(ii) χ(C2k+1) = 3

(iii) χ(Kn) = n

(iv) χ(Km,n) = 2 (m, n ≥ 1)

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

}YvUz gJYA ‡UXTJLPg gU@ U XfTALL•Mz –XUZ

(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ý.

WXf‡VŁg wvRO ‡UXJT ——©

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, deg x

≤ 5 (Eulerův vztah).

(a) deg x ≤ 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.

30

Pavel Valtr — Diskrétní matematika

Grafy — Barvení map a grafů

(b) deg x = 5: Nechť sousedé jsou označeni u1, . . . , u5. G je rovinný, tudíž neob-

sahuje podgraf K5 — to ale znamená, že nemůžou být všichni sousedé vzájemně
pospojováni hranami. Bez újmy na obecnosti nechť např. {u4, u5} /∈ E.

* u2

* u5

\

/

x * -- * u3
/

\

* u4

* u1

V grafu G − x ztotožníme u4 a u5 (tím nám nevznikne žádné křížení):

* u2

|__

//

u *

* u3

//

~~|

* u1

Podle indukčního předpokladu existuje obarvení b0 pěti barvami. Obarvení

G

− x pak můžeme definovat jako:

b(v) := b0(v)

v

6= u4, u5

b(u4) = b(u5) := b0(u)

Dobavíme vrchol x barvou různou od b(u1), b(u2), b(u3), b(u4) = b(u5).

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ý.

uVvJXLUvATLP QZSUYC

Indukcí podle |V |:

(1) |V | ≤ 5: zřejmé.
(2) |V | ≥ 6: Nechť v je vrchol nejmenšího stupně. Dle Eulerova formule ⇒ deg v ≤ 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á

31

Grafy — Barvení map a grafů

Pavel Valtr — Diskrétní matematika

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.

hpísničkai
Q.E.D.

32

Pavel Valtr — Diskrétní matematika

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

m:tap_9a `~nG e]„\:c=

WXALMA@ B‘QfBvA

∀G = (V, E) :

X

v∈V

deg v = 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.

X

v∈V

deg v =

X

e∈E

2

| {z }

2|E|

Q.E.D.

ŞJY?TABV• BRBvŁg gLfAL

IJKLAMJC

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

∀A, B ∈ M : A 6= B ⇒ A 6⊂ B

VĚTA (Spernerova):

X buď množina velikosti n. Potom maximální velikost nezávislého systému množin

M

⊆ P (x) je rovna

ˇ n

b n2 c

˘ (např. v Pascalově 4 je to v řádku, jehož součet je 2n, největší

číslo).

Příklady:

(i) n = 3:

X =

{1, 2, 3}

M1 =

{{1, 2}, {1, 3}, {2, 3}}

M2 =

{{1}, {2}, {3}}

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

µ3

1

¶

= 3

(ii) obecné n:

M := množina

bn/2c -prvkových podmnožin množiny X = {1, 2, . . . , n}. Pak

M bude nezávislý systém velikosti

ˇ

n

bn/2c

˘.

DŮKAZ:

(1) Maximální velikost ≥

ˇ n

b n2 c

˘: z předchozího příkladu.

(2) Maximální velikost ≤

ˇ n

b n2 c

˘:

X, M podle předpokladů.
Maximální řetězec: R = {0, {x1}, {x1, x2}, . . . , {x1, x2, . . . , xn}

|

{z

}

X

} kde x1, . . . ,

xn je libovolná permutace prvků X. Maximálních řetězců je n!, navíc kdykoliv si

33

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 podm-
nož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 sys-

tému množin.

(b) =

P

M∈M |M|!(n − |M|)!

|

{z

}

# max. řetězců

obsahujících M

.

Tedy:

n!

≥

X

M∈M

|M|!(n − |M|)!

1 ≥

X

M∈M

|M|!(n − |M|)!

n!

=

X

M∈M

1

ˇ n

|M|

˘

≥

X

M∈M

1

ˇ n

b n2 c

˘ =

|M|

1

ˇ n

b n2 c

˘

|M| ≤

µ n

Ą n

2

¦

¶

Q.E.D.

«XUR ‡JY

K2,2

¤

C4

Ą

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

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

|E| ≤

n

√

n + n

2

DŮKAZ:

Využijeme Cauchy-Schwarzovu nerovnost:

n

X

i=1

xiyi

≤

v

u

u

t

n

X

i=1

x2

i ·

v

u

u

t

n

X

i=1

y2

i

pro libovolné x1, . . . , xn, y1, . . . , yn ∈ R.

Počítáme dvěma způsoby počet podgrafů (cest) u - v - u’. Tento počet je:

(a) ≤

ˇn

2

˘: pro ∀u, u0 ∈ V , u 6= u0 existuje nejvýše jeden v ∈ V takový, že

{u, v}, {u0, v} ∈ E — jinak dostaneme K2,2:

*-* u

X

*-* u’

(b) =

P

v∈V

ˇdeg v

2

˘: pro ∀v ∈ V máme právě ˇdegv

2

˘ vidliček * - v - *.

34

Pavel Valtr — Diskrétní matematika

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

Tedy:

X

n∈V

µdeg v

2

¶

≤

µn

2

¶

≤

1
2

n2

1
2

X

n∈V

((deg v) − 1)

2 ≤

X

v∈V

µdeg v

2

¶

≤

1
2

n2

X

v∈V

((deg v) − 1) · 1

|

{z

}

2|E|−n

≤

s

X

v∈V

((deg v) − 1)2

|

{z

}

≤

√

n2

·

s

X

v∈V

12

|

{z

}

√

n

≤n

√

n

|E| ≤

1
2

(n

√

n + n)

Q.E.D.

35

Grafy — Orientované grafy

Pavel Valtr — Diskrétní matematika

‚d<E9p:~G9§ ›dGq=

Orientovaný graf: −→

G = (V, −→

E ), kde V je libovolná konečná množina a −→

E

⊆ V × V .

IJKLAMJC

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.

WOPSVUQC

−→

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

IJKLAMJC

−→

G je slabě souvislý, pokud

∀x, y ∈ V existuje (neorientovaná) cesta z x do y.

x

• → • ← • → • ← •y

−→

G je slabě souvislý, pokud

∀x, y ∈ V existuje orientovaná cesta z x do y.

x

• → • → • → • → •y

IJKLAMJC

Orientovaný graf −→

G je eulerovský, pokud lze nakreslit jedním uzavřeným orientovaným

tahem.

· · · → • → • → · · ·

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

−→

G = (V, −→

E ) je eulerovský

⇐⇒ −→

G je slabě souvislý a

∀v ∈ V : deg

+ v = deg− v

|

{z

}

(∗)

.

DŮKAZ:

“⇒”

Zřejmé.

“⇐”

LEMMA:

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

36

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 −→

G je eulerovský. Jinak (obdobně jako v neori-

entované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ý uza-

vř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.

6 ] Spor

37

Grafy — Počet koster Kn

Pavel Valtr — Diskrétní matematika

m:tEp r:\pEd

Kn

VĚTA (Cayleyho formule):

∀n ≥ 2: počet koster grafu Kn je n

n−2 (tedy počet stromů na {1, . . . , n}).

WOPSVUQC

n = 2: •

1 −

•

2

20 = 1 kostra.

n = 3: •

1 −

•

2 −

•

3 ,

•

2 −

•

1 −

•

3 ,

•

1 −

•

3 −

•

2

31 = 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

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ři-

daná 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 libo-

volné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 nn−1(n − 1)! možností, jak zvolit 1. až (n − 1). hranu. Každé slunce

dostaneme (n − 1)!-krát. Sluncí tedy dostaneme nn−1 a stromů tak bude nn−2.

Q.E.D.

38