Kromě uvedených pojmů a tvrzení se u zkoušky můžete setkat i s počítacími nebo teoretickými příklady.
Pojmy
U následujících pojmů byste měli umět zformulovat definici a na jednoduchém příkladu ukázat, že té definici rozumíte.
vytvořující funkce
vytvořující funkce posloupnosti (an)n=0∞ reálných čísel je funkce proměnné x definovaná jako součet f(x)=∑n=0∞anxn
Catalanova čísla
binární strom je zakořeněný strom, jehož každý vnitřní vrchol má 2 potomky, na pořadí potomků záleží
Cn … počet binárních stromů s n vnitřními vrcholy
(Cn)n=0∞ jsou Catalanova čísla
rekurentní tvar
C0=1
Cn+1=∑i=0nCiCn−i pro n>0
explicitní vzorec: Cn=n+11(n2n)
projektivní rovina
projektivní rovina je hypergraf (X,P) takový, že platí tři axiomy:
A1: (∀x,y∈X,x=y)(∃!p∈P):{x,y}⊆p
dva různé body určují právě jednu přímku
A2: ∀p,q∈P,p=q:∣p∩q∣=1
každé dvě přímky mají jeden průsečík
A3: (∃Cˇ⊆X,∣Cˇ∣=4)(∀p∈P):∣p∩Cˇ∣≤2
existuje množina čtyř bodů „v obecné poloze“ (žádné tři z nich neleží na přímce)
prvky X … body
prvky P … přímky
řád konečné projektivní roviny
KPR má řád n∈N, pokud každá její přímka má n+1 bodů
tedy řád KPR := velikost přímky – 1
hypergraf
hypergraf je dvojice (V,H), kde H je množina podmnožin V, tj. H⊆P(V)
incidenční graf hypergrafu
graf incidence hypergrafu (V,H) je bipartitní graf s partitami V a H, kde mezi x∈V a h∈H vede hrana ⟺x∈h
dualita projektivních rovin
mějme projektivní rovinu (X,P); potom duální projektivní rovina k (X,P) je hypergraf (X∗,P∗), kde
X∗=P,
pro x∈X definujme x∗:={p∈P:x∈p}
x∗ … přímky, které procházejí x
P∗={x∗∣x∈X}
v podstatě obrátíme incidenční graf
toková síť
tokovou síť tvoří
V … množina vrcholů
E … množina orientovaných hran, E⊆V×V
z∈V … zdroj
s∈V∖{z} … spotřebič / stok
c:E→[0,+∞) … c(e) je kapacita hrany e
definice umožňuje mít hrany oběma směry, připouští také smyčky, ty však z hlediska toků v sítích nejsou nijak užitečné
poznámka: ze stoku může vycházet orientovaná hrana, podobně do zdroje může vést hrana
tok
tok v síti (V,E,z,s,c) je funkce f:E→[0,+∞) splňující
∀e∈E:0≤f(e)≤c(e)
∀x∈V∖{z,s}: součet toků do vrcholu x se rovná součtu toků z vrcholu (formálně pomocí sum) … Kirchhoffův zákon
velikost toku
velikost toku f v síti (V,E,z,s,c) je w(f):=f[Out(z)]−f[In(z)]
kde Out(z) a In(z) jsou množiny hran do, respektive ze zdroje a f[A]:=∑e∈Af(e) pro A⊆E
maximální tok
maximální tok je tok, který má největší velikost
řez v síti
řez v síti (V,E,z,s,c) je množina hran R⊆E taková, že každá orientovaná cesta ze z do s obsahuje aspoň jednu hranu R
kapacita řezu
kapacita řezu R … c(R)=∑e∈Rc(e)
elementární řez
E(A,B):=E∩(A×B)
tedy E(A,B)={uv∈E:u∈A∧v∈B}
elementární řez je E(A,B) pro A⊆V,B=V∖A
přičemž z∈A,s∈B
minimální řez
minimální řez je řez, který má nejmenší kapacitu
nenasycená a zlepšující cesta
nenasycená cesta pro f je neorientovaná cesta x1e1x2e2…xkekxk+1, kde ∀i: buď ei=(xi,xi+1) (ei je dopředná hrana), nebo ei=(xi+1,xi) (ei je zpětná hrana) a navíc platí
pro každou dopřednou hranu ei platí f(ei)<c(ei)
pro každou zpětnou hranu ei platí f(ei)>0
zlepšující cesta pro f je nenasycená cesta ze z do s
párování v grafu
párování v grafu G=(V,E) je množina hran M⊆E taková, že žádný vrchol nepatří do více než jedné hrany M
vrcholové pokrytí v grafu
vrcholové pokrytí v G=(V,E) je množina vrcholů C⊆V taková, že každá hrana obsahuje aspoň 1 vrchol z C
systém různých reprezentantů v hypergrafu
systém různých reprezentantů (SRR) v hypergrafu H=(V,E) je funkce r:E→V taková, že
∀e∈E:r(e)∈e
∀e,f∈E:e=f⟹r(e)=r(f) … tj. r je prostá
r(e) … „reprezentant hyperhrany e“
analogie s předsedy spolků
hranový a vrcholový řez v grafu
F⊆E je hranový řez v G, pokud G−F je nesouvislý
kde G−F:=(V,E∖F)
A⊆V je vrcholový řez, pokud G−A je nesouvislý
kde G−A=(V∖A,E∩(2V∖A))
hranová a vrcholová souvislost grafu
stupeň hranové souvislosti (nebo jen hranová souvislost) grafu G, značený ke(G), je největší k takové, že G je hranově k-souvislý
pozorování: ke(G)= velikost nejmenšího hranového řezu v G
vrcholová souvislost grafu G, značená kv(G), je největší k takové, že G je vrcholově k-souvislý
pozorování: kv(Kn)=n−1
pozorování: G není úplný … kv(G)= velikost nejmenšího vrcholového řezu
hranově a vrcholově k-souvislý graf
graf je hranově k-souvislý, pokud neobsahuje žádný hranový řez velikosti menší než k
graf je vrcholově k-souvislý, pokud má aspoň k+1 vrcholů a neobsahuje žádný vrcholový řez velikosti menší než k
klika a nezávislá množina v grafu
klika v grafu je množina vrcholů taková, že každé dva jsou spojené hranou
nezávislá množina v grafu je množina vrcholů taková, že žádné dva vrcholy nejsou spojené hranou
Hammingova vzdálenost a Hammingova váha
slovo x∈Z2n lze chápat jako řádkový vektor x=(x1,x2,…,xn)
Hammingova vzdálenost d(x,y):= počet i takových, že xi=yi
Hammingova váha ∥x∥:= počet i takových, že xi=0
minimální vzdálenost kódu
pro kód C⊆Z2n je minimální vzdálenost Δ(C):=minx=yx,y∈Cd(x,y)
(n,k,d)-kód
(n,k,d)-kód je množina C⊆Z2n taková, že ∣C∣=2k a Δ(C)=d
lineární kód
kód C∈Z2n je lineární, pokud je to vektorový podprostor Z2n (ekvivalentně 0∈C a ∀x,y∈C:x⊕y∈C)
pro lineární (n,k,d)-kód je k jeho dimenze
generující matice
pro lineární (n,k,d)-kód C je generující matice G∈Z2k×n, jejíž řádky tvoří bázi C
kódování
nechť C je (n,k,d)-kód pro k∈N, tak kódování pro C je bijekce Z2k→C
dekódování
dekódování (n,k,d)-kódu C je funkce g:Z2n→C taková, že ∀x∈Z2n:d(x,g(x))=miny∈Cd(x,y)
duální kód
C⊥:={y∈Z2n:(∀x∈C)⟨x,y⟩=0} … duální kód k C
kontrolní matice lineárního kódu
nechť je C lineární (n,k,d)-kód, pak kontrolní matice kódu C je matice, jejíž řádky tvoří bázi C⊥
Hammingovy kódy
nechť r∈N,r≥2
nechť Kr je matice s r řádky a 2r−1 sloupci, jejíž sloupce jsou nenulové a různé
nechť Hr je kód s kontrolní maticí Kr
kódům Hr se říká Hammingovy kódy
Tvrzení
U následujících tvrzení se očekává, že je budete umět zformulovat a (není-li uvedeno jinak) i dokázat.
fakt: pokud se dá posloupnost shora odhadnout nějakou exponenciální funkcí, tak an=n!1f(n)(0)
kde f(x) je její vytvořující funkce
„odvození“
f(x)=a0+a1x+a2x2+a3x3+…
f′(x)=a1+2a2x+3a3x2+…
f′′(x)=2a2+3⋅2a3+…
f(n)(x)=n!⋅an+…
binomická věta
pro d∈N0:(1+x)d=∑n=0d(nd)xn
tedy (1+x)d je vytvořující funkcí pro (0d),(1d),(2d),…,(dd),0,0,0,…
pro δ∈R a n∈N0 definujeme zobecněné kombinační číslo (nδ):=n!δ(δ−1)⋅(δ−2)⋅…⋅(δ−n+1)
věta: zobecněná binomická věta
pro δ∈R platí (1+x)δ=∑n=0∞(nδ)xn
nekonečno bychom mohli použít i u základní binomické věty, pokud bychom použili zobecněné kombinační číslo (protože pro n>δ bude v součinu v čitateli jeden člen nulový)
celkově ignorujeme otázky konvergence, ale aby věta platila, tak bychom chtěli ∣x∣<1
důkaz
označme f(x)=(1+x)δ
zjevně
f′(x)=δ(1+x)δ−1
f′′(x)=δ(δ−1)(1+x)δ−2
f(n)(x)=δ(δ−1)⋅…⋅(δ−n+1)(1+x)δ−n
nechť a0,a1,… je posloupnost s vytvořující funkcí f(x)
potom an=n!f(n)(0)=(nδ)
Rozklad racionální funkce na parciální zlomky (bez důkazu) a jeho využití při práci s vytvořujícími funkcemi
modelový příklad: našli jsme f(x)=(1−3x)(1−x)1−2x
chceme znát explicitní vzorec pro an (známe rekurentní)
(1−3x)(1−x)1−2x=1−3xα+1−xβ
1−3xα odpovídá posloupnosti α,3α,9α,…,3nα,…
1−xβ odpovídá posloupnosti β,β,β,…,β,…
tedy an=3nα+β
α,β lze spočítat…
pomocí prvních několika členů posloupnosti
a0=1=30α+β=α+β
a1=2=31α+β=3α+β
rozkladem na parciální zlomky (viz např. Math Tutor)
Odvození vzorečku pro Catalanova čísla, definovaná jako počet binárních zakořeněných stromů
Cn … počet binární stromů s n vnitřními vrcholy
C0=1
mějme kořen, levý syn je list, pravý podstrom má n−1 vnitřních vrcholů → počet možných pravých podstromů je Cn−1
nebo levý podstrom má jeden vnitřní vrchol a pravý n−2, pak C1⋅Cn−2 možností
obecně levý podstrom i vnitřních vrcholů, pravý n−1−i vnitřních vrcholů, pak Ci⋅Cn−1−i možností
Cn=C0Cn−1+C1Cn−2+⋯+Cn−1C0=∑i=0n−1CiCn−1−i pro n≥1
C(x)=∑n=0∞Cnxn
∑n=1∞Cnxn=∑n=1∞(∑i=0n−1CiCn−1−i)xn
C(x)−1=x∑n=0∞(∑i=0nCiCn−i)xn
C(x)−1=x⋅C2(x)
xC2(x)−C(x)+1=0
2 řešení
2x1+1−4x=:C+(x)
2x1−1−4x=:C−(x)
chceme C(0)=C0=1
C−(x) lze spojitě dodefinovat v nule, takže C(x)=C−(x)
značení: [xn]f(x) je člen s indexem n v posloupnosti, jejíž vytvořující funkce je f(x)
Odvození vlastností konečných projektivních rovin: počet bodů, počet přímek, počet bodů v jedné přímce, počet přímek procházejících jedním bodem
tvrzení: v každé KPR mají všechny přímky stejný počet bodů
důkaz: sporem
nechť v KPR (X,P) existují přímky p,q takové, že ∣p∣<∣q∣
označme x společný bod p,q
nechť p obsahuje body x,y1,y2,…,yk a q obsahuje body x,z1,z2,…,zℓ, kde k<ℓ
tvrdím, že existuje bod w∈X, který nepatří do p∪q
volme Cˇ dle A3
pokud Cˇ∖(p∪q)=∅, volme w∈Cˇ∖(p∪q)
pokud Cˇ⊆p∪q, pak ∣Cˇ∩p∣=∣Cˇ∩q∣=2, BÚNO Cˇ={y1,y2,z1,z2}
v tom případě zvolíme za w společný bod y1z1 a y2z2
kdyby w∈p, tak w je jediný společný bod p a y1z1, a tedy w=y1, ale w∈y2z2, tedy y1=w∈y2z2, tedy ∣Cˇ∩y2z2∣≥∣{y1,y2,z2}∣=3, což je spor s volbou Cˇ
uvažme přímky wz1,wz2,…,wzℓ,wx, každá z nich protíná p, jsou navzájem různé, tedy existuje bod v∈p, který je obsažen v aspoň dvou z těch přímek
spor: w a v mají aspoň 2 společné přímky
lemma: v projektivní rovině (X,P) platí (∀x∈X)(∃p∈P):x∈/p
důkaz
volme Č dle A3
volme 3 různé body a,b,c∈Cˇ∖{x}
tvrdím, že alespoň jedna z přímek ab,ac neobsahuje x
jinak by {a,x}⊆ac∩ab, což je spor
definice: KPR má řád n∈N, pokud každá její přímka má n+1 bodů
tvrzení: pro KPR (X,P) řádu n platí následující
každý bod patří do právě n+1 přímek
∣X∣=n2+n+1
∣P∣=n2+n+1
důkaz 1 (každý bod patří do právě n+1 přímek)
volme x∈X
dle lemmatu ∃p∈P:x∈/p
označme p={y1,y2,…,yn+1}
definujme přímky q1,q2,…,qn+1, kde qi=xyi
tvrdíme, že pro i=j je qi=qj
kdyby ne, tak {yi,yj}⊆qi∩p, což je spor
tvrdíme, že ∀r∈P: pokud x∈r, tak r∈{q1,…,qn+1}
volme r∈P takovou, že x∈r, jistě ∣r∩p∣=1, nechť yi je prvek r∩p, potom r=xyi=qi
tedy bodem x prochází právě n+1 přímek
důkaz 2 (∣X∣=n2+n+1)
volme x∈X, nechť pi jsou přímky procházející x
všimněme si, že každý bod y∈X∖{x} patří do právě jedné z přímek pi
∣X∣=∣{x}∣+∣p1∖{x}∣+∣p2∖{x}∣+⋯+∣pn+1∖{x}∣=
=1+(n+1)⋅n=n2+n+1
důkaz 3 (∣P∣=n2+n+1) – dvě varianty
graf incidence – bipartitní graf, nahoře přímky, dole body
každý vrchol dolní partity má stupeň n+1
každý vrchol horní partity má stupeň n+1
celá dolní partita má n2+n+1 vrcholů
mezi partitami tedy vede (n2+n+1)(n+1) hran
proto i v horní partitě musí být n2+n+1 vrcholů
počítání dvěma způsoby
počítáme počet dvojic (x,p)∈X×P takových, že x∈p
těch je ∣X∣⋅(n+1)=(n2+n+1)(n+1)
je jich taky ∣P∣⋅(n+1)
tudíž (n2+n+1)(n+1)=∣P∣⋅(n+1)
proto ∣P∣=(n2+n+1)
Duální projektivní rovina je opravdu projektivní rovina
A3: existuje množina 4 přímek takových, že žádné tři z nich neprocházejí jedním bodem
máme 4 body z A3 v původní projektivní rovině – označíme a,b,c,d
tvrdíme, že ab,bc,cd,ad jsou hledané 4 přímky
zvolíme tři z nich: ab,bc,cd
průnik prvních dvou je b
průnik druhých dvou je c
společný bod nemají
obdobně pro libovolnou jinou trojici
Konstrukce projektivních rovin z konečných těles
nechť T je konečné těleso s n prvky (tedy n musí být kladná celá mocnina prvočísla)
uvažujme vektorový prostor V=T3={(x,y,z)∣x,y,z∈T}, ∣V∣=n3
nechť X je množina podprostorů dimenze 1 ve V
∣X∣=n−1n3−1
protože máme n3−1 nenulových vektorů, každý patří do jednoho podprostoru dimenze 1
podprostor dimenze 1 má n−1 nenulových vektorů
∣X∣=n−1n3−1=n2+n+1
pro každý podprostor p⊆V dimenze 2 definuji p~:={x∈X:x⊆p}
P={p~∣p je podprostor V dimenze 2}
∣P∣=∣X∣, protože podprostor dimenze 2 je ortogonálním doplňkem podprostoru dimenze 1 a protože existuje bijekce mezi podprostory a jejich ortogonálními doplňky
intuice: kdyby to bylo v R3, tak body jsou přímky procházející počátkem a přímky jsou roviny procházející počátkem (svazky přímek)
(X,P) je projektivní rovina
A1: dva různé podprostory dimenze 1 jsou generovány dvěma lineárně nezávislými vektory, ty dohromady generují podprostor dimenze 2
A2: dimP+dimQ−dim(P∩Q)=dim(span(P∪Q))
dimP=dimQ=2
dim(span(P∪Q))=3
tedy dim(P∩Q)=1
A3: lze nalézt 4 nenulové vektory takové, že každé tři z nich jsou lineárně nezávislé
např. (1,0,0),(0,1,0),(0,0,1),(1,1,1)
Existence maximálního toku v obecné síti (bez důkazu)
fakt: v každé tokové síti existuje maximální tok
poznámka: obecně na přednášce uvažujeme konečné tokové sítě, grafy apod.
idea důkazu
mějme síť, očíslujme hrany (od 1 do m)
tok f reprezentujme jako uspořádanou m-tici hodnot
množina všech toků je uzavřená a omezená podmnožina Rm, je tedy kompaktní
funkce, která toku f přiřadí w(f), je spojitá
víme z analýzy, že spojitá funkce na kompaktní množině nabývá maxima
Charakterizace maximálního toku pomocí neexistence zlepšující cesty a pomocí řezu odpovídající kapacity; minimaxová věta o toku a řezu
pozorování: pokud má tok f zlepšující cestu, tak není maximální
důkaz: máme zlepšující cestu pro tok f, označme ε možné zlepšení (je to minimum přes všechny rozdíly od kapacit na dopředných hranách a od nuly na zpětných hranách), přičtením/odečtením ε dostaneme lepší tok g, takže f nemohl být maximální
důkaz, že w(f)≤c(R)
definujme A:= vrcholy x∈V takové, že existuje orientovaná cesta ze z do x nepoužívající hrany R
z∈A, s∈/A, Out(A)⊆R
w(f)=f[Out(A)]−f[In(A)]≤f[Out(A)]≤c(Out(A))≤c(R)
věta: nechť f je tok v síti; potom následující tvrzení ekvivalentní
f je maximální
f nemá zlepšující cestu
existuje řez R takový, že w(f)=c(R)
důkaz
1⟹2: obměnou (viz pozorování)
3⟹1: obměnou
pro libovolný řez R′ a libovolný tok f′ platí, že w(f′)≤c(R′)
kdyby f nebyl maximální, tak existuje f+ tok splňující w(f+)>w(f)
potom pro každý řez R platí, že c(R)≥w(f+)>w(f)
tedy neexistuje žádný řez R splňující c(R)=w(f)
2⟹3
nechť f je tok, který nemá zlepšující cestu
definujme množinu A:={x∈V:ze z do x vede nenasycenaˊ cesta}
zjevně z∈A,s∈/A
definujme R:=Out(A)={uv∈E:u∈A,v∈/A}
všimněme si ∀e∈Out(A):f(e)=c(e)
∀e′∈In(A):f(e′)=0
z lemmatu výše víme, že pro A⊆V, kde z∈A,s∈/A, platí w(f)=c(Out(A))=c(R)f[Out(A)]−0f[In(A)]=c(R)
důsledek („Minimaxová věta o toku a řezu“): nechť fmax je maximální tok a Rmin je minimální řez v (V,E,z,s,c), potom w(fmax)=c(Rmin)
důkaz
w(fmax)≤c(Rmin) … víme, viz výše
w(fmax)≥c(Rmin) … dle věty w(fmax)=c(R)≥c(Rmin)
důsledek 2: v síti, kde všechny kapacity jsou celočíselné, Fordův–Fulkersonův algoritmus najde maximální tok, který bude celočíselný (celočíselnost vyvozujeme ze znalosti FF algoritmu)
Fordův–Fulkersonův algoritmus, jeho důsledek pro celočíselnost maximálního toku a pro existenci maximálního toku v síti s racionálními kapacitami
algoritmus
iterujeme, dokud existuje zlepšující cesta
spočítáme rezervu celé cesty (minimum přes rezervy hran cesty)
pro každou hranu upravíme tok – v protisměru odečteme co nejvíc, zbytek přičteme po směru
pro celočíselné kapacity vrátí celočíselný tok (protože i rezervy budou celočíselné)
racionální kapacity převedeme na celočíselné
algoritmus se zastaví, protože v takové síti musí existovat řez s konečnou kapacitou a protože se tok v každé iteraci zvětší aspoň o jedna
Souvislost mezi velikostí největšího párování a nejmenšího vrcholového pokrytí v obecném grafu
lemma: pokud M je párování a C vrcholové pokrytí v G=(V,E), tak ∣M∣≤∣C∣
důkaz
každá hrana z M musí být pokrytá vrcholem z C
zároveň každý vrchol z C pokryje nejvýš 1 hranu z M
Kőnigova–Egerváryho věta
věta: v každém bipartitním grafu má největší párování stejnou velikost jako nejmenší vrcholové pokrytí
důkaz
nechť G=(V,E) je bipartitní graf s partitami A,B
vytvořme tokovou síť (V∪{z,s},E+,z,s,c)
E+={zx∣x∈A}∪{ys∣y∈B}∪{xy∣{x,y}∈E∧x∈A∧y∈B}
pro x∈A, y∈B
c(zx)=c(ys)=1
c(xy)=∣A∣+∣B∣+1 (prakticky nekonečno)
nechť Cmin je nejmenší vrcholové pokrytí v G, Mmax největší párování v G
jistě ∣Mmax∣≤∣Cmin∣
nechť f je maximální tok v té síti a R minimální řez
dle minimaxové věty w(f)=c(R)
BÚNO f má celočíselné hodnoty
definujme Mf:={{x,y}∈E:f(xy)>0}
jistě Mf párování v G, navíc ∣Mf∣=w(f)
definujme CR:={x∈A:zx∈R}∪{y∈B:ys∈R}
pozorování: R neobsahuje žádnou hranu z A do B
jistě CR je vrcholové pokrytí G
kdyby CR nebylo pokrytí, tak existuje nepokrytá hrana {x,y}∈E, potom cesta z→x→y→s je ve sporu s tím, že R je řez
pozorování: v bipartitním grafu s partitami A,B má každé párování velikost nejvýše ∣A∣ (i nejvýše ∣B∣)
definice: pro graf G=(V,E) a množinu X⊆V označím N(X):={y∈V∖X:(∃x∈X){x,y}∈E}
Hallova věta, bipartitní grafová verze
nechť G je bipartitní graf s partitami A,B, potom G má párování velikosti ∣A∣⟺„Hallova podmıˊnka“∀X⊆A:∣N(X)∣≥∣X∣
důkaz
⟹
pokud existuje párování velikosti ∣A∣, tak pro každou X⊆A existuje ∣X∣ vrcholů spárovaných s X, ty patří do N(X), tedy ∣N(X)∣≥∣X∣
⟸
nechť M je největší párování v G
pro spor nechť ∣M∣<∣A∣
dle Kőnigovy–Egerváryho věty existuje pokrytí C, kde ∣C∣=∣M∣<∣A∣
CA:=C∩A
CB:=C∩B
X:=A∖CA
zjistím, že N(X)⊆CB
protože nepokryté hrany musí pokrývat vrcholy v N(X)
navíc ∣X∣=∣A∣−∣CA∣>∣CB∣≥∣N(X)∣
jelikož ∣C∣<∣A∣⟹∣A∣>∣CA∣+∣CB∣
to je spor s Hallovou podmínkou
pozorování: jakmile uvnitř hypergrafu je množina čtyř hyperhran, které ve svém sjednocení mají tři vrcholy, tak nemůžu najít systém různých reprezentantů
platí to obecně pro množinu k hyperhran – když budou mít ve sjednocení méně než k vrcholů, tak nenajdu SRR
implikace platí i obráceně, lze vyslovit jako větu
Hallova věta, hypergrafová verze
hypergraf H=(V,E) má SRR, právě když ∀F⊆E:⋃e∈Fe≥∣F∣
důkaz
nechť H=(V,E) je hypergraf, nechť IH je jeho graf incidence
H má SRR ⟺IH má párování velikosti ∣E∣
Hallova podmínka pro H: ∀F⊆E:⋃e∈Fe≥∣F∣⟺ bipartitní Hallova podmínka pro IH a partitu E
Mengerovy věty pro hranovou a vrcholovou souvislost (Mengerova věta pro hranovou souvislost je též někdy označována jako „Fordova–Fulkersonova věta“)
Mengerova věta, hranová xy-verze
pro dva různé vrcholy x,y grafu G platí, že G obsahuje k hranově disjunktních cest z x do y⟺G neobsahuje hranový xy-řez velikosti menší než k
důkaz
⟹: pokud máme k hranově disjunktních cest z x do y, tak každý hranový xy-řez musí obsahovat aspoň jednu hranu z každé té cesty
⟸
nechť G neobsahuje hranový xy-řez velikosti menší než k
vyrobíme tokovou síť (V,E,x,y,c), kde E={uv,vu∣{u,v}∈E},∀e∈E:c(e)=1
pozorování: v té síti není žádný řez velikosti menší než k
tedy v té síti existuje tok velikosti aspoň k
nechť f je celočíselný maximální tok
navíc mezi všemi celočíselnými maximální toky volme f tak, aby množina S(f){e∈E:f(e)=1} byla co nejmenší
pozorování: S(f) neobsahuje žádný orientovaný cyklus jinak spor s minimalitou S(f)
pomocí S(f) vyrobím k hranově disjunktních cest z x do y takto:
opakuj k-krát
začni v x
jdi po hranách z S(f), dokud nedojdeš do y
tenhle krok bude konečný, protože S(f) neobsahuje orientované cykly
použité hrany odstraň z S(f)
Mengerova věta, globální hranová verze
graf G je hranově k-souvislý ⟺ mezi každými dvěma různými vrcholy existuje k hranově disjunktních cest
důkaz
G je hranově k-souvislý
⟺ neexistuje hranový řez velikosti menší než k
⟺∀x,y různé: neexistuje hranový xy-řez velikosti menší než k
⟺∀x,y různé: existuje k hranově disjunktních cest z x do y
definice: dvě cesty v G z x do y jsou navzájem vnitřně vrcholově disjunktní (VVD), pokud nemají žádný společný vrchol kromě x,y
Mengerova věta, vrcholová xy-verze
nechť G=(V,E) je graf
nechť x,y jsou různé nesousední vrcholy
nechť k∈N
potom G obsahuje k navzájem VVD cest z x do y⟺G neobsahuje vrcholový xy-řez velikosti <k
důkaz
⟹ zřejmá
⟸
nechť G nemá vrcholový xy-řez velikosti <k
vyrobíme síť S takto
za každý vrchol u∈V dáme do S dva vrcholy u+,u− a hranu u+u− s kapacitou 1
za každou hranu {u,v}∈E dáme do S dvě orientované hrany u−v+ a v−u+ s kapacitami "∞"
zdroj: x−, stok: y+
tvrdím, že S nemá řez kapacity c<k
sporem: nechť takový řez existuje
potom všechny jeho hrany jsou tvaru u+u− pro nějaké u∈V a odpovídající vrcholy v G tvoří vrcholový xy-řez velikosti c<k, což je spor
podle minimaxové věty o toku a řezu v S existuje tok velikosti ≥k, BÚNO je ten tok celočíselný, říkejme mu f
z existence takového f plyne, že S obsahuje k hranově disjunktních cest z x− do y+ (viz hranová verze), označme je P1,…,Pk
ty cesty P1,…,Pk jsou i vnitřně vrcholově disjunktní, protože každá cesta (orientovaná) z x− do y+ v S, která obsahuje vrchol u+ nebo u− pro nějaké u∈V∖{x,y}, musí obsahovat i hranu u+u−
když v cestách P1,…,Pk nahradíme každou hranu tvaru u+u− jedním vrcholem u, tak dostaneme k VVD cest z x do y v G
lemma: nechť G=(V,E) je graf s hranou e={x,y}; nechť G−:=(V,E∖{e}); potom kv(G−)≥kv(G)−1
důkaz
nechť A je nejmenší vrcholový řez v G−
potom kv(G−)=∣A∣
chceme kv(G)≤kv(G−)+1=∣A∣+1
G− se po odebrání A rozpadne na několik komponent, rozlišme případy:
pokud existuje komponenta (v G−−A), která neobsahuje x ani y, tak A je vrcholový řez v G
tedy kv(G)≤∣A∣
jinak má G−−A právě 2 komponenty, jedna obsahuje x, druhá y, označíme je jako Gx−,Gy−
pokud BÚNO Gx− obsahuje ještě nějaký další vrchol z, tak A∪{x} je vrcholový řez v G, tedy kv(G)≤∣A∣+1
pokud Gx− ani Gy− už neobsahují kromě x nebo y už žádný další vrchol, tak ∣V∣=∣A∣+2, tedy kv(G)≤∣V∣−1=∣A∣+1
Mengerova věta, globální vrcholová verze
G je vrcholově k-souvislý ⟺ mezi každými dvěma různými vrcholy x,y existuje k navzájem VVD cest
důkaz
pro Kn věta zjevně platí (jedna cesta je přímá, další vždy přes jiný vrchol, těch je n−2)
nechť G není úplný (byť by tahle větev důkazu fungovala i pro Kn)
⟸: mezi každými dvěma vrcholy je k VVD cest ⟹ G má ≥k+1 vrcholů, žádný řez velikosti <k⟹G je k-souvislý
⟹: nechť x,y jsou různé vrcholy; případy
{x,y}∈/E … viz xy-verze M. věty
{x,y}∈E: nechť G−:=(V,E∖{{x,y}})
podle lemmatu: kv(G−)≥k−1
podle xy-verze M. věty pro G− existuje k−1 VVD cest x→y
přidám k nim hranu e a mám k VVD cest x→y
Lemma o uších pro 2-souvislé grafy
konvence: „k-souvislý graf“ znamená „vrcholově k-souvislý“
definice: přidání ucha ke grafu G=(V,E) je tato operace
zvol dva různé vrcholy x,y∈V
pro d≥0 přidej vrcholy z1,z2,…,zd
přidej hrany cesty xz1z2…zdy
věta: graf G je 2-souvislý ⟺G se dá vyrobit z kružnice pomocí přidávání uší
důkaz
⟸ kružnice je 2-souvislá a přidání ucha nevytvoří řez velikosti ≤1
⟹
nechť G=(V,E) je 2-souvislý, nechť C je libovolná kružnice v G, nechť Gmax=(Vmax,Emax) je největší podgraf G, který se dá vyrobit přidáváním uší k C
tvrdíme, že Gmax=G
kdyby ne:
Vmax=V,Emax⊊E: spor s maximalitou Gmax, protože přidání hrany je přidání ucha
Vmax⊊V:
G je souvislý, tak ∃e={xy}∈E taková, že x∈Vmax a y∈/Vmax
G−x je souvislý, protože G je 2-souvislý
takže bude existovat ještě další cesta do Vmax
tato cesta + hrana xy = další ucho
opět spor s maximalitou Gmax
Cayleyho vzorec pro počet stromů na n vrcholech
věta: sn=nn−2
sn … počet stromů na množině vrcholů [n]:={1,2,…,n}
důkaz
nebudu počítat stromy, ale kořenové stromy
definice: kořenový strom je strom, ve kterém se jeden vrchol určil jako kořen a všechny hrany se zorientovaly směrem ke kořeni
kn:= počet kořenových stromů
pozorování: kn=n⋅sn
pozorování: pokud ve stromě zorientuji hrany tak, aby z každého vrcholu odcházela nejvýš jedna hrana, tak potom existuje právě jeden vrchol („kořen“), z něhož žádná hrana neodchází, a navíc všechny hrany jsou orientované směrem ke kořeni
definice: povykos (postup vytváření kořenového stromu) je posloupnost n−1 orientovaných hran (e1,e2,…,en−1) na vrcholech [n] taková, že ([n],{e1,…,en−1}) je kořenový strom
pn:= počet povykosů
pozorování: pn=(n−1)!⋅kn
pozorování (pravidla): posloupnost orientovaných hran (e1,e2,…,en−1) je povykos ⟺∀k∈[n−1]:
hrana ek spojuje vrcholy z různých komponent grafu tvořeného hranami e1,…,ek−1
hrana ek vychází z vrcholu, z něhož nevychází žádná z hran e1,…,ek−1
chci vyrobit povykos (e1,…,en−1)
mám n⋅(n−1) možností, jak zvolit e1
vybírám dva vrcholy, mezi kterými povedu hranu
mám n⋅(n−2) možností, jak zvolit e2, když už znám e1
mám n možností, jak zvolit konec hrany
začátek hrany musí být v jiné komponentě než konec
je tam n−2 komponent, které můžu zvolit (dohromady je komponent n−1, z toho jednu zvolit nemůžu)
v každé komponentě je „kořen komponenty“ (vrchol, z nějž žádná hrana nevychází)
hrana musí nutně začínat v „kořeni komponenty“ (podle druhého pravidla)
tedy mám n−2 možností, jak zvolit začátek hrany
pokud už jsem vybral e1,…,ek−1 v souladu s oběma pravidly, tak mám n⋅(n−k) možností, jak vybrat ek
n … vyberu konec ek
n−k … vyberu začátek v kořeni nějaké komponenty neobsahující konec ek
pn=n⋅(n−1)⋅n⋅(n−2)⋅…⋅n⋅1=
=∏k=1n−1n(n−k)=nn−1(n−1)!
kn=(n−1!)pn=nn−1
sn=nkn=nn−2
Spernerova věta
značení
P([n]) … množina všech podmnožin množiny [n]
(k[n]) … množina všech k-prvkových podmnožin [n]
definice: antiřetězec v P([n]) je množina A⊆P([n]) taková, že ∀M,M′∈A:M=M′⟹M⊆M′∧M′⊆M
věta: největší antiřetězec v P([n]) má velikost (⌊n/2⌋n)=(⌈n/2⌉n)
důkaz
antiřetězec velikosti (⌊n/2⌋n) je např. (⌊n/2⌋[n])
dokažme, že neexistuje větší antiřetězec
nechť A je antiřetězec, označme A={A1,A2,…,Ak}, kde k=∣A∣, chceme k≤(⌊n/2⌋n)
definice: nasycený řetězec v P([n]) je posloupnost M0,M1,…,Mn⊆[n], kde M0⊆M1⊆⋯⊆Mn⊆[n] a ∣Mi∣=i
v P([n]) existuje n! nasycených řetězců
idea: začínám s prázdnou množinou, postupně do ní přidávám prvky (mám n−i+1 možností, jak do ní přidat i-tý prvek)
každý nasycený řetězec obsahuje nejvýš jednu množinu z A
počítejme dvěma způsoby dvojice (A,R), kde A∈A, R je nasycený řetězec, A∈R
první způsob: dvojic je ≤n!
druhý způsob: pro A∈A mám ∣A∣!⋅(n−∣A∣)! nasycených řetězců obsahujících A
mám množinu A
mám ∣A∣ možností, který prvek z ní odeberu
postupně odebírám prvky, až se dostanu k prázdné množině → ∣A∣! možností
podobně (n−∣A∣)! možností, jak dotvořit řetězec přidáváním prvků
ze všech kombinačních čísel (kn) je největší (n/2n), takže ho můžu všude nahradit a hodnota výrazu se tím zmenší
⟹(⌊n/2⌋n)≥∣A∣
Počet hran v grafu bez C4
věta
nechť G=(V,E) je graf na n vrcholech, který neobsahuje C4 jako podgraf
potom ∣E∣≤O(n3/2)
důkaz
nechť G=(V,E) je graf bez C4, ∣V∣=n
označme H počet dvojic (x,{y,z}) takových, že
x,y,z∈V
y=z
x je soused y i z
poznámka: (2n)=2n(n−1)
počítejme H dvěma způsoby
pro dané x∈V mám přesně (2degx) možností, jak zvolit y a z
tedy H=∑x∈V(2degx)≥∑x∈V2(degx−1)2
pro dané {y,z}∈(2V) existuje nejvýše jeden společný soused x∈V, jinak by G obsahoval C4
tedy H≤(2n)≤2n2
tedy 2n2≥∑x∈V2(degx−1)2
z toho plyne, že n2≥∑x∈V(degx−1)2
chci ∣E∣=21∑x∈Vdegx≤O(n3/2)
uvažme funkci f(x)=(x−1)2, ta je konvexní, tedy pro každé x1,x2,…,xn∈R:f(nx1+⋯+xn)≤nf(x1)+f(x2)+⋯+f(xn)
tedy n≥n∑x∈V(degx−1)2≥(n∑x∈Vdegx−1)2
n≥n2∣E∣−1
počet hran je polovina ze součtu stupňů
n3/2≥2∣E∣−n
21(n3/2+n)≥∣E∣
Počítání dvěma způsoby (znalost obecného postupu)
typicky známe vlastnosti množin A a B
snažíme se vyjádřit hledanou veličinu pomocí dvojic, kde jeden prvek je z A a druhý z B
alternativní pohled pomocí bipartitního grafu a partitami A a B
zjistíme, že A vysílá určitý počet hran a že B může přijmout určitý počet hran
Ramseyova věta v grafové verzi a ve verzi pro barvení hran úplného grafu (i s více než dvěma barvami)
Ramseyova věta, grafová verze: (∀k∈N)(∀ℓ∈N)(∃N∈N) takové, že každý graf na N vrcholech obsahuje kliku velikosti k nebo nezávislou množinu velikosti ℓ
R(k,ℓ) … Ramseyovo číslo (nejmenší N, pro které platí, že libovolný graf na N vrcholech obsahuje kliku velikosti k nebo nezávislou množinu velikosti ℓ)
důkaz indukcí podle k+ℓ
základ indukce
pozorování: R(k,1)=1=R(1,ℓ)
pozorování: R(k,2)=k=R(2,k)
mějme k≥3,ℓ≥3, definujme N:=R(k,ℓ−1)+R(k−1,ℓ)
tyhle hodnoty jsou dobře definované (z indukčního předpokladu), protože součet argumentů je menší než k+ℓ
nechť máme dán graf G na N vrcholech
nechť x je libovolný vrchol G
označme S množinu sousedů vrcholu x a T=V∖(S∪{x})
protože ∣S∣+∣T∣=N−1=R(k,ℓ−1)+R(k−1,ℓ)−1, tak platí buď ∣S∣≥R(k−1,ℓ), nebo ∣T∣≥R(k,ℓ−1)
právě jedna z nerovností musí platit
předpokládejme, že ∣S∣≥R(k−1,ℓ), označme GS podgraf G indukovaný S
tedy GS obsahuje kliku velikosti k−1 nebo nezávislou množinu velikosti ℓ
pokud GS obsahuje nezávislou množinu velikosti ℓ, tak i G ji obsahuje, hotovo
pokud GS obsahuje kliku velikosti k−1, tak ta klika spolu s x tvoří kliku velikosti k v G, hotovo
případ, kde ∣T∣≥R(k,ℓ−1), je analogický
důsledek (symetrická verze Ramseyovy věty): pro každé m existuje N takové, že graf na N vrcholech má kliku nebo nezávislou množinu velikosti m
ekvivalentní 2-barevná verze Ramseyovy věty: pro každé m existuje N takové, že pro každé obarvení hran KN červeně a modře existuje jednobarevná klika velikosti m
věta (vícebarevná verze Ramseyovy věty): (∀b∈N)(∀m∈N)(∃N∈N) takové, že pro každé obarvení hran KN pomocí b barev existuje množina m vrcholů taková, že všechny hrany mezi nimi mají stejnou barvu
Rb∗(m) … nejmenší N s touto vlastností
R2∗(m)=R(m,m)
důkaz
postupujme indukcí podle b
pro b=1:R1∗(m)=m
pro b=2:R2∗(m)=R(m,m)
nechť b>2
nechť N=R(m,Rb−1∗(m))
mějme obarvení KN pomocí b barev
nechť ty barvy jsou 1) modrá a 2) b−1 odstínů červené
Ramseyova věta pro 2 barvy říká, že v tom obarvení buď existuje modrá klika velikosti m (jsem hotov), nebo existuje klika X velikosti Rb−1∗(m) taková, že všechny barvy hran mezi vrcholy X jsou odstíny červené
X indukuje úplný graf na Rb−1∗(m) vrcholech, jehož hrany jsou obarveny pomocí b−1 barev, tedy v něm je jednobarevná klika velikosti m
Ramseyova věta pro hypergrafy v konečné a nekonečné verzi (bez důkazu)
značení
(pX) … množina p-prvkových podmnožin X
KN(p) … p-uniformní úplný hypergraf, což je hypergraf ([N],(p[N]))
tedy KN=KN(2)
b-obarvení KN(p) je funkce (p[N])→[b]
pro dané b-obarvení β hypergrafu KN(p) řeknu, že množina X⊆[N] je jednobarevná (v obarvení β), pokud β přiřazuje všem množinám v (pX) tu samou barvu
K∞(p) … nekonečný hypergraf (N,(pN))
Ramseyova věta, konečná verze: (∀p∈N)(∀b∈N)(∀m∈N)(∃N∈N) takové, že pro každé b-obarvení KN(p) existuje jednobarevná m-prvková podmnožina [N]
Ramseyova věta, nekonečná verze: (∀p∈N)(∀b∈N) pro libovolné b-obarvení K∞(p) existuje nekonečná jednobarevná podmnožina N
p=1
v podstatě barvíme vrcholy
pro dané b,m stačí N=b(m−1)+1
při b(m−1) vrcholech lze najít obarvení, kde každá barva barví přesně m−1 vrcholů, po přidání dalšího vrcholu už alespoň jedna barva musí barvit m vrcholů
princip holubníku
Kőnigovo lemma o nekonečné cestě ve stromě, jeho použití při odvození konečné Ramseyovy věty z nekonečné
Kőnigovo lemma
nechť T je strom s nekonečně mnoha vrcholy, který neobsahuje žádný vrchol nekonečného stupně
nechť x0 je libovolný vrchol T
potom T obsahuje nekonečnou cestu začínající v x0
důkaz
zakořeňme T ve vrcholu x0
indukcí definujme posloupnost vrcholů x0,x1,x2,… tak, že x0,x1 tvoří cestu a pro ∀i∈N0: podstrom zakořeněný v xi má nekonečně mnoho vrcholů
už máme x0
nechť už máme x0,x1,…,xn, nechť y1,y2,…,yk jsou děti xn
aspoň jeden vrchol yi je kořenem nekonečného podstromu
kdyby byly všechny podstromy konečné, byl by celý strom konečný
tedy definujeme xn+1:=yi
posloupnost x0,x1,x2,… tvoří nekonečnou cestu v T
tvrzení: z nekonečné verze Ramseyovy věty plyne konečná verze
důkaz
nechť neplatí konečná Ramseyova věta, tedy ∃p∃b∃m∀N∃b-obarvení KN(p) neobsahující jednobarevnou podmnožinu velikosti m
řeknu, že b-obarvení β hypergrafu KN(p) je záludné, pokud v něm neexistuje jednobarevná podmnožina [N] velikosti m
ZN … množina záludných obarvení KN(p)
řeknu, že b-obarvení γ∈ZN+1 rozšiřuje b-obarvení β∈ZN, pokud pro každou h∈(p[N]) platí γ(h)=β(h)
pozorování: každé γ∈Zn+1 rozšiřuje právě jedno β∈ZN
definujme strom T na vrcholech Z1∪Z2∪⋯=⋃N=1∞ZN
{β,γ}∈E(T)⟺γ rozšiřuje β nebo naopak
v tom stromě existuje nekonečná cesta β1,β2,β3,…, kde βN∈ZN (podle Kőnigova lemmatu)
definujme obarvení β:(pN)→[b] takto: nechť máme dánu množinu h∈(pN), volme N∈N takové, že h⊆[N] a definujme β(h):=βN(h)
tvrdím, že β je záludné obarvení pro K∞(p)
kdyby ne, tak β má nějakou jednobarevnou m-prvkovou množinu X⊆N
volme N tak, že X⊆[N]
potom β obarví (pX) stejně jako βN, ale βN je záludné pro KN(p), tedy X v něm není jednobarevná
tedy β je záludné pro K∞(p), a tedy nekonečná Ramseyova věta neplatí
Použití generující matice ke kódování
tvrzení: pokud G je generující matice (n,k,d)-kódu C, tak zobrazení, které vektoru x=(x1,x2,…,xk)∈Z2k přiřadí vektor xG je kódování pro C