Kombinatorika a grafy I

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey

Kombinatorika a grafy I látka z II. semestru informatiky MFF UK podle přednášek Ondřeje Pangráce

Zpracoval: Jan „Zaantar“ Štětina

Obsah Asymptotická notace..............................................................................................................................................2 Odhad faktoriálu................................................................................................................................................2 Odhady binomických koeficientů......................................................................................................................2 Největší kombinační číslo.................................................................................................................................3 Částečně uspořádané množiny...............................................................................................................................3 Princip inkluze a exkluze.......................................................................................................................................5 Vytvořující funkce..................................................................................................................................................6 Binární stromy........................................................................................................................................................6 Halleova věta, Systém různých reprezentantů.......................................................................................................7 Konečná projektivní rovina....................................................................................................................................8 Konstrukce KPR................................................................................................................................................9 Bloková schémata.................................................................................................................................................10 Toky v sítích.........................................................................................................................................................10 Míra souvislosti v grafech....................................................................................................................................12 2-souvislost......................................................................................................................................................12 Ramseyovy věty...................................................................................................................................................13

1

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey (přednáška 1, 23.2.09)

Asymptotická notace Def: Mějme f , g : ℕℝ  , pak: (1) f ∈O  g ⇔∃c≥0, n 0∈ℕ ∀ n≥n 0 : f  n≤c⋅g  n , tedy existuje c≥0 takové, že od nějakého n 0 pro všechna n platí f n≤c⋅g n , anebo také:

⇔lim sup n ∞

f n ∞ . g  n

f  n =0 g n n∞ (3) f ∈ g ⇔ g ∈O f  (4) f ∈ g ⇔ g ∈o f  (5) f ∈ g ⇔ f ∈O  g ∩ g  Píšeme také f =O  g  , ale ne O g = f . (2)

f ∈o g ⇔ lim sup

Odhad faktoriálu Úvod: Faktoriál n!=1⋅2⋅3⋅...⋅n . Pro n≥4 je 2n ≤n!≤n n (důkaz m.i.). n Platí ∀ c ∈ℝ ∃ n 0∈ℕ ∀ n≥n 0 : c ≤n! (hrubý odhad zespoda). Tvrz.:

n 2

n

 

n1 n ≤n!≤ 2

Důkaz: BÚNO uvažme n sudé. Dolní odhad: Spárujeme „od konců“ 1⋅2⋅...⋅n−1⋅n , n vidíme, že pro 1≤ k ≤ je k⋅n−k ≥n . 2 Tedy platí

n 2

n

∏ k⋅n−k ≥n 2

Horní odhad: Analogicky, použijeme AG-nerovnost (

 k⋅n−k 2≤

.

k⋅n−k 1≤

k= 1

Věta:

Mějme n∈ℕ , pak

k n−k 1 n1 = 2 2

n1 2  a tedy 2

n 2

k= 1

Horní odhad: n 1

n 1 1

ln n !≤ ∫ n⋅x⋅dx=[ x⋅ln x −x ]

Platí

1

Takže platí

ln n!≤n1⋅ln n1−n11⇒  n1n 1 ⇒ n!!≤e  n1 ⋅ln n1 −n = en n n n n n!=n⋅ n−1!≤n⋅ n −1 =n⋅e⋅  . e e

n

∫ ln  x−1⋅dx ≤ln n! , což se rovná: 2

∫ ln x⋅dx=[ x⋅ln x −x ]n1=n⋅ln n−n1 1

nn n n n⋅ln n −n 1 = n⋅e=e⋅  , Q.E.D. a tedy n!≥e e e

Odhady binomických koeficientů Úvod:

n! n  n = = n  , tedy BÚNO můžeme počítat s 0≤k ≤ . 2 k k !⋅n−k ! n−k

☼:

n 0≤k 1k 2≤ ⇒ n  n 2 k1 k2

 

k n = n⋅n−1⋅...⋅n−k −1 ≤ n k k⋅k −1⋅...⋅1 k!



2

ab )pro k⋅n−k 1 2

n

 ∏ k⋅n−k 1≤ n1 2

n n n n e⋅  ≤n!≤n⋅e⋅  . e e

Důkaz: Vezmeme ln n!=ln1ln 2...ln n Dolní odhad: n1

 a⋅b≤

. Q.E.D.

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey Věta:

Pro 1≤k ≤

n e⋅n k je  n ≤  . 2 k k k

Důkaz:

Dokážeme silnější tvrzení, že

k

 ∑  ni ≤ e⋅n k

.

i=0

n

Víme, že

n

k

∑  ni ⋅x i=1x n a také ∑  ni ⋅x i≥∑  ni ⋅xi . i=0

i=0

k

i= 0

k

k

1 1 n n i n 1 n 1 k ⋅1 x  ≥ k⋅∑  ⋅x = ∑  ⋅ k −i = ∑  ⋅  x x x i= 0 i i=0 i x i=0 i  k

Tedy

∑  ni ≤ i=0

n

1 x  xk

x n

≤  1 x≤e x

e  xk

k−i

k

∑  n  i= 0 i

vždy1 k k n n

e  e ⋅n k e⋅n k = k =  . Q.E.D. k k k k  volme x= k  n n

=

Největší kombinační číslo Úvod: BÚNO uvažujme n sudé. n n 2 ≤ n ≤ e⋅n n/2 ⌊ n/2⌋  n/ 2 

   =2

 

n 2

= 2⋅e 2⋅m

Věta:

n 2

2n ≤ n ≤2n n1 ⌊n /2 ⌋ 



...

n 2



průměr 2⋅m

2 2 ≤ 2⋅m ≤ Pro m≥1 platí (odlišnost o konstantu!) 2⋅ m m  2⋅m

 

Důkaz:

1⋅3⋅5⋅...⋅2⋅m−1 1 1 ≤ Pm≤ , chceme . 2⋅4⋅6⋅...⋅2⋅m  2⋅ m  2⋅m 1⋅3⋅5⋅...⋅2⋅m−1 2⋅4⋅6⋅...⋅ 2⋅m 2⋅m ! 1 2⋅m ⋅ = = ⋅ . Rozšíříme P m = 2⋅4⋅6⋅...⋅2⋅m  2⋅4⋅6⋅...⋅ 2⋅m 22⋅m⋅m!2 22⋅m m 2⋅m−1⋅2⋅m1 1 1 1 1⋅3 3⋅5 5⋅... 1− 2 ⋅1− 2 ⋅... = P 2m⋅2⋅m11  ⋅1− 2⋅m 2 = 22 ⋅ 4 2 ⋅ ... ⋅...⋅ 2 Horní odhad:  2⋅m 2 4 1  Definujeme P m=

1

1

1

2 1 k −1  k −1⋅ k 1 1 1 1− 2 = 2 = ⇒ Pm  2⋅m1  2⋅m k k k2 2⋅m−2⋅2⋅m 1 1 1 1 2⋅4 4⋅6 6⋅... 1 1− 2 ⋅1− 2 ⋅...  ⋅1− 2⋅m−12 = 3 2 ⋅ 52 ⋅ ... ⋅...⋅ 2⋅m−1 2 = P 2 ⋅2⋅2⋅m 1 3 5   1  m



Dolní odhad:

1

1 2

1

1 P m⋅4⋅m ⇒ P m

1 1 = , Q.E.D.  4⋅m 2⋅ m

(přednáška 1, 23.2.09)

Částečně uspořádané množiny Def:

Částečně uspořádaná množina (ČUM) je  X , ≤  , kde X je neprázdná množina a reflexivní, ≤ je relace, která je antisymetrická a tranzitivní.

Př.:

Hasseho diagramy {1,...,10},dělitelnost 

Def.:

Mějme částečně uspořádanou množinu  X , ≤  , pak a∈ X je minimální, pokud pro všechna x ∈X platí nejmenší, ... maximální, ... největší, ...

Def.:

Pozn.:

x≤a ⇒ x=a , a≤x , a≤x ⇒ x=a a x≤a .

f : X  X ' , kde  X , ≤  , X ' , ≤'  jsou dvě částečně uspořádané množiny, je vnoření, pokud (1) f je prosté (2) pro všechna x , y ∈ X platí x≤ y , právě když f  x ≤' f  y  .  X , ≤  je lineární ⇔ pro všechna x , y ∈ X platí x≤ y nebo y≤x . 3


