Maticový popis grafu 1) Matice sousednosti G = (V , E), |V | = n AG ∈ {0, 1}V ×V (AG)uv =
1 uv ∈ E 0 uv E
Matice sousednosti je symetrická Na hlavní diagonále jsou 0 2) Matice incidence IG ∈ {0, 1}V ×E (IG)ue =
1 u∈e 0 u e
3) Laplaceova matice LG ∈ Z V ×V
deg u (LG)uv = − 1 0
u=v u v, uv ∈ E u v, uv E
Pozorování:
T IGIG = LG + 2AG
(nad Q)
T Důkaz. IG · IG je čtvercová deg u P P T T = ∈ e, v ∈ e, e ∈ E = I IG · IG = = |{e|u }| ) −1 ) (I (I ) (I G G G ve ue ue G e v uv 0
e∈E
e∈E
u=v u v, uv ∈ E u v, uv E
Teorém 1. ∀G∀k AkG uv = počet sledů délky k od u k v Důkaz.
Indukcí podle k 1. k = 0 k=1
A0G =
A1G = AG
2. k − 1 → k k≥2
E
jednotková
AkG
=
1 0
k−1 = A A G G uv
0 1
uv
=
P
Ak−1 G
w∈v
uw
délky k − 1 od u k w) = # sledů délky k od u k v
(AG)w v =
P
w∈v
Ak−1 G
uw
IP
=
P
w ∈v
(# sledů
Teorém 2. (u)
∀G∀u∈V (G) # koster G = det LG řádek)
(M (x) znamená, že byl vynechán x-tý sloupec a x-tý
Důkaz. DG je IG pro orientovaný graf (má v každém sloupci jednu 1 a jednu − 1) 1
T
(DG)(DG) =
P
e∈E (u)
T = (DG)ue DG ev
DG ∈ { − 1, 0, 1}(n−1)×E (u)T
(u)
DG DG
deg u u = v (DG)ue(DG)ve = − 1 u v; u, v ∈ E 0 u v; uv E e∈E
P
= LG
det AB = det A det B
(u)
= LG
Teorém 3. Cauchy-Biset P det AB = det Aω det B ω (výběr sloupců) ω ⊆{1,2, ,m} |ω |=n
(u)
(u)
det LG = det DG
(u) T
DG
P
=
= # koster G
ω ⊆E |w| =n−1 (V ,ω) je kostra
Lemma 4. ∀G∀u∀ω ⊆ E , |ω | = n − 1 (u) (V , ω) je strom (= ko stra G) det Dω = 01 (V , ω) n ení strom ( ⇒ n ení
ko stra G)
Důkaz. a)
(V , ω) není kostra ⇒ (V , ω) není souvislý ⇒ ⇒ V = V1
.
∪
(disjunktní)
V2 tak, že ω ⊆
V1 2
∪
V2 2
⇒
⇒ (obě čísla jsou buď nahoře, nebo dole) Dω(u) = V
/
{u} = búno u ∈ V1 ⇒ u V2 ⇒
součet řádků v matici Dω indexovaných vrcholy z V2 je (0, 0, , 0) ⇒ (u)
(u)
det Dω = 0
b) (V , ω) je kostra strom má alespoň 2 vrcholy Dω(u) det Dωu = součin prvků na diagonále = ± 1
⇒
(u) det Dω = 1
070307 t(G) = #koster grafu multigraf - může mít násobné hrany a smyčky matice sousednosti multigrafu - udává se vždy počet hran mezi dvěma vrcholy multigraf lze popsat jako trojici (V , E , ϕ), kde V je množina hran, E je množina názvů hran a V V ϕ: E → 2 ∪ 1 Definice 5. Kontrakce hrany v grafu G.e 2
V (G.e) = (V (G)\e) ∪ {Xe } E(G.e) = {f |f ∈ E(G) ∧ f ∩ e = {}} ∪ {WXe |W ∈ V (G) ∧ (WU ∈ E(G) ∨ WV ∈ E(G)) ∧ W V}
U,
Definice 6. Kontrakce hrany v multigrafu G: e e není smyčka V (G: e) = (V (G)\ϕ(x)) ∪ {Xe } E(G: e) = E(G)\{e} ϕ(f ) ϕ(f ) ∩ ϕ(e) = {} ϕ˜(f ) = {Xe } ϕ(f ) = ϕ(e) {W , Xe } ϕ(f ) = {W , U } neb o {W , V } a W
U,V
Teorém 7. ∀G ∀e ∈ E(G) počet koster
multigraf
0 G n esouvislý G = K1 t(G) = 1t(G\e) e sm yčka t(G\e) + t(G: e) e n ení sm yčka
Důkaz. třetí řádek - smyčky můžeme libovolně vyhazovat čtvrtý řádek - e není smyčka t(G) = {kostry G} t(G) = t1(G)∪˙ t2(G) ⇒ t(G) = |t(G)| = |t1(G)| + |t2(G)| = t(G: e) + t(G e)
t1(G) = {kostry ∋ e}
t2(G) = {kostry e} = t(G\e) ⇒ |t2(G)| = t(G\e) F ⊆ E(G) je kostra G e∈F ⇓
⇑
F \{e} je kostra G: e |t1(G)| = |t(G: e)| = t(G: e)
PG(x) = #obarvení G pomocí ( ≤ )x barev Teorém 8. PG(x) je polynom stupně n v x a platí PG(x) =
xn G n em á žádn é h ran y PG −e(x) − PG.e(x) pro e ∈ E(G)
chromatický polynom
Pozorování 3
Rekurzivní vzorec ⇒ PG(x) je polynom Indukcí dle počtu hran G 1. E(G) = {} ⇒ PG(x) = xn 2. G ← G − e, G.e PG(x) = PG−e(x) − PG.e(x) = Důkaz. E(G) = {} ⇒ ∀obarvení (zobrazení) ϕ: V (G) → {1, , x} je dobré obarvení e ∈ E(G) B(G) = {obarvení G} B(G − e) B(G−e) k
{ϕ|ϕ(u) = ϕ(v)}∪˙ {ϕ|ϕ(u) ϕ(v)} l B(G.e)
k B(G)
rozhodnout jestli jde graf obarvit 3mi barvami je NP-úplný => pravděpodobně nelze nalést chromatický polynom rychle
(Pod)grafy jako vektory prostor kružnic G = (V , E) pevný graf Definice 9. vG = {H |H = (V , F ), F ⊆ E }, + , · ) vektorový prostor nad GF(2) = {0, 1} 1·H =H 0 · H = o = (V , {}) H1 + H2 = (V , F1 ÷ F2)
DCV - dokažte, že vG je vektorový prostor Definice 10. eG = {H ∈ vG |∀x ∈ V : degHx ≡ 0 mod 2} Teorém 11. eG je vektorový prostor, dim eG = |E | − |V | + 1
Důkaz. eG uzavřené ve 1, násobení skaláry H ∈ eG ⇒ 1 · H ∈ eG ⇒ 0 · H ∈ eG
triv platí, protože o = (V , {}) ∈ eG
H1, H2 ∈ eG ⇒ H1 + H2 ∈ eG 0 mod 2
∀x ∈ V : degH1 +H2x = degH1x + degH2x − 2|{x u|xu ∈ F1 ∩ F2} = 2k + 2l − 2m ≡
zvolme pevně kostru T elementární kružnice ∀e ∈ E(G)\E(T ): Ke je kružnice určená hranou e a (jedinou) cestou v T mezi koncovými vrcholy e. 4
kG = {kružnice v G} k G ⊆ eG DCV
eG = hkG i
(generují prostor)
Tvrzení 12. {Ke |e ∈ E(G) − E(T )} je báze eG
070314 Vytvořující funkce Motto: Jak explicitně vyjádřit n-tý člen posloupnosti 1, 1, 2, 3, 5, 8, 13, ? Mnohočleny Příklad 13. I , J konečné množiny I , J ⊂ N r∈N kolik existuje dvojic (i, j), i ∈ I, j ∈ J takových, že i + j = r? P j P i r x x Tolik, jaký je koef. u x v j ∈J
i∈I
Příklad 14. Kolika způsoby může vydat bankomat částku 10.000,- ,pokud vydává pouze bankovky v hodnotách 200,- a 500,-? koef. u x100 v (1 + x2 + x4 + + x100 )(1 + x5 + x10 + + x100 ) Příklad 15. Kolika způsoby může vydat bankomat částku 10.000,- ,pokud vydává pouze bankovky v hodnotách 200,-,500,- a 1000,-? koef. u x100 v (1 + x2 + x4 + + x100 )(1 + x5 + x10 + + x100 )(1 + x10 + x20 + + x100 ) Příklad 16. Kolika způsoby může vydat bankomat částku 10.000,- ,pokud vydává pouze bankovky v hodnotách 12 × 200,-,12 × 500,- a 12 × 1000,-? koef. u x100 v (1 + x2 + x4 + + x24 )(1 + x5 + x10 + + x60 )(1 + x10 + x20 + + x120 )
Teorém 17.
Binomická v¥ta:
1. ∀x∈R ∀n∈N (1 + x)n =
2. ∀a,b∈R ∀n∈N (a + b)n =
n 0
n 0
+
+
n 1
x+
n 0
n 2
anb0 +
x2 + +
5
n 1
n n
xn
an−1b1 + +
n n
a0bn
Poznámka 18. 1) a 2) jsou ekvivalentní Důkaz: 1)->2) triviální b n 2)->1) (a + b)n = an 1 + a = an
n 0
+
n 1
b a
+
n 2
a 0 (v tom případě triviální)
b a
2
+ +
n n
b a
n
Důkaz. 1) vezměme r ∈ {0, 1, , n}
roznásobíme-li (1 + x)n, koeficient u xr bude roven počtu n-tic (i1, i2, , in), kde i1, i2, , in ∈ {0, 1} a i1 + i2 + + in = r tedy je roven nr Nekonečné řady Definice 19. Mocninná řada: a0 + a1x + a2x2 + , kde a0, a1, ∈ R (konstanty) x je proměnná Příklad 20. 1 + x + x2 + x3 + = 1 − x pro x ∈ ( − 1, 1) 1
Teorém 21. Nechť (a0, a1, ) je posloupnot reál. čísel. Nechť ∃K ∈ R+: |an | ≤ K n (pro n ∈ N, n ≥ 1) ∞ P 1 1 aixi konverguje (Tedy a(x) můžeme považovat za Potom pro každé x ∈ − K , K řada a(x) = i=0 1 1 funkci na − K , K ). Hodnoty a(x) na libovolně malém okolý 0 jednoznačně určují posloupnost (a0, a1, ):
∀n∈N 0an =
a(n)(0) n!
Definice 22. (a0, a1, a2, ) posloupnost reálných čísel. Potom mocninná řada a(x) = a0 + a1x + a2x2 + je její
(oby£ejná) vytvo°ující funkce
Operace s posloupnostmi A) sečtená (a0, a1, ), (b0, b1, ): (a0 + b0, a1 + b1, ) B) vynásobení (a0, a1, ) číslem α ∈ R:
?
(αa0, αa1, )
C) vynásobení (a0, a1, ) polynomem xk: (0, 0, , 0, a0, a1, ) k
6
D) E) a(x) je vytvořující funkcí (a0, a1, ) a(αx) je vytvořující funkcí (a0, αa1, α2a2, )
?
F) a(x) je vytvořující funkcí (a0, a1, )
a(xk) je vytvořující funkcí (a0, 0, , 0,a1, a2, ) k−1
G) derivování a integrování
a(x) je vytvořující funkcí (a0, a1, )
a ′(x) je vytvořující funkcí (a1, 2a2, 3a3, ) R a a a(x)dx je vyvořující funkcí ( 0 , a0, 21 , 32 , ) kons
H) vynásobení (a0, a1, ),(b0, b1, )
(a0b0, a0b1 + a1b0, a0b2 + a1b1 + a2b0, )
070321 Fibonacciho čísla F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn (pro n ≥ 0) ozn: F (x) je VF posl. (F0, F1, )
F (x) − xF (x) − x2F (x) je VF posloupnosti (F0, F1 − F0, F2 − F1 − F0, F3 − F2 − F1, ) (0,F0,F1, ) (0,0,F0,F1, ) její VF je x
(F0,F1, )
x = F (x) − xF (x) − x2F (x) (v malém okolí 0) x
F (x) = 1 − x − x2 x 1 − x − x2
=
a 1 − λ1x
A
B
= x − x + x − x kde x1, x2 jsou kořeny 1 − x − x2 1
+
2
b 1 − λ2x
odtud Fn = aλn1 + bλn2 1 1−x
je VF posloupnosti (1, 1, )
1 1 − λx a 1 − λx
je VF posloupnosti (1, λ, λ2, ) je VF posloupnosti (a, aλ, aλ2, ) 1
vzorec pro n-tý člen fibonacciho posloupnosti je Fn = √ je vhodné provést kontrolu
F0 = 1,F1 = 4,F2 = 3 Fn+3 = Fn+2 − 3Fn+1 + 8Fn
7
5
√ 1+ 5 2
n
−
√ 1− 5 2
n
Binomická věta ∀r ∈N 0(1 + x)r =
r 0
x0 +
r 1
x1 + +
tj.(1 + x)r je VF posloupnosti
r 0
,
r r
r 1
xr
,,
r r
, 0, 0,
Definice 23.
r 0
=
r(r − 1)(r − 2) (r − k + 1) k!
r ∈ R, k ∈ N0 (0! = 1) Zobecněná binomická věta ∀r ∈R (1 + x)r je VF posloupnosti
r 0
,
r 1
,
r 2
,
Bez Důkazu (tailorův rozvoj funkce (1 + x)r v 0)
Binární Stromy Definice 24. (zjednodušená) i. {} (žádný vrchol) ii. kořen+levý podstrom +pravý podstrom Definice 25. bn = počet binárních stromů s n vrcholy b0 = 1 b1 = 1 b2 = 2 b3 = 5 bn = (b0bn−1 + b1bn−2 + b2bn−3 + + bn−1b0 (pro n ≥ 1) 1 + xb(x)b(x) = b(x) ↓
(0, b0 b0, b0 b1 + b1b0, b0 b2 + b1b1 + b2b0, ) b1
b2
b3
2
b(x) = x(b(x)) + 1 b(x) = b(x) =
√
1 − 4x 2x √ 1 − 1 − 4x 2x
1+
“+” nevyhovuje
zobecněná binomická věta: 8
√
∞ P
1 − 4x =
k=0 ∞ P
1
(1 + x) 2 =
( − 4) 1 2
k=0
k
1 2
k
k
!
xk
!
xk
koeficient nx0 je 1 ⇒
√
1 − 4x můžeme vydělit 2x
!
1 2
1
bn = − 2 ( − 4)n+1
1−
n+1
070328 Ramseyovy věty Příklad 26. 6 osob osoby vůbec neznají
⇒ 3 osoby se navzájem znají (znají se je symetrická relace), nebo se 3
Důkaz. M :=množina 6 osob A ∈ M lib. Dirichletova pravidla ⇒ A zná ≥ 3 osoby nebo A nezná ≥ 3 osoby a) A zná B , C , D 1. osoby B , C , D se vůbec neznají 2. dvě z osob B, C , D (např. B , C) se znají A,B,C se znají b) A nezná B , C , D 1. B , C , D se navzájem znají 2. dvě z osob B, C , D (např. B , C) se neznají A, B, C se neznají
Teorém 27. Ramseoyova věta ∀k ∃n = n(k):
G graf na n vrcholech ⇒ G obsahuje Kk nebo nezávislou množinu k vrcholů.
Ramseova věta (nesymetrická verze): ∀k∀l∃n=n(l,k): G graf na n vrcholech ⇒ G obsahuje Kk nebo nezávislou množinu l vrcholů Poznámka: obě verze jsou ekvivalentní Důkaz. nesymetrické verze 9
indukcí podle k + l: 1. k = 1 nebo l = 1: n = 1 2. k, l ≥ 2, předp., že věta platí pro k ′, l ′ taková, že k ′ + l ′ < k + l tedy ∃n(k, l − 1), ∃n(k − 1, l)
ukážeme, že věta platí pro n 4 n(k, l − 1) + n(k − 1, l) G graf na n vrcholech v ∈ V (G) lib. A: = {u ∈ V (G): uv ∈ E(G)}
B 4 {u ∈ V (G)\{v }: uv E(G)}
|A| + |B | = n − 1 Dirichletův princip ⇒ |A| ≥ n(k − 1, l) nebo n(k, l − 1) a) |A| ≥ n(k − 1, l) na A existuje Kk−1 nebo l nezávislých vrcholů b) |B | ≥ n(k, l − 1) na B existuje Kk nebo l − 1 nezávislých vrcholů
Definice 28. r(k, l) 4 min {n: nesymetrická verze R. věty s parametry k, l platí pro n} Poznámka 29. r(k, l) ≤
k+l−2 k−1
D: indukcí k = 1 nebo l = 1 2) r(k, l) ≤ r(k, l − 1) + r(k − 1, l) ≤
k+l−3 k −1
+
k+l−3 k −2
=
k+l−2 k −1
Definice 30. r(k) 4 r(k, k) r(3) = 6 r(4) = 18 r(5) ∈ [43, 49] r(8) ∈ [282, 1870] r(17) ∈ [8917, 601 080 389] Teorém 31. Ramseova věta - dvoubarevná verze ∀k∀l∃n=n(k,l): hrany Kn obarveny každá červeně nebo modře, tj. c: E(Kn) → {červ., modrá } ⇒ Kn obsahuje červený Kk nebo modrý Kl Poznámka 32. Nesymetrická a dvoubarevná verze jsou ekvivalentní 10
Důkaz. hrany G
↔ červené hrany v Kn
(v nesym. verzi) nehrany G ↔ modré hrany v Kn
Teorém 33. R. věta - vícebarevná verze ∀r∀k1∀k2 ∀kr∃n=n(k1, ,kr)
hrany Kn obarvený barvami 1, 2, , r ⇒ ∃i∈{1, ,r}∃U ⊆ V (Kn): |U | = ki a c(uv) = i pro u, v ∈ U
Důkaz. indukcí podle k1 + + kr 1. ∃i ki = 1: n = 1 2. ki > 1 pro ∀i, předp., že platí pro k1′ + + kr′ < k1 + + kr ukáže se, že tvrzení platí pro n = n(k1 − 1, k2, , kr) + n(k1, k2 − 1, k3, , kr) + + n(k1, , kr −1, kr − 1) v ∈ V (G) libovolný D.pr. ⇒
∃i: |Ai | ≥ n(k1, k2, , ki − 1, , kr −1, kr) atd.
070404 n(k1, , kn) ≤ 2 +
n P
i=1
(n(k1, , ki − 1, , kn) − 1)
Teorém 34. nr(3, , 3) ≤ 1 + [e.r!] Důkaz. Pozorování: nr(2, 3, , 3) = nr −1(3, , 3) ≥ ≤ Nepřítel obarví E(Kn) barev n(k1, , kn) ≤ 2 + n˜r (3) = nr(3) − 1
n P
i=1
první barva je použitá O K první barva není p oužitá - je tam jednobarevný tro jůhelník O K
(n(k1, , ki − 1, , kn) − 1) = 2 + r(nr −1(3) − 1)
n˜r (3) ≤ 1 + r nr −1(3) ≤ 1 + r (1 + (r − 1)(1 + (r − 2)(nr −3(3))) n˜1(3) = n1(3) − 1 n˜r (3) ≤ r! indukcí 1)
r=1
ind. krok
r P
i=0
1 i!
1 1 1 1 = r! 0! + 1! + + (n − 1)! + n!
1 1 n˜r (3) = 2 ≤ 1! 0! + 1! = 1(1 + 1) = 2
11
r⇐r −1
rP −1
IP
n˜r (3) ≤ 1 + r nr −1(3)≤1 + (r − 1)! rP −1
1
= r! r! + r! 1
= r! r! + r! = r!
i=0
rP −1
1 r!
+
i=0
rP −1 i=0
1 = i!
1 i!
=
1 i!
!
= r!
r P
i=0
i=0
1 r= i!
1 i!
důsl: n˜r (3) ≤ r!
r P
i=0
1 i!
≤ r!
∞ P
i=0
1 i!
= er!
nr(3) = 1 + n˜r (3) ≤ 1 + er! ⇒ nr(3) ≤ 1 + [e.r!]
Schurovo lemma ∀r∃N (≤[e.r!]){1, 2, , N } = a1 ∪ ∪ an ⇒ ∃i∃x, y,z ∈aix + y = z Důkaz. 1
2
1 2
a b
= a1 ∪ ∪ an
N N
N +1
ϕ:
(nepřítel obarví)
[1 N + 1] 2
→ {1, 2, , n}
ϕ(ab) = i ⇔ |a − b| ∈ ai ϕ: obarvení hran 1 + [e.r!] nr(3) ≤ 1 + [e.r!] RV
⇒ Pro ϕ ∃
jednobarvný trojúhelník
∃a
x = b − a ∈ ai ,
⇒ x, y, z ∈ ai
y = c − b ∈ ai , z = c − a ∈ ai x+ y=z
motivace: Velká Fermatova věta ∀n ≥3xn + y n = z n nemá řešení x, y, z ∈ N Teorém 35. (není na zkoušku) ∀n∃ p0∀ p> p0, p prvočíslo ∃n etriviá lní
n řešení x +
y n ≡ z n mod p
Teorém 36. RV ∀ p,r,k∃N ∀ [1pN ] = a1 ∪ ∪ an∃A ∈ [1kN ] ∃i∀x∈ A x ∈ ai p
12
∀ p,r,k∃N ∀
[1 N ] p
= a1 ∪ ∪ an∃A ∈
[1 N ] k
∃i
A p
Teorém 37. Erdös-Szekerös ∀k∃N ∀X ⊆E2|X | = N , X v obecné poloze ∃A ⊆X |A| = k a body A jsou vrcholy konvexního k-úhelníka. min N = ES(k)
(erdös-sekerösovo číslo)
ES(1) = 1 ES(2) = 2 ES(3) = 3 ES(4) = 5 Důkaz. p=4 ES(k) ≤ nr=2 (k, 5) ≤ n42(k)
<——– barvním 4veřice pomocí 2 barev
N = n42(k, 5) Nepřítel dá N bodů v obecné poloze já obarvím
X 4
=
a1 ∪ a2 konvexní nekonvexní
RV
⇒
∃ A ⊆ X , |A| = k, nebo ∃ A ⊆ X , |A| = 5,
A 4
konvexní
A 4
nekonvexní
→ NELZE
Latinské čtverce a konečné projektivní roviny Definice 38. Latinský tverec
řádu n je A ∈ {1, , n}n×n
∀i,j j ′Aij Aij ′, A ji A j ′i Definice 39.
A, B ∈ {1, , n}n×n latinské čtverce A⊥B ⇔ ∀a,b∈{1, ,n}∃i,j Aij = a
a
Bij = b
Teorém 40. A1, , At jsou NOLČ(n) Definice 41.
kone£ná projektivní rovina
⇒ t≤n−1
je množinový systém (B , P ), P ⊆ 2B splňující
1. ∀ p p ′ ∈P |p ∧ p ′| = 1 13
2. ∀x y ∈B ∃ p∈Px, y ∈ p 3. ∃4 body a, b, c, d z nichž žádné 3 neleží na přímce 3 ⇔ B nelze pokrýt dvěma přímkamy
( ¬∃ p,q ∈Pp ∪ q = B)
příklad: fanova rovina DCV ∀kP R(B , P )∃n ∀ p∈P |p| = n + 1 ∀x∈B |{p|x ∈ p ∈ P }| = n + 1 |B | = |P | = n2 + n + 1 n je řád (B, P )
070418 Toky v sítích Definice 42.
Sí´
(G, z , s, c) kde G = (V , E) je orientovaný graf bez smyček
z, s ∈ V z s
(zdroj a stok)
c: E → R+ 0 Definice 43.
tok v síti
(G, z , s, c): funkce f : E → R+ 0 taková, že
1. ∀e∈Ef (e) ≤ c(e) 2. ∀u∈V \{z,s}
P
ux∈E
f (ux) −
P
f (xu) = 0
xu∈E
f Definice 44. P P P P f (sx) f (xs) − f (xz) = f (zx) − w(f ) = velikost toku
xz ∈E
z x∈E
xs∈E
sx∈E
Tvrzení 45. Pro každou síť existuje maximální tok (tj. tok maximální možné velkikost) BD Definice 46.
ez
(mezi z a s)
libovolná R ⊆ E množina hran taková, že (V , E \R) neobsahuje orientovanou cestu ze z do s. Definice 47. množiny E ′ ⊆ E P c(e) e(E ′) = kapacita
e∈E ′
Teorém 48.
v¥ta o tocích
14
Pro každou síť (G, z , s, c): max w(f ) = min c(R) f tok
R řez
Definice 49. A, B ⊆ V, A ∩ B = ∅ S(A, B) = {xy ∈ E |x ∈ A, y ∈ B } Tvrzení 50.
1
V = A∪˙ B, z ∈ A, s ∈ B ⇒ S(A, B) je řez (takové řezy nazýváme
elementární
)
Důkaz. každá orientovaná cesta ze z do s obsahuje hranu z S(A, B) Tvrzení 51.
⇒
S(A, B) je řez
2
Každý řez obsahuje elementární řez. Důkaz. A E \R)
4
množina všech vrcholů z V do kterých vede orientovaná cesta ze z v grafu (V ,
z ∈ A, s A
ukážeme, že S(A, V \A) ⊆ R nechť uv ∈ S(A, V \A)
kdyby uv R, potom by platilo v ∈ A(spor) tedy uv ∈ R Tvrzení 52.
3
Každý v inkluzi minimální řez je elementární. (řez R takový, že R\{e} už není řez pro ∀e ∈ R) Důkaz. z tvrzení 2
Lemma 53. ∀A ⊆V , z ∈A, s A∀to k fw(f ) = f (A, V A) − f (V A, A) Důkaz. ∀u∈A\{z }
P
ux∈E
P
zx∈E
součet:
P
f (ux) − f (zx) −
u∈A
P
ux∈E
Definice 54. f (X , Y ) =
P
f (xu) = 0
xu∈E
P
f (xz) = w(f )
x z ∈E
f (ux) − P
P
xu∈E
f (xu) = w(f )
f (xy)
xu∈E ,x∈X ,y ∈Y
tedy f (A, V \A) − f (V \A, A) = w(f )
15
Důsledek: pro každý tok f a pro každý řez R: w(f ) ≤ c(R) a tedy také max f (w) ≤ min c(R) Důkaz. existuje A ⊆ V , z ∈ A, s A: S(A, V \A) ⊆ R
(tvrz. 2)
w(f ) = f (A, V \A) − f (V \A, A) ≤ f (A, V \A) ≤ c(S(A, V \A)) ≤ c(R) Definice 55.
cesta
(v0, e1, v1, e2, , vm), kde ei = vi−1vi nebo vivi−1∀i
Definice 56. cesta (v0, e1, , vm) je
nasycená
pokud existuje hrana ei = vi−1vi splňující f (ei) = c(ei)
nebo existuje hrana ei = vivi−1 splňující f (ei) = 0 Tvrzení 57. Tok je maximální (tj. má maximální možnou velikost) právě když každá cesta ze z do s je nasycená Důkaz. ⇒ . sporem: nechť existuje nenasycená cesta (v0 , e1, v1, , vm ) ze z do s =s
=z
pro každou ei = vi−1vi def ε(ei) = c(ei) − f (ei) > 0 ei = vivi−1 def ε(ei) = f (ei) > 0 položme ε = min ε(ei) > 0 i=1, ,m def tok f ′: f ′(e) = f (e) pro e ei pro ∀i f ′(ei) = f (ei) + ε, pokud ei = vi−1vi f ′(ei) = f (ei) − ε, pokud ei = vivi−1 w(f ′) = w(f ) + ε > w(f ) ⇐.
0704025 síť (G, z , s, c) tok f : E → R+ 0 velikost toku řez, elementární řez
Tvrzení 58. Pro každou síť existuje maximální tok 16
BD
Teorém 59. max w(f ) = min c(R) f tok
R řez
pro každou síť Tvrzení 60. Tok f je maximální ⇔ neexistuje nenasycená cesta ze z do s Důkaz. ⇒ . sporem: nechť existuje nenasycená cesta ze z do s vylepšíme o něj ε > 0 podle této cesty ⇒ ∃ tok f ′ takový, že w(f ′) > w(f ) ⇐ . nechť každá cesta ze z do s je nasycená A: = množina všech vrcholů do nichž existuje nenasycená cesta ze z z ∈ A, s A ∀e∈S(A,V \A) f (e) = c(e)
(jinak spor s definicí A)
∀e∈S(V \A,A) f (e) = 0
(jinak spor s definicí A)
w(f ) = f (A, V \A) − f (V \A, A) = f (A, V \A) − 0 = c(A, V \A) = c(S(A, V \A)) tedy f je maximální, protože w(f ) ≤ c(S(A, V \A)) pro každý tok f ′
Důkaz věty o tocích ∃ max. tok f jeho velikost je rovna kapacitě nějakého řezu R = S(A, V \A)
řez R má minimální kapacitu, protože c(R ′) ≥ w(f ) pro každý řez R ′ =c(R)
Algoritmus (Ford, Fulkerson) 1. f (e) = 0 pro ∀e∈E 2. dokud existuje nenasycená cesta ze z do s, opakuj: najdi nenasycenou cestu P ze z do s, najdeme příslušné ε > 0, vylepšíme o ε tok podle cesty P (dostaneme tok f ′ velikosti w(f ′) = w(f ) + ε) 3. tok f → výstup (max. tok) Teorém 61.
V¥ta o celo£íselném toku
jsou-li všechny kapacity celočíselné (resp. racionální), potom F-F algoritmus skončí po konečně mnoha krocích a najde maximální tok takový, že f (e) je celočíselný (resp. racionální) pro každou hranu e ∈ E Důkaz. celočíselný algoritmus zachovává celočíselnost a každým krokem zvětší velikost toku alespoň o 1 17
rac: vynásobíme všechny kapacity vhodným celým číslem, abychom dostaly celočíselné kapacity, najdeme celočíselný maximální tok, tok na každé hraně znovu vydělíme číslem, kterým jsme násobili Definice 62. M = (Mi |i ∈ I) je
mnoºinový systém
M má systém různých reprezentantů (SRR), pokud existuje f : I → ∪ Mi taková, že i∈I
1. f (i) ∈ Mi pro ∀i∈I 2. f je prostá Teorém 63.
Hallova v¥ta
M má SRR ⇔ ∀J ⊆I ∪ Mi ≥ |J | i∈J
Důkaz.
⇒ . zřejmé ⇐. G = (V , E) V = I ∪ X ∪ {z, s} E = {zi |i ∈ I } ∪ {ix|i ∈ I , x ∈ Mi } ∪ {xs|x ∈ X } síť (G = (V , E), z, s, 1), c(e) = 1 pro ∀e∈E existuje maximální celočíselný tok f , f (e) je 0 nebo 1 pro ∀e∈E pokud w(f ) = |I | pokud w(f ) = |I |, příslušné hrany s tokem 1 dávají SRR pokud w(f ) < |I |, existuje řez R velikosti < |I | J 4 {i ∈ I |i neleží na žádné hraně R} Y
4 {y ∈ X |ys je hranou R}
|I \J | + |Y | ≤ (#hran R) < |I | |J | + |I \J | + |Y | < |I | + |J | |I |
|Y | < |J | spor s pravou stranou v H. větě
070509 Hameltonovská kružnice Definice 64. G = (V , E), |v | = n
HK v G je uspořádané V = v1, v2, , vn aby vi , vi+1 ∈ E pro ∀i=1,2, ,n
Pozorování 18
(vn+1 = v1)
Kn má HK ⇔
n≥3
Km,n má HK ⇔ m = n ≥ 2 Tvrzení 65. Rozhodnout, zda G má HK je NP-úplný problém Bez Důkazu
n≥3 V1
∀x∈V deg x ⊇
V2 V3
n 2
⇒
G má HK
∀x y ∈V deg x + deg y ⊇ n
⇒
G má HK
∀x y,x y E deg x + deg y ⊇ n
⇒
G má HK
Definice 66. Chvatalův uzávěr G while ∃x y,x y E deg x + deg y ≥ n do E(G) 4 E(G) ∪ {xy} V4
G má HK
⇔
...
[G]
[G] má HK
Důkaz. ⇒ ⇐ G...G + xy má HK G
G + e1
G + e1, e2
G + xy má HK
C
x1 = x, x2, , xn = y
G + e1 ek = [G]
x y E(C) ⇒ C je HK v G x y ∈ E(C)
X = {i|xxi ∈ E(G)}, |X | = degGx, X ⊆ {2, 3, , n − 1}
Y = {i|yxi−1 ∈ E(G)}, |Y | = degGy, Y ⊆ {3, 4, , n}
X ∪ Y ⊆ {2, 3, , n} |X ∪ Y | ≤ n − 1
|X ∩ Y | = |X | + |Y | − |X ∪ Y | = deg X + deg Y − |X ∪ Y | ≥ n − (n − 1) = 1 ⇒ i ∈ E(G) ∃i∈X ∩Y xx yx ∈ E(G) i −1
⇒ x1, x2, , xi−1, y = xn , xn−1, , xi , x1 = x
TSP
HK v G
obchodní cesující
Knw: E(Kn) → R+ 0,k P w(e) ≤ k? Otázka: ∃HK C ⊆ E(Kn)
Vstup.
e∈E(C)
19
Teorém 67. TSP je NP úplný Definice 68. HK α TSP G → Kn n = |V (G)|
V (Kn) = V (G) w(uv) =
∃Cv(C) = n ⇔ G má HK
1 uv ∈ E(G) 2uv E(G)
Aprox. alg. Pokud w splňuje trojúhelníkovou nerovnost -> 2-aproximace trojúhelníková nerovnost: w(xz) ≤ w(xy) + w(yz) 2-aproximace: ∀Kn ,w
C dé aby O PT
w(C) ≤ 2 OPT
Algoritmus 1. Najdu minimální kostru T vůči w →
2. Uvaž symetrickou orientaci T kostry T →
3. Nakresli T jedním tahem U = v1, v2, 4. While ∃x kterým U projde ≥ dvakrát do zkrať U u vrcholu x 5. Vydej U , který je HK Důkaz. C˜ je optimální HK w(T ) ≤ w C˜
w(U ) = 2w(T ) ≤ 2w C˜ = 2 OPT w(U ′) ≤ w(U )
w(C) ≤ w(U ) ≤ 2 OPT
070523 Rovinné grafy 2-souvislé grafy, ušaté lemma Teorém 69. KV (G) ≥ 3, |V (G)| ≥ 5 ⇒ ∃e∈E(G)KV (G.e) ≥ 3 Důkaz. sporem ∃GKV (G) ≥ 3, |V (G)| ≥ 5, ∀e∈E(G)KV (G.e) < 3 ∀e∈E(G)∃ ye ∈V (G)G {y, v, ye } nesouvislý 20
KV (G.e) < 3 ∃A ≤V (G)|A| ≤ 2 G\A nesouvislý A = {u}, u xe
?? ?
??
( G\u ).e = (G.e)\u s ouvislý
⇒ souvislý
souvislý
A = {xe }
⇒
A = {x, y} xe A = {xe , ye }
G\{u, v} = G.e\{xe }
(G\{x, y}).e = G.e\{x, y} souvislý
souvislý
G\{u, v, ye } = G.e\{xe , ye }
Vybereme e ∈ E(G) a ϕe ∈ V (G) tak, aby K bylo největší možné. ∃z ∈K( (V (G)\K)\{u,v, ye }) yez ∈ E(G) ⇒ ∃w ∈V (G) ye , z , w je řez v G Tvrdím: {K ∪ {u, v })\{w} indukuje souvislý podgraf G\{z , ye , w} ∀ ∃ vezmeme nejkratší takovou cestu → ta je ⊆ K ∪ α,β ∈K ∪{u,v }\{w } cesta o d α do β v G\{ye ,w} {u, v} {w} / / Tedy G {z, ye , w} má komponentu K˜ ⊇ K ∪ {u, v} {w}, |K˜ | ⊇ |K | + 2 − 1 = |K | + 1 spor s
max K
Důsledek ∀G, KV (G) ≥ 3 lze vytvořit z K4 “dobrými” roztaženími vrcholů. Lemma 70. A ⊆ V (G) je minimální (co do inkluze) řez v G, C1, C2, Ck jsou komponenty souvislosti G A, pak pro ∀x∈A∀i∈{1, ,k}∃ y ∈Cix y ∈ E(G)
Důkaz. Kdyby z x ∈ A nevedla žádná hrana do Ci, pak A ′ = A\{x} by byl řez, neboť Ci by byla komponenta souvislosti G\A ′. A ′ ⊂ A spor s minimalismem A Lemma 71. KV (G) ≥ 2, G rovinný ⇒ v ∀ nakreslení hranice ∀ stěny je (grafová) kružnice Důkaz. ušatým lematem, nepřítel dá nějaké G, vezmeme kružnici začnu krunicí a přidávám ucha indukcí v každém kroku “hranice ∀ stěny je grafová kružnice” 1) 2 stěny, mají stějnou hranici = kružnici 2) K ← K − 1
ucho se nakreslilo do stěny, která se rozpadně na dvě podkružnice
Lemma 72. ∀ rovinný G ∀e∈E(G) lze G nakreslit (bez křízení) tak, že e je na hranici vnější stěny Důkaz. kruhová inverze nebo rovina -> míč -> rovina 21
Teorém 73. kuratowski G je rovinný ⇔ G neobsahuje dělení K5 ani K3,3 jako podgraf |E | ≤ 3|V | − 6
|E | ≤ 2|V | − 4
když nemá K3
Definice 74. d¥lení
G
vznikne z grafu G nahrazením libovolných hran cestami Důkaz. ⇒ . jasné (pokud by obsahoval, nebyl by rovinný) ⇐ . Indukcí 1. |V (G)| ≤ 4 OK protože G musí být rovinný 2. |V (G)| ≥ 5
a) G je nesouvislý G = G1∪˙ G2∪˙ ∪˙ GK ⇒∀Gi rovinný IP
b) kV (G) = 1 Gi ⊆ G, |V (Gi)| < |V (G)| lze použít IP Gi nemá dělení K5, K3,3
⇒ Gi jsou rovinné
nakreslím G1, G2 tak, aby n byl na vnější stěně c) kv(G) = 2 G1 = (C1 ∪ {u, v }, E(G[C1 ∪ {u, v}]) ∪ {u, v })
|V (G j )| < |V (G)| ... lze použít IP
⇒ Gi jsou rovinné, vezmu rovinné nakreslení uv je na hranici vnější stěny
Gi nemá dělení K5, K3,3 d) kv(G) ≥ 3
⇒ ∃e∈E(G)kv(G.e) ≥ 3
|V (G.e)| < |V (G)| lze použít IP
G.e nemá dělení K5, K3,3 ⇒ G.e rovinný ⇒ G rovinný Lemma 75. G.e má dělení k3,3 ⇒ G má dělení k3,3 Lemma 76. G.e má dělení k5 ⇒ G má dělení k5 nebo k3,3 G.e je rovinný G.e − xe
=>
okolí xe tvoří kružnici
sousedi u dělí C na useku pokud ∀ sousedy v jsou ve stejném úseku OK
pokud nejsou ∀ sousedi u ve stejném úseku, pak máme jeden z
ale žádná z nich nemůže nastat (převod na dělení k3,3 nebo k5)
22