Nechť  X , ≤  je ČUM, potom existuje její vnoření do 2 X

, ⊆ .

Důkaz: Chceme vnoření f : X  2 , položíme f x ={y ; y ∈ X , y≤ x } X

(1) předpokládejme f x = f  y  .

(2) ⇒ předpokládejme x≤ y .

Pak platí x≤ x ⇒ x ∈ f  x ,

Pak pro všechna z∈ X platí

x ∈ f  x ⇒ x ∈ f  y ⇒ x ≤ y .

z∈ f x ⇒ z≤x ⇒ z≤ y ⇒ z ∈ f  y⇒ f  x⊆ f  y  .

Analogicky y ∈ f x  , y ∈ f  x ⇒ y≤ x .

⇐ nechť f x ⊆ f  y  .

 x≤ y ∧ y≤ x ⇒ x = y , tedy f je prosté.

Pak pro všechna z∈ X platí z≤x ⇒ z∈ f  x⇒ z∈ f  y ⇒ z≤ y . Položíme z :=x a pak x≤ y . Q.E.D.

Def.:

R⊆ X je řetěžec, A⊆ X je antiřetězec,

r 1≤r 2∨r 2≤r 1 . pokud pro všechna r 1, r 2∈ R platí pokud pro všechna a 1, a 2∈ A , a 1≠a 2 platí ¬a1 ≤a 2 ∧¬a 2≤a1  .

Def.:

Délka je  X , ≤ =max {∣R∣; R řetězec v  X , ≤ } . Šířka je  X , ≤ =max {∣A∣; A antiřetězec v  X , ≤ } .

Věta:

O dlouhém a širokém Mějme  X , ≤  ČUM, ∣X∣=n . Potom  X , ≤ ⋅X , ≤ ≥n . Důkaz: Označíme X 1={x ∈ X ; x minimální v  X , ≤} .

Mějme R řetězec. Nechť x , y ∈R , x , y ∈ X , x≠ y . Pak x≤ y ∨ y≤ x , SPOR.

X l (předpokládejme, že máme definováno X 1,... , X l ). Položme

l

Dokážeme t = X , ≤ .

i =1

Volme x t libovolný v X t .

X ' l= X ∖∪ X i . (pokud X ' l=∅ , iteraci ukončíme a položíme t :=l )

Pak máme x k 1≤...≤ xt , kde x i ∈ X i a tedy x k 1 ∉ X k .

X l1 ={x ∈ X ' l ; x minimální v  X ' l , ≤} . Získáme

Z toho plyne, že existuje x k ∈ X k takové, že x k ≤x k 1≤...≤x t .

X 1 , ... , X t , zjevně antiřetězce.

Takto lze postupovat až do x 1 , tedy x 1≤...≤ x t .

(1) Pro i =1...t platí ∣ X i∣≤  X , ≤ 

t

t

i= 1

i=1

⇒ ∑ ∣ X ∣i ≤∑   X , ≤=t⋅ X , ≤ = X , ≤ ⋅ X , ≤  . Q.E.D.

(2) X 1 , ... , X t tvoří rozklad X. (3) t ≤ X , ≤ :

Věta:

Erdös-Szekresova (opakování) Libovolná posloupnost n 21 různých čísel obsahuje monotónní podposloupnost délky n1 . Důkaz:

Máme x 1 , ..., xn 1 , X ={1 , ... , n2 1} . 2

Definujeme i◂ j ⇒i≤ j∧ x i≤ x j  . Toto je částečné uspořádání. Víme, že ⋅≥n2 1 ⇒ ≥n2 1 … klesající podposloupnost nebo

Věta:

≥n 2 1 … rostoucí podposloupnost. Q.E.D.

Spernerova

⌊n/n2 ⌋

Bn = Důkaz: Pozn.:

Počítejme počet p dvojic M , R , kde M ∈ A , R ∈R, M ∈ R :

Bn =n1 2n Bn≥ n1 Mějme 0≤k ≤n , A= {1 ,... , n} je antiřetězec v B a pak n k n  B ≥ n  B ≥ platí a . n n ⌊n /2⌋ k n  Stačí nám tedy už jen dokázat, že Bn≤ . ⌊n / 2⌋ n  Vezměme A libovolný antiřetězec, chceme A≤ . ⌊n /2⌋ Položme R:= množina všech maximálních řetězců.

(1) (2)

Každý R je nejvýše jednou ve dvojici M , R , tedy p≤∣R∣=n! . Fixujme M ∈ A: M ={m1 , ... , mk },∣M ∣=k . Máme R∈R, M ∈R ⇒{x  1 ,... , x  k }={m1 ,... , mk } . Počet R s touto vlastností je k !⋅n−k ! . Tedy p= ∑ ∣ M∣!⋅n−∣ M∣ !≤n! , M ∈A

∣ M∣!⋅n−∣ M∣ !≤n! 1 =∑ = n! M ∈A M∈A  n  ∣ M∣ 1 1 n n (Víme, že ∣ M∣ ≤ ⌊n /2⌋ ⇒ n ≥ n ) ⌊ n/ 2 ⌋ ∣ M∣ 1≥ ∑

 

R∈R je tvořena ∅ , {x 1 },{x  1 , x 2 }, ... a ∣R∣=n! . Víme ∣ A∩R∣ ≤1 .

4

  

 

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey =∣ A∣⋅



1 ⇒ n ≥∣ A∣ ⇒ n ≥Bn  ⌊n/ 2⌋ ⌊n /2 ⌋ . Q.E.D. n ⌊ n /2 ⌋

  





(přednáška 11.3.09)

Princip inkluze a exkluze Věta:

PIE n

∣∪ A ∣= i

i=1

∑

−1 J −1⋅∩ Ai ∣ ∣

∅≠J ⊆{1 ,... ,n }

∣

∣

i ∈J

Důkaz první: indukcí. Pro 1 a 2 platí. Indukční krok n ⇒ n1 .

∣∪ A∣=∣∪ A ∪ A 1∣=∣∪ A ∣∣ A ∣−∣∪ A ∩A ∣ = n 1 i =1

=

∑

∅≠ J ⊆{1 ,... , n}

n

i

i= 1

n

i

n

−1∣J∣−1⋅∩ Ai ∣ An 1∣−

∣

i ∈J

n

i

i=1

∣

n1

∑

∅≠ J ⊆{1 ,..., n}

i

i =1

n 1

∣ ∣ ∣ ∣= ∑ −1 ⋅∩ A − ∑ −1 ⋅ ∩ A ∣= ∑  ∣ ∣ ∣

−1∣J∣−1⋅∩  Ai ∩A n 1

∣

i∈J

∑

∅≠ J ⊆{1 ,... ,n }

n

−1∣J∣−1⋅∩ Ai ∣ An 1∣− ∪  Ai∩ A n1  =

∣

i ∈J

i= 1

∣J ∣−1

∣ J ∣'−2

i

i∈J

∅≠ J ⊆{1 ,... , n1 }

i∈J '

∅≠J '⊆{1 , ..., n1 }

n 1∉J

i

∅≠ J⊆ {1 ,... ,n }

−1∣J∣−1⋅∩ Ai

∣

i ∈J

∣

n1 ∈J

Q.E.D. n Důkaz druhý: pomocí binomické věty  x y  =

∑

j⊆{1 ,..., n}

x ∣J∣⋅yn−∣J∣ .

n

Nechť x ∈∪ A i a je prvkem právě množin Ai , ... , A i , BÚNO Ai =A 1 , ..., Ai = A k . 1

i =1

k

1

k

n

∑ −1n −∣ J∣⋅1 , to má být rovno 1. ⇒ ∑ −1i−1⋅ n =n− n  n − n ... x přispívá k pravé straně ∅≠J ⊆{1 ,... ,k } i 2 3 4 i= 1 n − n  n − n ...≈ 0= Platí počet podmnožin sudé velikosti – počet podmnožin liché velikosti. Q.E.D. 0 1 2 3 Příklad:Pravděpodobnost, že permutace 1 , ... , n nemá pevný bod. Permutace bez pevného bodu je bijekce p: {1 , ..., n} {1 , ... , n} , kde ∀ i : pi ≠i Počet všech permutací je n! . Označme P množinu všech permutací a V množinu permutací bez pevného bodu. Pak

n

A ∪ i=1 i

V=P∖

, kde Ai ={ p ; p i=i } .

perm.s ≥1 pevným bodem

n

∣ ∣

∣V ∣=∣ P∣− ∪ Ai =n!− i= 1

∑

−1∣J∣−1⋅

∅≠ J ⊆{1, ..., n}

A i∣ ∩ ∣ i∈J

=n!

n n −1i −1∣ J∣⋅n−∣ J∣!= ∑  n ⋅−1i⋅n−i!= ∑ n!⋅ i! ∅≠J ⊆{1,... ,n } i=0 i i =0

∑

={ p ∀i ∈J : p i=i } n

−1 i 1 Pravděpodobnost ∑ n!⋅ i !   e. i=0 n ∞ (přednáška 18.3.09) n

Úloha:

∑ i=0

2



n =? i

n

n

=1 x  ⋅1x  =

2⋅n

(a) 1x  =∑ 2⋅n ⋅x ... k k=0 2⋅n

n

k

 2⋅nn 

n

k l ∑  n ⋅x ⋅ ∑  n ⋅x  (b)  k=0 k l=0 k  ... x k n

Úloha:

  

i −1 ⋅ n ⋅ n =? ∑ i n−i i=0

... x n −k

n

n

n

=1− x  ⋅1x  =

n

k k l (a) ∑  n ⋅−1  ⋅x ⋅ ∑  n ⋅x  k l k=0 l= 0 n

(b) 1−x  = ∑  n ⋅−x  k= 0 k 2 n

n liché

0

n n sudé k= 2

n n  n ⋅−1 2 2

 

n

Úloha:



n

∑ i⋅ ni =∑ i⋅ ni =? i=0 i=1 n n n i n−1 n 1x  =∑  ⋅x ⇒ n⋅1 x =∑  n ⋅i⋅x i−1  i=0 i i=1 i derivace 5

2 k

n

...

n

2

 n ⋅ n =∑  n  , a=b  ∑ n−k k =0 k k= 0 k

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey n

Dosadíme x=1 :

∑  ni ⋅i=n⋅11n−1=n⋅2 n−1 i=1

n

 x y n=∑  n ⋅x i⋅y n−i i=0 i

Opak.: Binomická věta

Multinomická věta:

∑

x 1...x p n=

p

 k 1 ,...,k p∈ℤ 0 ; ∑ k i =0 ∞

Zobecněná binom. věta:





k k n n! n ⋅x 1 ⋅...⋅x p = , kde k 1 , ..., k p k 1 , ..., k p k 1!⋅...⋅k p ! 1



p



i=1

r⋅r −1⋅r−2⋅...⋅r−i1 r r i 1x  =∑ r ⋅x , kde r = ; =1 i! i 0 i=0 i







Vytvořující funkce ∞

Def.:

∞ Uvažme posloupnost reálných čísel a n 0 . Vytvořující funkce je mocninná řada a  x =∑ ai⋅x . i

i=0

i

Pokud existuje k∈ℝ takové, že pro všechna i≥1 je ∣ai∣≤k , potom mocninná řada a  x =

∞

∑ a i⋅x i konverguje pro x ∈− 1k , 1k  . i=0

1 =1 x 2x 3... konverguje na −1,1 (posloupnost 1,1 ,1 ,1,... ). 1−x

Př.:

Postup: Operace s mocninnými řadami

a  x =∑ ai⋅x i

b0 , b1 , b 2 , ...

b  x=∑ bi⋅x

1.

Sčítání:

2.

Násobení

3.

∞

a 0 , a 1 , a 2 ,...

i=0 ∞

i

i =0

6.

a  x b  x ⇔a 0b 0 , a 1b1 ,... ∈ℝ : ⋅a x⇔⋅a 0 , ⋅a 1 , ...

Přidání n nul na začátek:

n

Derivování (integrování):

a '  x ⇔a 1 , 2⋅a 2 ,3⋅a3 ,... x

∫ a t ⋅dt ⇔C , a0 , 12⋅a1 , 13⋅a 2 ,...

n

Posunutí doleva:

0

8.

n−1

a  x −∑ a i⋅xi

Násobení: ∞

k

i =0

i=0

a  x ⋅b  x=∑ c i⋅x i , kde c k =∑ a i⋅b k−i

i=0 n

⇔ a n , a n1 ,... x 5. Dosazení ⋅x za x: 0 1 2 a ⋅x⇔ ⋅a 0 ,  ⋅a 1 ,  ⋅a 2 , ...

c 0=a0⋅b0 , c 1=a 0⋅b 1a 1⋅b 0 , c 2=a 0⋅b2 a 1⋅b1a 2⋅b0 , ...

Fibonacciho posloupnost (zatím vynecháno)

Binární stromy Def.:

n

a  x ⇔ a0 ,  0, ...,0 , a 1 ,  0,... ,0 , a 2 ,... 7.

x ⋅a  x ⇔0 ,... , 0 , a 0 , a 1 , ... 

Př.:

n x za x:

n

n

4.

Dosazení

Binární strom (rekurentní definice) (a) prázdný (0 vrcholů) (b) s jedním vrcholem (kořen) (c) kořen a uspořádaná dvojice binárních stromů

Úloha: Hledáme b n počet binárních stromů s n vrcholy.

∞

b0 ,b 1 , b 2 , ... má vytvořující funkci b  x=∑ bi⋅x

i

i =0

6

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey Pro n≥1 : b n= počet dvojic B L , BP  , kde B L , B P jsou binární stromy a ∣V B ∣∣V B ∣=n−1 . L

P

n −1

b n=∑ bk⋅b n−1−k ⇒* k =0

n

b  x⋅b  x =c 0c 1⋅xc2⋅x 2...=b 0b1⋅xb2⋅x 2...2 , kde c n=∑ bi⋅b n−i i =0

1±  1−4⋅x *⇒ b x=x⋅b  x 1⇒ x⋅b  x −b  x1=0⇒ b1,2  x= 2⋅x 1 1−4⋅x b1  x= ...lim b1  x =∞ , to nemůže být součet konvergentní řady. 2⋅x 1−  1−4⋅x Zbývá tedy b 2  x = :=b x . 2⋅x 1 ∞ 1 2 1−4⋅x=1−4⋅x  =  ∑ 2 ⋅−4⋅x k k =0 k 1 Koeficient u x 0 je 2 =1 . V 1− 1−4⋅x je nultý absolutní člen. 0 ∞ 1 ∞ 1 1 1 k k −1 i1 k−1 To lze vydělit 2⋅x a dostáváme b  x=− ⋅∑ 2 ⋅−4  ⋅x =∑ − ⋅ 2 ⋅−4 ⋅x , 2 k =1 2 i=0 k i1 1 1 3 1 ⋅− ⋅− ⋅...⋅ −n n1 1 1 2 2 2 2 4 n 1 n2 tedy b n=− ⋅ 2 ⋅−4 = ⋅ ⋅−1 = 2 n1⋅n! 2 n1 2

2







 

 

n2 členů

 1 1 3 2⋅n−1 1 2⋅n 2 ⋅ ⋅ ⋅...⋅ ⋅ ⋅2 =

2 2 2

2 2 n1⋅n!

=

2 4⋅12⋅3 4⋅56⋅...⋅2⋅n−12⋅n 1 2⋅n! 1 = ⋅ = ⋅ 2⋅n  2 n1⋅n! n1 n! n1 n

(Catalanova čísla) Opak.: Teorie pravděpodobnosti, zde vynecháno.

Halleova věta, Systém různých reprezentantů Def.:

Mějme množinový systém M=M i ;i =1 , ..., n , kde M i je konečné. n

Systém různých reprezentantů je prosté zobrazení f : {1 ,..., n }∪ M i , i= 1

kde pro všechna i=1, ... , n je f i∈M i . Př.: Def.:

M 1={1 ,2,3}; M 2={1,4 ,5 }; M 3={2 ,5}; M 4={1,3 ,5}

Mějme graf G=V , E  . F⊆ E se nazývá párování v grafu G, pokud pro všechna v∈V ; f , f ' ∈F : v∈f ∧v ∈f ' ⇒ f =f ' .

Úloha: Máme

M množinový systém, n

G bipartitní graf s partitami {1 , ..., n} a ∪ M i a i=1

e∈E G ⇔e={i , x }, x ∈M i . M=M i ;i =1 , ..., n nemá SRR, pokud existuje I ⊆{1 , ..., n} takové, že

Druhý případ:

7

n

∣∪i=1 M i∣∣I∣ .


Halleova M=M i ;i =1 , ..., n má SRR

⇔ ∀ I ⊆{1 , ... , n}:∣I ∣≤ ∪ M i

∣

i∈ I

∣.

Halleova podmínka

Důkaz:

⇒ jasné

položíme M'=M i ; i=1,... , n−1 .

n

Dle předpokladu věty pro I ⊆{1,... , n−1} platí H.P.

⇐ matematickou indukcí dle ∑ ∣M ∣=k : i

i=1

n −1

a

(1) Předpokládejme, že ∃ J ⊂{1, ..., n}, J ≠∅ ,∣ J ∣= ∪ M j .

∣

∣

j∈ J

i=1

Položme J ' ={1 , ... , n}∖ J ; MJ =M j ; j∈J  ;MJ ' =M j ' ; j ' ∈ J '  . Pozorování: ∀ i=1,... , n: M i≠∅ . MJ splňuje Halleovu podmínku a

∣∪ M ∣k . j

j ∈J

M'=M i ' ;i=1,..., n  splňuje Halleovu podmínku:

Dle indukčního předpokladu: MJ má SRR. M'=M i ∖ ∪ M j  ;i∈ J ' j ∈J 

Položíme

I '⊆ J ' : ∪ M i ' =

∣

i ∈I '

∣∣∪

i ∈I '∪J

Mějme I ⊂{1,... , n} .

, pak

M i'

∑ ∣ M j '∣k

Protože nenastala (1): ∣ I∣≤ ∪ M i −1 a

∣

j ∈J '

j ∈J

∣

i∈I

∣∪ M '∣≥∣∪ M ∣−1 , i

i∈I

i ∈I

i

tedy ∣ I∣≤ ∪ M i ' .

∣

M i − ∪ M j ≥∣ I ' ∪ J∣−∣ J ∣=∣ I '∣∣ J∣−∣ J∣=∣ I '∣

∣ ∣

∑ ∣M i∣k … dle indukčního předpokladu existuje SRR pro M' .

(3) nenastane-li (1) ani (2): x budiž libovolný prvek M n . M proi =1, ..., n−1 Položíme M i ' = i . M i ∖ {x}pro i=n

∣

∣

i∈I

⇒ M' splňuje Halleovu podmínku.

Zbývá ověřit

n

(2) Předpokládejme, že ∃ x∈∪ M i takové, že existuje právě jedno j, že

∣∪ M '∣≥n , ale protože nenastala (2), n

i

i=1

tak ∃in : x ∈M i ⇒ x ∈M ' i a

i= 1

x ∈M j (BÚNO j=n ).

n

n

M i '=∪ M i . ∪ i=1 i=1

n

Zároveň

Zvolíme x jako reprezentanta M n a

∑ ∣M i '∣=k −1k a dle indukčního předpokladu i=1

má M' SRR a ten je SRR pro M ( M i ' ⊆M i ). Q.E.D.

Tvrz.: Nechť G je bipartitní graf s partitami V 1 , V 2 a E≠0 , pro všechna x ∈V 1 , y ∈V 2 platí, že deg  x≥deg  y . Pak existuje párování F v G takové, že pokrývá V 1 . Důkaz: V 1 ={x 1 , ..., x n }, V 2 ={y 1 ,... , y n }

Označme k 1 =min {deg x j ; j∈J } ,k 2=min {deg y; y ∈S J } .

Položme M= M i ; i=1,... , n tak, že M i ={y j ; {x i , y j }∈E } ,

Platí k 1≥ k2 0 :

Mj . J ⊆{1, ..., n } , S J ={y ∈V 2 ;∃ j∈ J : {x j , y}∈ E }= ∪ j∈ J

∑ deg  x j≥ k1⋅∣J∣ ; ∑ deg  y≤k 2⋅∣S J∣ j ∈J

⇒ k 1⋅∣ J∣≤k 2⋅∣ S J∣ ⇒

Chceme, aby platila Halleova podmínka: ∣ J ∣≤∣S J∣

≥1

Počet hran G [ {x j ; j ∈ J }∪ S j ]= ∑ deg  x j ≤ ∑ deg  y  j ∈J

Př: Def:

y∈S J

Latinské čtverce a obdélníky Latinský čtverec řádu n≥1 je matice A řádu n×n taková, že pro všechna i , j : a i , j ∈{1,..., n} a pro všechna i , r , s , r≠s: a i , r ≠ai ,s ∧ar ,i ≠a s , i n

Úloha: Odhad počtu latinských čtverců:

∏  k!

n k

≥L n≥

k =1

Def:

y ∈S J

k1 ⋅∣ J ∣≤∣S J∣ ⇒ Halleova podmínka platí, Q.E.D. k 2

 n!2⋅n nn

2

Latinský obdélník řádu k×n1≤k≤n je matice A ' typu k ×n , která splňuje podmínky latinského čtverce.

Tvrz.: Každý latinský obdélník k×n lze doplnit na latinský čtverec n×n . Důkaz:

1≤ kn rozšíříme o řádek k 1 :

Otestujeme již jen Halleovu podmínku: ∣ J ∣≤ ∪ M j , J ⊆{1 ,... , n} :

∣

A '=a i , j ; i =1,... , k ; j=1,..., n .

j ∈J

∣

Definujeme G bipartitní graf s partitami {x 1 ,... , x n },{ y 1 ,... , y n} ,

Hledáme a k 1 doplňující A ' na latinský obdélník k 1×n .

kde {xi , yi }∈ E ⇔ j∈ M i .

Položíme M j={1,... , n}∖ {a 1, j ,... , a k , j } ,

Platí:

M= M j ; j=1 ,... , n a f :{1 ,... , n} {1 , ... , n} SRR pro M .

∀ i=1 , ... , n:deg  x i =∣M i∣=n−k =a ∀ j=1 ,... , n :deg  y j=∣M i∣=n−k =b , b≤a .

Definujeme a k 1, j= f  j . Toto je korektní rozšíření A ' .

Dle předchozího tvrzení existuje SSR pro M , Q.E.D.


Konečná projektivní rovina Def.:

,P , kde X je konečná neprázdná množina, P⊆2 X a platí axiomy ∃č ∈ X :∣č∣=4 ; ∀ P ∈P:∣P∩č∣≤2 P 1 , P 2 ∈P , P 1≠P 2 ⇒∣ P1∩ P 2∣=1

Konečná projektivní rovina je dvojice  X (P0) (P1)

8

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey (P2) Tvrz.:

∀ x1 , x 2 ∈X , x 1≠ x 2 ⇒∃! P∈P: x1 , x 2 ∈P

 X ,P je KPR, potom ∀ P 1, P 2 ∈P:∣P 1∣=∣P 2∣ . Důkaz: P 1≠ P 2 . Dle (P0) existuje č ={a ,b , c , d } , kde platí:

Oindexujeme P 1={x , x 1 , ... , xn } , položíme Ri = yx i , i=1 ,... , n .

(a) existuje jeden bod ∉P 1 ∪P 2 anebo

Ri ∩P 2 = x ' i≠ x , jinak ∣ Ri ∩P 1∣≥2 ⇒ SPOR, i≠ j⇒ x ' i≠ x ' j , jinak ∣ Ri ∩R j∣≥2⇒ SPOR,

(b) body jsou na P 1, P 2 po dvou, BÚNO P 1=ab , P 2=cd . Uvažme přímky Q1=ac ,Q 2=bd .

tedy ∣ P 1∣≤∣ P 2∣ . Analogicky dokážeme ∣ P 1∣≥∣ P 2∣ ⇒∣ P 1∣=∣P 2∣ , Q.E.D.

Dle (P1) existuje y ∈ X : y ∈Q1 ∩Q 2 ∧ y ∉ P 1 ∪P 2 

Def.:

Řád KPR  X

,P je roven ∣P∣−1 pro P ∈P .

Tvrz.:

 X ,P je KPR řádu n, potom platí: (0) ∀ P ∈P:∣P∣ =n1 (1) ∀ x∈ X :∣ {P ∈P; x∈ P }∣=n1 (2) ∣ X ∣=n2 n1 2 (3) ∣P∣=n n1 Důkaz: (0) z definice (1) Vezměme libovolný x ∈ X . Dle (P0) existuje a ,b , c∈č ∖ {x } ,

(2) Vezměme libovolnou P∈P , P={x0 , ..., xn }, a∉ P libovolný. Položme P i=ax i ; i=0 , ... , n−1 .

že ab∩ac={a} ⇒ x ∉ab ∨ x∈ac .

n

∣∑ ∣

∃P ∈P: x∈ P , označíme toto P={a 0 ,... , a n } a P i=a i x ;i=0 , ..., n .

i =1

P i =n1⋅n1−n=n 2 n1 .

(3?) Ať je b∈ X . Pro b=a …ok, jinak:

Ať Q ∈P: x ∈Q ⇒∣Q∩ P∣=1 , tedy existuje i: ai ∈Q .

Položíme Q=ab ⇒ P i ∩Q ={xi} a zároveň

{x , a i }⊆P i ∩Q ⇒ P i=Q

a , x i ∈Q ⇒ Q= P i , Q.E.D.

Def.:

Dualita je  A , M , kde M⊆2 . A

M,B je duální systém pro B={{M ∈M; a∈M }, a∈ A} . Tvrz.: Duální systém ke KPR řádu n je KPR řádu n. Pozn., jako důsledek má (3) v předchozím tvrzení. Důkaz:  X , PP, T ; T=T x ; x ∈ X ; T x={P ∈P; x ∈ P }

(P1)* ∀ x , y∈ X , x ≠ y :∣T x∩T y∣=1 (P2)

(P0)* ∃P 1 , ... , P 4∈P různé, tž. ∀ x∈ X :∣T x∩{P 1 , ... , P 4 }∣≤2 .

T x∩T y={P∈P; x ∈P , z∈ P} ⇒  ∃! P ∈P: x , y ∈ P

 X , P je KPR ⇒∃č ⊆ X :č ={a , b , c , d } .

(P1)

(P2)* ∀ P P ∈P , P ≠P ⇒ 1, 2 1 2  ∃! x : x∈ P 1 ∩P 2

P 1=ab ; P 2 =bc ; P 3=cd ; P 4=da , ať x ∈P 1 ∩P 2 ∩P 3 .

P 1 , P 2 ∈T x . Ať P 1 , P 2 ∈T y pro x≠ y ⇒ y ∈ P 1∩ P 2 ⇒ SPOR. Q.E.D.?

Pak x ∈P 1 ∩P 2 ⇒ x =b ; x ∈P 2∩ P 3 ⇒ x =c , SPOR. Žádné tři přímky nemají jeden společný průsečík.

Konstrukce KPR Př.: Věta:

Nechť n= p e , kde p je prvočíslo, e≥1 . Potom existuje KPR řádu n. Důkaz: Existuje F těleso s právě n prvky.

(P0) č ={0,0, 0,1 ,1,0 ,1,1} , ∀ P∈P:∣č ∩P∣≤2 (P1) P 1= P   , P 2 =P  

X ={ x , y ; x , y ∈ F}∪{* , y ; y ∈F }∪{* , *} P:

Def.:

Tvrz.:

1

1

2

2

 ,  ∈F : P   ={ x , ⋅x ; x ∈F }∪{* , }

 1= 2 ⇒* ,  1⊆P 1 ∩P 2

∈ F : P ={  , y ; y ∈F }∪{* , *}

 1≠ 2 ⇒ 1⋅x1= 2⋅x2 ⇒ x=2 −1 =1 − 2

P *={* , y  ; y∈ F }∪{* , *}

 x ,  1⋅x 1∈ P 1∩ P 2 , Q.E.D.

Latinské čtverce A, B řádu n jsou ortogonální:

A⊥ B ⇔∀ i , j , i ' , j ' ,i , j≠i ' , j' ⇒ ai , j , bi , j ≠a i ' , j ' , bi ' , j '  A1 ,... , Am budiž navzájem po dvou ortogonální latinské čtverce řádu n, pak m≤n−1 .

Důkaz: Mějme A⊥ B latinské čtverce řádu n,

BÚNO je první řádek Ai =1, ... , n pro i1,... , m ,

∈ S n ; A '=a ' i , j ni , j =1 , a' i , j =a i , j .

tedy např.  Ai 2,1≠1 a pro i≠ j : Ai 2,1≠ A j 2,1 ⇒ m≤n−1 , Q.E.D.

Potom A ' ⊥ B .

9

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey (přednáška 15.4.09)

Věta:

Pro n≥2 existuje KPR řádu n, právě když existuje n−1 vzájemně ortogonálních latinských čtverců řádu n. Dále konstruujeme přímky dle latinského čtverce:

Důkaz: Mějme A1 , ... , A n −1 ortogonální latinské čtverce řádu n,

a=1 , ..., n−1; b=1 ,... , n ⇒ La ,b ={l a }∪{xi , j ; A a i , j=b}

 X , P KPR řádu n. Zde platí následující: 2

∣ X ∣=∣P∣=n n1; ∀ P∈P:∣P∣=n1 ;∀ x ∈ X :∣{P∈P; x∈ P }∣=n1 . Zvolíme r, s libovolné body, P=rs , ostatní body označíme l 1 ,... , l n−1 . Budiž

P 1 ,... , P n přímky tž. r ∈P i , s∉ P i , i=1,... , n a

a=c ⇒ L a ,b∩ Lc , d ={l a }

a≠c ⇒ Aa ⊥ A c ⇒∃! i , j: x i , j : Aa  i , j =b ;  Ac i , j=d – OK. (P2) Zřejmé. Q.E.D.

Označme ∀ i , j=1 , ... , n: x i , j= P i∩Q j průsečík.

Mějme n mocninu prvočísla, potom existují

P i∩ La , b :∃! j : A a i , j=b – OK. La ,b∩ Lc , d :

Q1 , ..., Qn přímky tž. s∈Q i , r ∉Qi ,i=1, ..., n ,

Věta:

Ověříme axiomy: (P0) č ={x 1,1 , x1,2 , x2,1 , x 2,2} (z obr.) (P1) P s ostatními – OK. P i∩Q j dle definice – OK.

A1 ,... , An−1 navzájem ortogonální latinské čtverce řádu n.

Důkaz: Mějme K komutativní těleso řádu n.

ještě zbývá ověřit k ≠k ' ⇒ A k ⊥ A' k .

Označme prvky t 0=0 , t 1=1 , ..., t n −1 ,

, j , i' , j' : A k i , j ,  A k ' i , j = A k i' , j ' ,  A k ' i ' , j '  . Ať ∃i

k =1 , ..., n−1 ;i , j=0 , ..., n−1 a budiž  Ak  i , j =t k⋅t it j .

různé

t k⋅t it j=t k⋅t i' t j ' ; t k '⋅ti t j=t k ⋅t ' i ' t j '

Je A k latinský čtverec?

t i⋅t k −t k ' =ti '⋅t k −t k ' ⇒ t i =ti ' ; t j =t j' ⇒ i=i ' ; j= j ' , SPOR. Q.E.D.

V i-tém řádku jsou prvky t k⋅t it 0 ,t k⋅t it 1 ,... , t k⋅ti t n−1 různé,

≠0

v j-tém sloupci jsou prvky t k⋅t 0t j , ..., t l⋅t n−1 t j různé,

Bloková schémata X

Def.:

Nechť X je konečná množina, B⊆2

Př.:

(1) Triviální blokové schéma:

Věta:

Ať existuje blokové schéma typu t−n , k ,  , potom jsou následující zlomky celočíselné:

; n , k ,t ,∈ℤ , nk t≥1, ≥1 , pak  X ,B je blokové schéma typu t−n , k ,  , pokud platí (1) ∣ X ∣=n (2) ∀ B∈B:∣ B∣ =k X (3) ∀ T ∈  existuje přesně  množin Bi ,i=1 , ... , , že B i ∈B, T ∈ Bi . t

∣ X ∣=n ,B= X  , = n−t  k k−t (2) KPR řádu n  K ,P je zároveň blokové schéma typu 2− n2 n1, n1,1 (3) Blokové schéma typu 1−n , k ,1 existuje, právě když k∣n . n⋅n−1⋅...⋅ n−t1  n−1⋅...⋅n−t1 n−t1 ⋅ ,⋅ , ... , ⋅ . k⋅k −1⋅...⋅k −t1 k −1⋅...⋅k −t1 k −t1

n⋅n−1⋅...⋅n−t1 Důkaz:  X , B dle zadání, platí ∣B∣ =⋅ . k⋅ k −1⋅...⋅k −t1 Zvolme S ⊆ X ,∣ S∣=s≤t a počítejme počet dvojic T , B  X takových, že S ⊆T ∈  , T⊆ B⊆B : t n−s  (a) S lze na T rozšířit  způsoby, T je v  blocích. t−s

T ∈ X  takových, že S ⊆T⊆ B . t Tedy počet bloků obsahujících S je

n⋅n −1⋅...⋅n−s−t s1 ⋅ n− s  t− s t −s ! =⋅ k⋅k −1 ⋅...⋅k−s −t s 1 celé číslo  k −s  t −s ! t−s Q.E.D. s=0 , ... ,t−1

k −s  (b) libovolné B takové, že S ⊆B , obsahuje  různých t−s

Def.:

Steinerovské systémy trojic jsou bloková schémata typu t=2, =1, k =3 .

Př.:

Fanova rovina, KPR řádu 2... KPR řádu 3 bez bodů jedné přímky afinní rovina


Toky v sítích Def.:

Síť je G , s , t , c  , kde G je orientovaný graf V

(a) , (b)

,E , 10

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey s , t∈V , s≠t (s: source, zdroj, start, t: target, spotřebič, stok) a c : E ℝ +0 (kapacita). Def.:

Tok je

f : E ℝ0+ taková, že

∀ e∈E : f e≤c e a ∀ v∈V , v≠s ,t : ∑ f  x , v =  x ,v ∈E

Velikost toku je ∣ f ∣=

∑

s , x

∑

v , x∈ E

f v , x  .

f  s , x − ∑ f  x , s= ∑ f  x , t− ∑ f t , x  . x , s

x , t 

 t , x

☼:

Pro všechny sítě existuje tok.

Věta:

Pro každou síť existuje maximální tok.

Pozn.,

do odvolání uvažujeme BÚNO G souvislý (v rámci této přednášky).

Def.:

Řez mezi s a t je R⊆ E taková, že v síti G ' , s , t , c '  neexistuje žádná orientovaná cesta ze s do t, kde G ' =V

Def.:

Je-li A⊆V , s ∈ A , t∉a , označme R A , V ∖ A:={e∈E ; e=a Potom R A , V ∖ A je řez a nazývá se elementární řez.

Def.:

Mějme G , s , t , c  síť, f tok, ať

, E ∖ R .

,b , a∈ A , b∉A} .

s=v 0 , e1 , v 1 , ... , v k−1 , e k , v k =t je neorientovaná cesta ze s do t, že i≠ j : v i ≠v j ; e i = v i−1 , v i  ∨ e i = vi , v i−1  . f e i c e i  pro e i=v i −1 , v i  a nenasycená (vylepšující), je-li f e i 0 pro e i=v i , v v−1 ,

Tato cesta je

nasycená jinak. Lemma:Mějme G , s , t , c  síť, f tok. f je maximální, právě když neexistuje vylepšující cesta ze s do t. šlo prodloužit vylepšující cestu do b)

Důkaz: Ať s=v 0 , e 1 , v 1 ,... , v k −1 , e k , v k =t je vylepšující cesta.

c  R= ∑ c e = ∑ f e  ≥  ∣ f∣

{c e i− f e i }0 , ⇒ Položme 1= e min =v ,v  i

2 =

min

e i=v i ,vi −1

f ' e =

i −1

e∈ R

e∈R

(*)

i

Ať R' je libovolný řez a f' je libovolný tok, potom ∣ f '∣≤∣c  R ' ∣ .

{ f e i }0 ; =min {1, 2 }0 a konečně

Protože ∣ f ∣ =∣c  R∣ , tak f je max. Q.E.D. (*) Nerovnost:

f e , pokud e≠ei , i=1 , ... , k , f e , pokud e=e i =v i−1 , v i  ,

∣ f ∣ =∑  ∑ f v , x − ∑ f  x , v= ∑ v ∈A v , x

f e− , pokud e=e i =v i , v i−1  .

 x , v

∑

v ∈A v , x 

f v , x − ∑

∑

v∈ A x , v

∑ f a , b− ∑ f b ' , a ' ≤c  R .  

Platí, že f ' je tok, ∣ f '∣=∣ f ∣∣ f ∣ , SPOR.

e =a ,b

e= b ' ,a ' 

c  R

⇐ A={v ∈V ;∃vylepšující cesta ze s do v }, s∈ A , t∉ A ,

≥0

Platí e=b , a , b∉ A , a∈ A ⇒ f e =0 a tedy

potom R A , V ∖ A je řez.

∑

e∈ R

f  e=∣ f ∣ .

e ∈R , e= a , b , a∈ A , b∉ A⇒ f e =c e (jinak by

Důsl.:

∣ f ∣≤min c  R . max f tok R řez

Věta:

Nechť G , s , t , c je síť, pak

∣ f ∣=min c  R . max f tok R řez

≤ Již máme. Pro spor ať f je maximální tok,

A={v ∈V ;∃vylepšující cesta ze s do v }, s∈ A , t ∉ A a

R minimální řez, ale ∣ f ∣ c  R .

Alg.: Ford-Fulkerson (pro c e ∈ℤ ∀ e ) 1. ∀ e : f e =0 2. Existuje-li vylepšující cesta ze s do t, 3. Důsl.:

R A , V ∖ A je řez c  R A , V ∖ A=∣ f ∣c  R , SPOR. Q.E.D.

zvětšíme tok podél cesty a opakovat (2).

Tok je maximální, konec. Je-li G , s , t , c síť s celočíselnými kapacitami, potom existuje celočíselný maximální tok. ⇒ Je-li G , s , t , c síť a ∀ e :c e ∈ℚ , potom existuje maximální tok.

11

f  x , v

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey n

f :{1 , ... , n }∪ M i a ∀ i∈{1 ,... , n }: f i∈M i . SRR odpovídá párování velikosti n. n

i =1

X =∪ M i ; i , x∈E ⇔ x∈ M i . i =1

Budiž f celočíselný tok ∣ f ∣≤ n , E∩{e ; f e=1 } je párování. SRR existuje, právě když existuje celočíselný tok velikosti n. Úloha: Kapacita na vrcholech.

Míra souvislosti v grafech Def.:

Mějme graf G=V , E , k ∈ℕ . G je vrcholově k-souvislý, pokud ∣V ∣≥k 1 a pro ∀ U ⊆V :∣ U ∣≤k −1 je G ∖ U souvislý. G je hranově k-souvislý, pokud pro ∀ F ⊆E :∣ F∣ ≤k −1 je G ∖ F souvislý. U ⊆V je vrcholový řez, je-li G ∖ U nesouvislý. F ⊆E je hranový řez, je-li G ∖ F nesouvislý. Vrcholová souvislost je k V G=min {∣U ∣ ; U vrcholový řez } , pokud G≠K n , jinak k V  K n =n−1 . Hranová souvislost je k E G =min {∣ F∣ ; F hranový řez}

Lemma:Mějme G=V

, E  , e∈E , pak k E G −1≤k E G−e ≤k E G  .

Důkaz: Uvažme F minimální hranový řez. F ' =F ∖ {e } je řez G−e , ale nemusí být minimální.

Položme F'' minimální řez G−e , F ' '∪{e } je řez G.

∣ F ' '∪{e }∣ =∣ F ' '∣1=k E G−e 1 , Q.E.D.

∣ F∣−1≤∣F '∣≤∣F ∣ ⇒ k E G−e ≤∣F '∣≤∣F ∣≤k E G 

Lemma:Mějme G=V

≥k E G

, E , e∈E , pak k V G−1≤k V G−e≤k V G .

Důkaz: Uvažme U ⊆V minimální řez G.

e ∉E  H e ∖ U ' ⇒ H e ∖ U ' =H ∖ U '

G ∖ U není souvislý. Položme H :=G−e .

(2) ∃i: x , y ∉C i komponenta grafu H e∖ U '

1 kV  H ≥k V  H e  .

⇒ graf nesouvislý.

Vezměme U' minimální řez H, k V H =∣U '∣ .

(3) x ∈C 1, y∈C 2, r =2 a máme dvě možnosti:

H ∖ U má komponenty C 1 ,... , C r , r≥2 .

buď ∣C 1∣=∣C 2∣=1⇒ H e≃ K n ; k V H =n−2, k V  H e =n−1

e={x , y } a může nastat:

anebo ∣C 1∣≥2⇒ C 1 ∖ {x }, C 2 komponenty H e∖ U ' ∪{x } , Q.E.D.

(1) x ∈U ' nebo y ∈U '

Tvrz.:

k V G≤k E G  Důkaz: indukcí dle ∣E∣

⇒ F ≠∅∧∃ e ∈F .

(1) ∣E∣ ∣V ∣−1⇒G nesouvislý, k V G=k E G =0 a dokonce platí pro každý G nesouvislý. (2) G souvislý, k E G≥1, F minimální hranový řez.

Položíme G ' :=G −e , dle I.P. k V G ' ≤k E G '  . Platí k E G ' =k E G −1 a k V G−1  ≤ k V G '   ≤ k E G ' =k E G−1 , Q.E.D. Lemma 2

I.P.

2-souvislost Tvrz.: Graf G=V

, E  je 2-souvislý, právě když ∀ u , v∈V ∃ kružnice v G, která obsahuje i v.

Tvrz.: Ušaté lemma Každý 2-souvislý graf lze sískat z kružnice přidáním uší, kde ucho je cesta, která má s původním grafem společné právě koncové vrcholy. Důkaz: G je 2-souvislý ⇒∣V ∣≥3, e={u , v }∈ E , k E G ≥k V G ≥2

(2) x ∈V G ' , y ∉V G ' ⇒ G− x souvislý.

G−e souvislý ⇒∃ cesta z u do v v G−e ⇒ Pe kružnice. G' maximální podgraf G vzniklý přidáváním uší ke kružnici. Ať existuje e ' ∈ E ∖ E G '  . Možnosti:

Buď P' cesta z y do V G  v G. Pak P 'e ' je ucho. OK (3) x , y ∉V G ⇒ ∃ cesta z x do V G '  v G. Buď e'' poslední hrana této cesty, e ' '={a , b}, a∈V G ' , b∉V G '  Převedeno na případ (2). Q.E.D.

(1) e ' ={x , y }, x , y ∈V G ' ⇒ e ' ucho v. OK

Věta:

Ford-Fulkersonova Mějme G=V , E , k ∈ℕ . Pak k E G ≥k ⇔ ∀ u , v ∈V Důkaz: ⇐ Ať F je minimální řez ∣ F∣k a

, u≠v ∃ k hranně disjunktních cest z u do v. u, v jsou v různých komponentách G ∖ F .

12

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey Existují P 1 ,... , P k hranně disjunktní cesty z u do v:

k ≤∣ f ∣≤∣R∣ ⇒∣ f ∣≥k a najdeme P 1 ,... , P k disjunktní cesty uv.

(1) k =1 : hrany s f =1 obsahují tok z u do v, tedy minimální tok je cesta z u do v. (2) k ≥2 : hrany s f =1 obsahují tok z u do v.

∀ i:∣ P i∩ F∣≥1⇒ ∃ei∈ P i∩ F :i≠ j ⇒ ei≠e j a tedy ⇒{e1 , ... , ek }⊆ F ,∣{e 1 , ... , ek }∣=k , SPOR. ⇒ Mějme G' síť, zdrojem budiž u, spotřebičem v, c≡1 , f maximální celočíselný tok v G' neobsahující kružnice délky 2, R minimální řez ∣ f ∣ =∣ R∣ . Položme F ={{x , y}; x , y ∈ R} .

Věta:

P 1 cesta z u do v. Na P 1 nastavíme f 1=0 , jinak f.

∣ f 1∣=∣ f ∣−1 a postup indukcí. Q.E.D.

Menger Mějme G=V , E , k ∈ℕ . Pak k V G≥k ⇔ ∀ u , v∈V , u≠v ∃k vrcholově disjunktních cest z u do v (až na koncové vrcholy). f maximální tok v síti, R maximální řez, že ∀ e ∈R ∖ F najdeme e ' :e=x ' ' , y '  .

Důkaz: ⇐ Ať U je minimální vrcholový řez ∣U∣k , u, v v různých komponentách G ∖ U . Existují P 1 ,... , P k vrcholově disjunktní cesty z u do v a ∀ i:∣ P i∩U∣ ⇒∃v i∈ P i∩U :i≠ j⇒ v i≠v j .

Buď

x≠u : e ' = x ' , x ' '  jedna z nich

nebo

y ≠v :e ' = y ' , y ' '  .

 . Předpoklad: {u , v }∉E , jinak totéž v G −e

Pak {v1 , ..., v k }⊆U ,∣{v 1 , ... , v k }∣=k , SPOR.

{u , v}

⇒ Symetrická orientace v G,

Položíme R' =R bez hran e ∈R ∖ F , ale s e'.

∀ x∈V , x≠u , v : ...

∣ R'∣∣ R∣ , R' řez ⇒∣ R '∣=∣ R∣ , R ' ⊆F .

Zdroj u u ' ' , spotřebič v  v ' , c≡1 ,

U ={x ; x ' , x ' ' ∈ R ' }⇒U řez v G.

F ={ x ' , x ' ' ; x ∈V ∖ {u , v }} ,

k ≤∣U∣ =∣ F∣ . Q.E.D.

Ramseyovy věty Věta:

∀ n∈ℕ ∃ N ∈ℕ ∀ G=V , E  ,∣V∣=N : R n budiž minimální takové N.

K n⊆G ∨ E n ⊆G indukovaně. ∣V i −1∣

Důkaz: Ukážeme Rn≤4 n−1 .

∃V i⊆V i−1 ∖ {vi} , že buď ∀ v ∈V i :{v , vi }∈E ∧ ∣V i∣≥

Končíme s v 2⋅n− 1 a máme posloupnost v 1 , ... , v 2⋅n−1 takovou,

Vezměme v 2 libovolný vrchol z V 1 .

že ∀ i ∀ j i

∣V 1∣

∃V 2⊆V 1 ∖{v 2 } , že buď ∀ v ∈V 2 :{v , v 2 }∈ E ∧ ∣V 2∣≥

2

≥2

(pro ∀ v u vi víme, že je s nimi (ne)spojen) buď {v i , v j}∈ E ⇒ v i označíme ⊕ nebo {vi , v j}∉ E ⇒ v i označíme ⊖ . Existuje znaménko a existuje i1 , ... ,i n takové, že G [{v i ,... , v i }] je K n pro ⊕ anebo E n pro ⊖ .

Dále indukcí v i z v i −1 :

Tvrz.: Pro n≥4 je

1

n

≥2 2⋅n− 2−i

nebo ∀ v ∈V i :{v , v i }∉E

n −4

nebo ∀ v ∈V 2 :{v , v 2 }∉ E .

n

n 2

R n  2 =2 . n

1 n  E n :=P 2 ≤ N ⋅  2 . n 2

Důkaz: Mějme N =2 2 , G náhodný graf s N vrcholy a 1 {u , v }∈E s pravděpodobností 2 (nezávisle). n-prvková podmnožina vrcholů indukuje 1  n K n s pravděpodobností  2  2 , E n stejně tak. Pravděpodobnost, že G má indukovaný podgraf 1 n  K n :=P 1 ≤ N ⋅  2 a n 2

Věta:

2

Vezměme G=V , E  ,∣V ∣=2 2⋅n −2 , v1 libovolný vrchol z V. ∣V∣ −1 2⋅n−3 =2 ∃V 1⊆V ∖ {v 1 } , že buď ∀ v ∈V 1 :{v , v 1 }∈E ∧ ∣V 1∣≥ 2 nebo ∀ v ∈V 1 : {v , v1 }∉E .

K n nebo E n :=P I ≤P 1 P 2= 1 n  N! 1 Nn 1 =2⋅ N ⋅  2 =2⋅ ⋅ n −n ≤2⋅ n ⋅ n −n = 2 n! ⋅ N −n! n 2 2 2 2 2 2

n

2

2

−n 2

=21⋅2 2 ⋅2−n⋅2

n

⋅2 2 =2

1− n 2

2

1 .

Pravděpodobnost, že G nemá indukovaný podgraf K n nebo E n : n

P N =1−P I 0⇒ ∃ graf s 2 2 vrcholy bez K n , E n . Q.E.D.

∀ r ∈ℕ ∀ n 1 , ... , nr ∈ℕ∃ N ∈ℕ ∀ c : E K n {1 ,... , r }∃ i0 ∈{1 , ... , r }∃U ⊆V  K n ∀ u 1 ,u 2∈U :c {u1, u 2 }=i 0∧∣U ∣≥ ni

0

Česky: Pro každé r ∈ℕ a všechny r-tice n 1 , ... , n r ∈ℕ existuje přirozené číslo N, že pro libovolné obarvení c hran grafu K n pomocí r barev existuje barva i 0 a podmnožina vrcholů U taková, že hrana mezi každými dvěma jejími vrcholy má barvu i 0 a

počet vrcholů je alespoň n i0 . Uf.

Důkaz: Označme minimální takové N jako Rn 1 , ..., n r  , R r n .

(1) n 1=...=n r =1 stačí N =1 (existuje-li i, aby n i=1⇒ N =1 , triviální)

r

Tedy dále platí ∀ i: ni≥2 .

Dokážeme Rn 1 , ..., n r ≤1∑ R n 1 , ... , ni −1 , ni −1,n i1 , ... n r  i= 1

Ať v je libovolný vrchol, V i={u∈V ; n≠r , c {u , v }=i} .

r

indukcí dle

∑ ni :

∣V i∣≥R n 1 , ... , ni −1 , ni−1,n i1 , ... , nr  , použijeme I.P:

i=1

13

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey ∃i0 ∃U ⊆V i : i0 ≠i⇒ ni = i-tému z n1 , ... , ni −1 , ni−1,n i1 , ... , nr 

i0 =i⇒ U '=U ∪{v } ... Q.E.D. ?!

0

Věta:

 



∀ n , r , p ∈ℕ ∃ N ∈ℕ ∀ X ,∣ X ∣≥N ∀ c : X  {1 ,... , r} ∃i 0 ∈{1 ,... ,r } ∃Y ⊆X ,∣Y∣ ≥n : c Y ≡i 0 p p

Česky: Pro libovolná přirozená čísla n, r, p existuje N takové, že na libovolné množině X o velikosti N pro c libovolné obarvení p-tic jejích prvků r barvami existuje barva i 0 taková, že pro ni najdeme Y podmnožinu X velikosti alespoň n takovou, že na ní c je konstantně rovno barvě i 0 . Věta:

Nekonečná verze předchozí.

 



∀ r , p∈ℕ∀ X nekonečnou ∀ c : X  {1 ,... , r }∃i 0 ∈{1 ,... , r }∃Y ⊆X nekonečná :c ^ Y ≡i 0 p p Česky: Pro libovolná přirozená čísla r, p a pro libovolnou nekonečnou množinu X a pro c libovolné obarvení p-tic jejích prvků r barvami existuje barva i 0 taková, že najdeme Y nekonečnou podmnožinu X, že c parcializováno na Y je konstantně rovno i 0 . Důkaz: Indukcí dle p. (1) p=1: c : X  {1 ,... , r} triviální.

Existuje Y 2⊆Y 1 ∖ {x2 } nekonečná, že c ' ' ^







Existuje Y 1⊆ X ∖ {x1 } nekonečná, že c ' ^



Y 2 ≡c 2 . A tak dále: p−1



x i ∈Y i−1 : c  i : Y i− 1 ∖ {x i } {1 , ... , r}: c i {y 2 ,... , y p }=c {x i , y2 , ... , y p} p−1 i  Y i ≡c Existuje Y i⊆Y i− 1 ∖ {xi } nekonečná, že c ^ i . p−1

(2) p≥2 : X ={x 1 ,... } spočetná, x 1 : c ' : X ∖ {x 1 } {1 , ... , r} tak, že p−1 c ' {y 2 ,... , y p }=c {x1 , y 2 , ..., y p } .

 

 

Tím dostáváme nekonečnou posloupnost x 1 , x 2 ,... takovou,

 

Y 1 ≡c 1 . p−1

že ∀ i ∀ j p  j p −1... j 2 i : c {xi , x j ,... , x j }=c i . 2



x 2 ∈Y 1 : c ' ' Y 1 ∖{x2 } {1 ,... , r}: c ' ' {y 2 , ... , y p }=c{x2, y 2 , ..., y p} p−1

p

∃i0 takové, že pro nekonečnou I ⊆N : c i=i0 a Y ={x i ;i ∈ I } . Y =i Potom c ^ 0 a Y je nekonečná. Q.E.D. p



Pozn.: Odhady Ramseyových čísel Erdös-Szekeres (1935): Rödl (1986):

   



Rm1, n1≤ mn ; Rn ≤ 2⋅n−2 m n−1 2⋅n−2 n−1 Rn≤c1⋅ , c1, c 20 c log2⋅n−2 2⋅n −2 n−1 Rn ≤ n n 2 Rn ≥ ⋅n⋅2 2 e



2



Thomason: dolní odhad: Věta:



Erdös-Szekeres

∀ k ∈ℕ ∃ N ∈ℕ takové, že libovolná N-prvková množina bodů v rovině v obecné poloze (žádné tři neleží na přímce) obsahuje k bodů v konvexní poloze. Důkaz: Indukcí dle k. (1) k =4 : stačí N =5 . Pokud je konvexní obal pěti bodů 4 nebo 5-úhelník, OK. Pro 3-úhelník: ... (2) k 4 : buď X množina vodů (v obecné poloze) a

Věta:

 X4   konvexní / nekonvexní čtveřice. ∃Y ⊆ X : ∣Y∣=k ∧ Y stejného typu, dle (1) konvexní, tedy  4

buď c obarvení

Y je konvexní. Sporem, triangulujeme y bodů, je-li bod v trojúhelníku, spolu s ním tvoří čtveřici, která není konvexní. N ≥R  p=4, r =2,k  . Q.E.D.

Schur

∀ r ∈ℕ ∃ N ∈ℕ ∀ c : {1 , ... , N }{1,... , r } ∃ x , y ∈{1 ,... , N }, x≠ y : c  x =c  y=c  x y 

Důkaz: N : =R 2,r ,3 {1, ... , N } {1 ,... , r}: c ' {i , j}=c ∣i− j∣ Položíme c ' : . 2





x=− , y=− . Potom platí, že

c  x =c ' { , }=c 0 ; c  y=c ' {, }=c0 ; c  x y =c ' { , }=c0 Ale může nastat x= y ⇒ budeme hledat čtveřice, N :=R 2,r ,4 a

Najdeme  : c ' { ,  }=c ' { , }=c ' { , }=c 0 a

Věta:

pro x= y použijeme y '=− . Q.E.D.

∀ k ∈ℕ ∃G k bez trojúhelníků takový, že G k ≥k .

 

X Položíme X : ∣ X ∣= R2, k ,3 , V Gk = a 2

Důkaz: k 3

14

Kombinatorika a grafy I – Asymptotická notace, ČUM, PIE, Vytvořující funkce, Bin. stromy, SRR, KPR, Bloková schémata, Toky v sítích, Ramsey E Gk ={{{u , v },{x , y }}; uv= x y } .

⇒ x 2= x3 ∧ x 2 x 3 , SPOR.

G k nemá trojúhelník, sporem: {x1 , y 1 }, {x 2 , y 2}, {x3 , y 3 } ,

G k =? Buď c libovolné obarvení,

BÚNO x i y i , x1 ≤x 2≤ x 3 .

∃z 1 z 2 z 3 ∈ X , že v1 ={z 2 , z3 }, v 2={z 1 , z3 }, v 3 ={z 1 , z 2 } . Pak {v 1 , v3 }∈E ⇒c  v1 =c v 2  . Tedy G k k .

x 1 y1= x 2  y2 ; x 2 y 2= x3 y 3 ; x 1  y1= x 3  y3

To by mělo být všechno. Pokud najdete nějaké chyby, prosím oznamte mi je obratem na [email protected], pomůžete sobě, mně i všem ostatním, co výpisky užívají. Také se na mě obraťte v případě jakýchkoliv requestů na případné chybějící části apod. Zaantar.

15

Kombinatorika a grafy I

Recommend Documents