Kombinatorika a grafy

  • definice: graf (2jice množin), hrana, smyčka, jednoduchý graf (bez smyček a nás. hran), konečný graf, vážený graf ( s váh. funkcí ), cesta, tah (neopak. hran), sled, souvislý graf, eulerovský graf (dá se nakreslit 1 tahem), komponenta souvislosti, kružnice, strom, kostra (podgraf bez kružnic, obs. všechny vrcholy), les, most (hrana, jejímž odebráním zvýším počet komponent), hladový algoritmus, polynomiální algoritmus (ex. takový polynom P, že při zadání o velikosti n alg. skončí po max. P(n) krocích), NP-úplná úloha (když se dá ověřit uhodnuté řešení v polynom. čase), hamiltonovská kružnice (prochází každým vrcholem právě 1x), rovinný graf, stěna nakreslení (!ne grafu), Eulerova formule ( |V| - |E| + |S| = 2 ), těleso (konečné, nekonečné).

    • Operace s grafy

  • maticový popis grafu - matice sousednosti, matice incidence: ( IG )ue = 1, pokud u ∈ e, matice stupňů - ( DegG )uv = degG u (u = v) / 0 (jinak), Laplaceova matice - ( LG )uv = degG u (u = v) / -1 ( uv ∈ E(G) ) / 0 (jinak).
  • orientace: neorientovaný graf G -> orientovaný G-->, orientovaná matice incidence - D G--> = 0 ( není hrana ), 1 ( uv--> ∈ E(G-->) ), -1 ( vu--> ∈ E( G--> ) ).
  • Věta 1 : IG * IGT = DegG + AG. Dk: ( IG * IGT )uv = ∑e∈ E(IG)ue(IG)ve = # hran. t.z (IG)ue = 1 && (IG)ve = 1.
  • Veta 2 : G--> je orientace G => D G--> * D G--> T = DegG - AG = LG. Dk: e = uv--> - v i-tem radku je 1 a ve v-tem -1 na sloupci e. (DG*DGT) = ∑e∈ E(DG)ue (DG)ve.
  • Veta 3 : ( AGk )uv = pocet sledu delky k z u do v Dk: indukci - k=0 - pro jednotk. matici plati, k=1 - sled delky 1 musi byt hrana; k <-- (k-1), k > 1: (AGk)uv = ∑x∈ V (AGk-1ux (AG1)xv = ∑xv ∈ E (AGk-1)ux - pocet sledu delky k-1 od u k x & pres hrany z x do v => sledy delky k od u do v.
  • pocet koster grafu G - K( G ).
  • Veta 4 : K( G ) = det( L'G ), kde L'G je LG bez u-teho radku a sloupce. Dk: uvazim DG, DGT bez u-teho radku/sloupce. det L'G = (Binet-Cauchy) = ( w - indexova mnozina, vsechny moznosti vyberu n-1 radku/sloupcu ) ∑w⊂ E, |w|=n-1 det(DG(u))w det [(DG(u))w ]T = ∑w det2 (DG(u))w. - z lemmatu uz plyne: lemma: det(DGu) = 0 ( (V,w) neni kostra ), ± 1 ( (V,w) je kostra ). v grafu chybi nejaky vrchol u. a) w neurcuje kostru -> nesouvisly graf, podmatice urcena 1 z komp. (neobs. u) ma radk. soucet = 0-->. b) w urcuje kostru -> matici D(u)w lze usporadat na trojuhelnikovou (vezmu list, dam do rohu&indukci, vzdy ± 1).
  • prostor cyklu - nad GF( 2 ) - V*(G) = { vsechny podgrafy G }, E*(G) = { vsechny eulerovske podgrafy G ( ∀ u : degG u ≡ 0 mod 2 ) }
  • Veta 5 : V*(G) je vekt. prostor nad GF(2), dim V*(G) = |E(G)| Dk: vektory nad GF(2)|E(G)|, scitani - xor.
  • Veta 6 : E*(G) je vekt. prostor nad GF(2), dim E*(G) = |E(G)| - |V(G)| + 1
  • Veta 7 : fixujme kostru T v grafu G. ∀ e: e ∉ E( T ) Ke je kruznice v T ∪ { e } (jednozn. urcena), potom B* = { Ke | e ∈ E(G) - E(T) } je baze E*(G). Dk: B* je LN mnozina - ∀ hrana mimo je prave 1x, z ostatnich vektoru B* ji nedostanu; B* generuje: vezmu G' euler. podgraf, G'' = ∑e∈ E(G') Ke ∈ E*(G), E(G') xor E(G'') ⊂ E(T) = ∅ => G' = G''.
  • operace s grafy: kontrakce hrany: G ◦ e (v multigrafech - G : e )
  • Veta 8 : G multigraf, e ∈ E(G). Potom K(G) = 0 ( G nesouvisly ) / K(G\e) ( e je smycka ) / K(G\e) + K(G:e) ( e neni smycka ). K( K1 ) = 1. Dk: indukci podle poctu hran pro 0 bud nesouvisly nebo K1, pro m <-- m+1. smycka - ok, bez smycky - # koster G, t.z. e ∈ E(T) = # koster G:e, e ∉ T = # koster G-e.
  • chromaticky polynom PG(x) = pocet obarveni grafu G pomoci x barev ( x ∈ N ).
  • Veta 9 : ∀ G: PG(x) je polynom stupne ≤ |V(G)| a lze spocitat rekurzivne: P Kn (x) = xn ( doplnek uplneho grafu - nema hrany ), PG(x) = PG-e(x) (lib. barvy) - P G ◦ e (x) (maji stejnou barvu). Dk: v G.e - pouziji-li na G-e, dostanu legalni obarveni kde u,v maj stejnou barvu => rozdil = vysledek.

    • Latinske ctverce a projektivni roviny

  • L ∈ An x n je lat. ctverec (radu n), kdyz ∀ i: Lij ≠ Lij', j' ≠ j, ∀ j: Lij ≠ Li'j, i' ≠ i. L a L' jsou ortogonalni, kdyz ∀ (i,j) ≠ (i',j') : ( Lij, L'ij ) ≠ ( Li'j', L'i'j' ).
  • Veta 1 : Pokud existuje t navzajem ortogonalnich lat. ctvercu radu n, potom t ≤ n-1. Dk: lemma: permutace symbolu ve ctverci zachovava kolmost. ∀ ctverec takovou permutaci, aby prvni radek obs. prave posl. (1,2,...,n). potom na (2,1) nesmi byt 1 (uz je v (1,1)), a ve 2 ctvercich nesmi byt to same.
  • konecna projektivni rovina je mnozinovy sytem (V,P), P ⊂ 2V (pot. mn.), pro ktery plati (P - mnozina primek):
    1) ∀ x ≠ y ∈ V ∃! p ∈ P, x,y ∈ p. (pro kazde 2 body ∃ právě 1 přímka ve které oba leží)
    2) ∀ p ≠ q ∈ P : | p ∩ q | = 1 ( každé 2 přímky se protínají v právě 1 bodě)
    3) ∃ 4 body a,b,c,d ∈ V z nichz zadne 3 nelezi v primce.
  • Veta 2 : Pro kazdou projektivni rovinu (V,P) ∃ n: ∀ p ∈ P: |p| = n+1, ∀ x ∈ V: | { p | x ∈ p } | = n + 1. Navic |V| = |P| = n2 + n + 1. n se nazyva rad projektivni roviny. Dk: x ∈ p ∩ q ( ∈ P ), ∃ z : z ∉ p ∪ q. ∀ y ∈ p ∃ yz--> ∈ P. y' := q ∩ yz-->. y1 ≠ y2 => y'1 ≠ y'2 (z ax.2), ∀ bod ∈ p mam ∈ bod q, p & q lib. => |p| = |q| :=def. n+1. pocet primek yz--> je taky roven |p| (pro lib. bod z) => celkem n2 + n + 1 bodu/primek.
  • Veta 3 : Existuje (n-1) ortogonalnich lat. ctvercu radu n <=> existuje projektivni rovina radu n. (Nevi se pro ktera n existuje, zname pro mocniny prvocisel)
    Dk:<=: vezmu "vnejsi" primku PR, na ni body A0, An. ∀ bod Ai (1 ≤ i ≤ n-1) definuje lat. ctverec. ∀ primka z Ai se s primkami s A0, An protne prave 1x. ∀ 2 primky z Ai prochazi mimo vnejsi primku ruznymi body. ∀ primka proch. ∀ radkem&sloupcem mřížky "T" prave 1x => dostavam lat. ctverec. jsou ortogonalni - k-ty Lij = l <=> Tij ∈ pkl (l-ta primka z bodu Ak) . sporem necht pro (a,b) ex. 2, pak by se primky pka a pk'b protinaly ve 2 bodech.
    =>: vytv. primku q s body A0 ... An & mrizku T. do ni pridam primky p1,1 ... pn-1,n : pkl = {Ak} ∪ {Tij : k-ty Lij = l }. overit axiomy PR:
    2.) ( ∀ pij 1 prusecik s q, radkove x sloupcove - Tij, radkove, sloupcove spolu - A0, An. primky | pkl ∩ p0i,ni | = 1 -> v lat ctvercich je na kazdem radku a sloupci kazde cislo jen 1x. | pkl ∩ pk'l' | = { aij : ( Lijk, Lijk' ) = ( l,l') } (pro k = k' - Ak ).
    3.) { a11, a12, a21, a22 } - OK
    1.) pocet primek & bodu sedi, splnen axiom 2., W := | {(x,y,p), x ≠ y, x,y ∈ p } | = |P|*( n+12 ) (počet přímek * počet 2-jic bodů v přímce), navic W ≤ ( |X|2 ) ( ∀ 2 body ex. ≤ 1 přímka co je obsahuje) - jinak by se 2 primky mohly protnout ve > 1 bode. ~~> spocist ... vyjde rovnost => PRÁVĚ 1 přímka ∀ 2 body.
  • Latinský obdélník - L ∈ { 1,2,... n }k*n ( k radku, n sloupcu ), v zadnem radku ani sloupci se neopakuji prvky.
  • Veta 4 : Kazdy latinsky obdelnik velikosti k * n, k < n, lze doplnit na latinsky ctverec.
    Dk: indukci LO(k,n) --> LO(k+1,n). Bip. graf ( S ∪ H, E ), kde S je mn. sloupcu lat. ctverce, H je mn. hodnot pro n+1-radek. E = {{si,x}, x ∉ si} - "volne" hodnoty. moznost noveho radku = ex. parovani uspokojujiciho S. ∀ sloupci chybi n-k hodnot => deg si = n - k. x (∈ H) - vyskytuje se v k radcich, vzdy 1x -> n-k sloupcu prazdnych => deg x = n - k => mame perfektni parovani (Toky.V9).

    • Vytvorujici funkce

  • Binomicka veta : ( 1 + x )n = ∑i=0n ( ni ) xi = (1+x)(1+x)... . Koeficient u xi je pocet zpusobu, kterymi vyberu z cinitelu i-krat x a (n-i)-krat 1, proto ( ni ) moznosti.
  • necht a0, a1, ... je posloupnost realnych cisel takova, ze |ai| < Di pro nejake realne D > 0. Potom rada ∑i=0∞ ai xi konverguje k funkci a(x) pro x ∈ ( -1 /D , 1/D ). Naopak funkce a(x) na lib. malem okoli nuly definuje radu a0, a1, ... predpisem ai =
    a(i) (0)
    i!
    . a(x) je vytvorujici funkce posloupnosti { an }.
  • necht {an}, {bn} jsou posloupnosti, a(x), b(x) jejich vytv. fce. potom:
    { an + bn }n=0∞ <~> a(x) + b(x)
    { α an }n=0∞ <~> α a(x)
    (0,0,0, ..0n, a0, a1 ) <~> xn a(x)
    (an,an+1, ... ) <~>
    a(x) - (prvnich n clenu - do n-1)
    xn

    { αn an }n=0∞ <~> a(α x)
    (a0,01,0 ..., 0n-1,a1, 0 ... 0, ... ) <~> a(xn)
    {(n+1) an+1 }n=0∞ <~> a'(x)
    konvoluce <~> a(x)b(x)
    ( "základní" řady:
    1
    1-x
    ~ (1,1,1....),
    1
    1 - x2
    ~ (1,2,3 .... ),
    1
    1 - 2x
    ~ (1,2,4,8,16 ... ) ).
  • Fibonacciho cisla pres vytv. fce - vytv. fce F(x) =
    x
    1 - x - x2
    ; rozklad na parc. zlomky.
  • Zobecnena binom. veta : ( rk ) =
    r(r-1) ...(r-k+1)
    k!
    (k>0) / 1 (k=0) ( r ∈ R, k ∈ Z0+ ). Pokud r = -n, kde n ∈ N : ( -nk ) = (-1)k ( n+k-1k ).
  • Veta 1 : ( 1 + x)r = ∑n=0∞ ( rn ) xn ( k ∈ Z0+, r ∈ R ), tj. vytv. fce pro { ( rn ) }n=0∞ je funkce ( 1 + x )r. Dk: z Taylora
    ((1+x)r)(n)
    n!
    pro x = 0, vydelit n!. ((1+x)r)n = r(r-1)... (r-n+1)(1+x)r-n, ale (1+x) = 1 pro x = 0.
  • Bin. stromy - zakoreneny (ma koren) a pesteny (hraje roli levy/pravy naslednik). bn - pocet takovych stromu na n vrcholech: bn = ∑i=0n-1 (bi * bn-1-i), b(x) =
    1 - √ 1 - 4x
    2x
    , bn =
    1
    n+1
    * ( 2nn ).

    • Toky v sitich

  • Sit: G-->, z, s ∈ v(G-->), c: E(G-->) --> R0+. Tok: f : E(G-->) --> R0+, ∀ e ∈ E( G--> ): 0 ≤ f(e) ≤ c(e). Kirchhoff: ∀ v ≠ z,s : ∑x∈V, xv ∈ E f(xv) = ∑x∈ V, vx ∈ E f(vx). Velikost toku: w(f) = ∑x∈ V, zx ∈ E f(zx). Rez: R ⊂ E(G-->), t.z. v G--> \ R neni orientovana cesta ze z do s. Kapacita rezu - c( R) = ∑e ∈ R c(e).
  • elementarni rez: A ⊂ V(G), z ∈ A, s ∉ A. E(A, V\A) = { xy | x ∈ A, y ∈ V \ A, xy ∈ E(G) }.
  • lemma 1 : ∀ elementarni rez je rez. Dk: v G--> \ E(A,V\A) neex. orentovana cesta ze z do s. sporem, i = max{ j| vj ∈ A}, vivi+1 je v rezu => neni hrana rozdilu - spor.
  • lemma 2 : ∀ rez obsahuje elementarni rez. ( ∀ F ⊂ E(G) rez ∃ A ⊂ V, z ∈ A, s ∉ A : E( A, V\A) ⊂ F ). Dusledek - minimalni co do inkluze rez je elementarni, ∀ rez s nejmensi kapacitou je elementarni. Dk: A := { x | v G--> \ F ∃ or. cesta ze z do x }. sporem necht E(A, V\A) neni ⊂ F. potom ∃ xy ∈ E(G), x∈ A, y ∉ A, xy ∉ F - spor.
  • def. E( U,W ) = {xy, xy ∈ E(G), x ∈ U, y ∈ W }. ∀ U,W ⊂ V(G) : f(U,W) = ∑xy ∈ E(U,W) f(xy). ( z∈ U, s∈ V, U ∩ W = ∅, U ∪ W = V(G) => E(V,W) je elementarni rez.)
  • lemma 3 : ∀ U z ∈ U, s ∉ U : W = V(E) \ U, w(f) = f(U,W) - f(W,U). Dk: ∀ u ∈ U \ {z} : plati Kirchhoff, pro z : f+(z) = w(f). ∑u∈ U ( f+(u) ) = w(f) = f(U,W) - f(W,U).
  • dusledek: ∀ F rez, f tok : w(f) ≤ c(F) (ex. elem. rez E(A, V\A) - w(f) ≤ f(A,V\A) - f(V\A,A) ≤ f(A,V\A) ≤ c(E(A,V\A)) ≤ c(F) ). Dusledek dusledku - supf tok w(f) ≤ minF rez c(F).
  • Nenasycena cesta z u do v je cesta u = v1 v2 v3 ... vk = v, ∀ i = 1,... k-1 : vi vi+1 ∈ E--> => f(vi vi+1 ) < c( vi vi+1 ); vi+1 vi ∈ E--> => f( vi+1 vi ) > 0. Nasycena cesta neni nenasycena. Nasyceny tok - neex. nenasycena cesta ze z do s.
  • Veta 1 : f je maximalni <=> f je nasyceny. Dk: => "nenasyceny neni max." - ex. nenasycena cesta P ze z do s - vezmu min. rezervu kapacit, o ni zvetsim f'(e), dukaz ze je tok (kirchhoff), ze je vetsi. <= "nasyceny je max." - A := { X | ∃ nenasycena cesta z --> x } ∀ e ∈ E(A,V\A): f(e) = c(e), (sporem) ∀ e ∈ E(V\A,A) : f(e) = 0 (stejne). w(f) = c(A,V\A) - 0.
  • Veta 2 : ∀ sit : maxf tok w(f) = minR rez c(R) (toku je nekonecny pocet, rezu konecne). Dk: plyne z věty 1 a dusledku: ex. řez = tok.
  • Veta 3 : pokud c(e) ∈ Z0+ pro ∀ e ∈ E--> => ∃ celociselny max. tok ( ≠ max. celociselny tok !). Dk: algoritmem - f:= 0, zvetsovani podle nenasycenych cest, ε ∈ Z !, dukaz spravnosti - indukci podle poctu prechodu - je tok, je celociselny, je max., konecny alg.

    • Hamiltonovske kruznice

  • Necht G = (V,E) je graf. Kruznice c je hamiltonovska, pokud prochazi vsemi vrcholy. Graf G je hamiltonovsky, pokud ma hamiltonovskou kruznici.
  • Veta 4 : Rozhodnout zda graf ma HK je NP-uplny problem. BD.
  • lemma 4 : u,v ∈ V, {u,v} ∉ E. deg(u) + deg(v) ≥ |V|. potom G ma HK <=> G+{u,v} ma HK. Dk: => triv. <= mame HK "C" v G'=G+{u,v} - a) neobs. {u,v}, b) obs. - A:= { i, {u,ui} ∈ E }, B:= {(i+1), {v,ui} ∈ E }. ui - hrany HK. potrebujeme A ∩ B ≠ ∅. A ani B neobs. "1" -> | A ∪ B | ≤ n-1. |A| = deg(u), |B| = deg(v) |A ∩ B| = |A| + |B| - |A ∪ B| ≥ 1. tj. mam i v A i B. u = u1, u2, ... ui, un = v, un-1, ui+1 je nova HK.
  • Veta 5 - Dirac : Pokud ∀ v ∈ V plati ze deg(V) ≥ |V|/2, potom je G hamiltonovsky. Dk: pouzijeme lemma 4. ∀ u,v ∈ V, {u,v} ∉ E plati -> pouzitim ∀ u,v ∈ V, {u,v} ∉ E dostanu uplny graf.
  • Veta 6 : G = (V,E) a ∀ u,v : {u,v} ∉ E plati ze deg(u) + deg(v) ≥ |V|, potom je G hamiltonovsky. Dk: stejne, z lemmatu.

    • Chvataluv uzaver

  • mame G0 = (V, E0 ). Dokud ex. u,v ∈ V : {u,v} ∉ Ei a deg(u) + deg(v) ≥ |V|, potom Gi+1 = ( V, Ei+1 ), kde Ei+1 := Ei ∪ {u,v}, i := i + 1. Vysl. graf ma HK <=> puv. graf ma HK. Vysl. graf - jednozn. urceny := G* = [ G ].

    • Problem obchodniho cestujiciho

  • zobecneni HK, uplny graf a vahy na hranach w : ( V2 ) --> R. Hledame kruznici proch. vsemi vrcholy, s min. cenou. NP-uplne, jde ale priblizne, ve spec. pripadech - napr. pokud vahy jsou nezaporne a splnuji troj. nerovnost.
  • 2-aproximacni algoritmus - nalezne min. kostru, obejde po obvodu, udela zkratky z troj. nerovnosti.

    • Existence max. toku, toky jako lin. programovani

  • Mnozina vsech toku (vsemi m hranami) - F* ⊂ Rm, zobr. Fu : Rm --> R - tok 1 vrcholem site. Fu je spojite (lin. komb. konecneho poctu spojitych zobr - f --> f(ei)), Fz(f) = w(f) tim padem spojite. z kirchhoff. zákonů: Fu-1( {0} ) je uzavr. mnozina; F* = ∩u ≠ z,s Fu-1( {0} ) ∩ πi=1n < 0, c(i) > => uzavr. mnozina, proto existuje.
  • uloha maxx cT x za podminek Ax ≤ b, x ≥ 0. F* - mn. vsech toku, omezeni: fi ≥ 0, f1 ≤ c(e1) ... & kirchhoff pro vrcholy => podminky pro LP, cT x = w(f) = tok ze zdroje.

    • Systemy ruznych reprezentantu a Hallova veta

  • mnozinovy system M = ( Mi, i ∈ I ), I - mn. indexu. X := ∪i∈ I Mi . system ruznych reprezentantu - proste zobr. f: I --> X, t.z. ∀ i ∈ I : f(i) ∈ Mi.
  • mn. system odpovida bipartitnimu grafu (grafu incidence): G(M) = ( I ∪ X, { ix | x ∈ Mi, i ∈ I } ).
  • Veta 7 - Hallova : M = ( Mi, i ∈ I ) ma SRR <=> ∀ J ⊂ I : | ∪i∈ J Mi | ≥ | J |. ( tj. splnuje Hallovu podminku ).
    Dk: => jednoduchy : necht f je SRR. potom ∪i∈ j Mi &sup { f(i) | i ∈ J }, |∪i∈ J Mi } ≥ | {f(i), i∈ J } | = | J | ( prosta fce ).
    <= vytv. sit - G = ({z,s}∪ I∪ X. E--> ), E--> = {zi | i∈ I} ∪ {ix | x ∈ Mi, i∈ I} ∪ {xs | x ∈ X}. c ≡ 1 ∀ e. max. tok = min. rez. min. kapacita ∀ rezu ve vytvorenem grafu ≥ I, protoze: R ⊂ E--> rez => ∃ rez R' ⊂ {zi|i∈ I} ∪ {xs|x ∈ X}, t.z. c(R') ≤ c(R) (indukci podle poctu hran v prostř. hladině - misto ix mohu dat zi - porad bude rez, za kazdou pridanou hranu min. 1 vyhodim (mozno vic) ). A = {i | zi ∈ R'}, B = {x | xs ∈ R'}. R' rez => neex. hrana z I-A do X-B -> ∪i∈ I-A Mi ⊂ B, |B| ≥ |∪i∈ I-A Mi| ≥ |I-A|. c(R) ≥ c(R') = (c ≡ 1) = |R'| = |A|+|B| ≥ |A|+|I|-|A| = |I|.
    c(e) ≡ 1 => celociselny max. tok - w(f) = |I|. (kazdou hranou tece bud 1 nebo 0) w(f) = |I| -> kazdou hranou ze z musi tect 1, kirchhoff - ∀ i ∃ xi: f(ixi) = 1. xi i ≠ j xi ≠ xj (z x vede jen 1 hrana) g : I --> X, t.ž. g(i) = xi je SRR.
  • parovani v G je F ⊂ E(G), t.z. ∀ e ≠ f ∈ F : e ∩ f = ∅
  • Graf je k-regularni, pokud deg u = k ∀ u ∈ V. Je regularni, pokud je k-regularni pro nejake k. Parovani F je perfektni, pokud |F| = |V|/2.
  • Veta 8 : G = ( A ∪ B , E ) je bipartini graf s alespon 1 hranou a deg u ≥ deg v pro ∀ u ∈ A, v ∈ B => existuje parovani velikosti |A|. Dk: 0 ≠ maxv∈ B deg v = k ≤ minu∈ A deg u. mn. system: I = A, Mu = { v |uv ∈ E} := NG(u) - "okolí". k|NG(J)| ≥ |E(G[J∪ N(J)])| ≥ k|J| => ∀ J ⊂ A : NG(J):= |∪u∈ J Mu | ≥ J - plati Hall.
  • Dusledek 9 : Neprazdny (ve smyslu hran) regularni bipartitni graf ma perfektni parovani. Dk: ∃ parovani velikosti |A| = velikost |B| -> plne uspokojuje obe parity => perfektni

    • Mira souvislosti grafu (pro neorientovane grafy se ≥ 2 vrcholy)

  • Hranovy rez - F ⊂ E t.z. G \ F je nesouvisly. Vrcholovy rez - A ⊂ V, t.z. G[V\A] (ind. podgraf) je nesouvisly. ∀ graf se ≥ 2 vrcholy ma hranovy rez, ∀ neuplny graf ma vrcholovy rez.
  • Hranova souvislost grafu - Ke(G) = minF⊂ E(G),hran.rez | F |. Vrcholova souvislost - Kv(G) = minA⊂ V(G), vrchol.rez | A | (pokud G neni uplny ) / |V|-1 jinak. Graf je hranove/vrcholove k - souvisly, jestlize Ke(G)/Kv(G) ≥ k.
  • lemma 1 : kazdy co do inkluze minimalni hranovy rez souvisleho grafu rozdeli prislusny graf na PRAVE 2 komponenty souvislosti. Dk: F ⊂ E hranovy rez. necht ma komp. C1, ... Ck, pak hrany spojujici C2, ... Ck mohu vratit do grafu, ziskam mensi - spor.
  • lemma 2 : Necht A ⊂ V(G) je co do inkluze minimalni vrcholovy rez grafu G. Necht C1, ... Cj (j ≥ 2 ) jsou komponenty souvislosti grafu G[V\A]. Potom ∀ x ∈ A, ∀ i ∈ {1,.. j } ∃ ui ∈ Ci, t.z. xui ∈ E. Dk: kdyby ∃ x ∈ A, ∃ i: z x do ci neni hrana, potom kdyz x z A vyloucim, bude mit G[V\A'] opet aspon 2 komponenty - mensi rez - spor. (zde netreba predp. souvislost - min. rez je potom ∅)
  • lemma 3 : ∀ e ∈ E(G) : Ke(G) - 1 ≤ Ke(G-e) ≤ Ke(G) (vyhozenim hrany se Ke(G) nezvysi, a snizit se muze max. o 1.) Dk: hranova souvislost se nezvysi: mam-li hranovy rez F, odebranim e z grafu zůstane F hranovy rez. F' hr. rez v G-e. potom F'' = F' ∪ {e} hr. rez v G - o 1 vetsi.
  • lemma 4 : ∀ v ∈ V(G) : Kv(G) - 1 ≤ Kv(G-v) (snizi se max. o 1, muze se ale i zvysit). Dk: G uplny => Kv(G) = n-1, Kv(G-v) = n-2. rez |A|= Kv(G-v) => A ∪ {v} rez v G.
  • lemma 5 : ∀ e ∈ E(G) : Kv(G) - 1 ≤ Kv(G-e) ≤ Kv(G). ( Kv(G'+e) ≤ Kv(G') + 1 ). Dk: Kv(G) ≤ Kv(G-e) + 1. vrcholový řez v G => vrch. řez v G'. G' = G-e. Kv(G'+e) ≤ Kv(G')+1. |A|=Kv(G') - A rez v G', dělí G[V\A] na C1, ... Cl. pro G'+e: a) |e∩ A|≥ 1 - A je furt rez v G'+e., b) ∃ i: e⊂ C1 => A je rez i v G'+e. c) e BUNO spojuje C1 a C2 - l ≥ 3 - A je opet rez v G'+e. , l = 2 : e:= xy, x∈ C1, y ∈ C2. |C1| ≥ 2: A ∪ {x} je rez. |C2| ≥ 2 symetricky. |C1| = |C2| = 1 - potom |V| = |A|+2 => Kv(G'+e) ≤ |A| + 1 = |V|-1.
  • Veta 10 : ∀ G : Kv(G) ≤ Ke(G). Dk: rez F = {e1,...e|F|}. G' = G \ F. Kv(G'+e1) ≤ Kv(G')+1 (z lemma 5) ... Kv(G'+e1+... +e|F| } = Kv(G) ≤ Kv(G') + |F| = 0 + Ke(G).
  • Veta 11 - Ford-Fulkerson : G je hranove k-souvisly <=> ∀ u ≠ v ∈ V(G) ∃ alespon k hranove disjunktnich cest z u do v. (∀ 2 cesty jsou hranove disjunktni).
    Dk: <= F hranovy rez, |F|=Ke(G). u,v v ruznych komp. G\F. v G ∀ cesta z u do v obs. hranu z F ( |F| ≥ k ). z u do v ex. k hranove disj. cest, kazda musi byt prerusena F.
    => dano lib. s,z, vytv. sit G--> = (V(G), {xy-->, yx-->, xy ∈ E(G) } ), c ≡ 1. necht R lib. rez v siti. F = {xy|xy--> nebo yx--> ∈ R} - odp. rez v puv. grafu. |F| ≥ Ke(G) ≥ k, c(R) = |R| ≥ |F|. => ∃ tok: w(f) ≥ k. vezmu takovy tok, zrusim cirkulace => f(xy-->) = 1 => f(yx-->) = 0!! k hranove disj. cest vytvorim indukci podle toku - ze z vyteka k hranami "1", musi se dostat do s. z nich dostanu neorientovane hranove disj. cesty v G.
  • Veta 12 - Menger : G je vrcholove k-souvisly <=> ∀ u,v ∈ V(G) ∃ ≥ k vrcholove disjunktnich cest z u do v (cesty mohou mit spolecne jen vrcholy u,v, zadne jine).
    Dk: G = Kn - najdu snadno. jinak: <= A vrch. rez, u,v v ruznych komp. G[V\A], A prerusuje kazdou vrcholove disj. cestu => |A| ≥ k.
    => dany lib. u,v. a) uv ∉ E(G): z G vyrobim sit: G' = ( V(G) ∪ V'(G) - {u',v}, {x'x|x∈ V(G)-{u,v} } ∪ {xy'|xy∈ V(G), y≠u, x≠v } ), z=u, s=v, c≡1. ∀ rez R v siti ∃ R': c(R')≤c(R). (jen "svislé" hrany) R' = {x'x|∃ xy' ∈ R & x≠u} ∪ {y'y| ∃ uy' ∈ R} (uv∉ E(G)!). A = { x|x'x ∈ R'} ⊂ V(G)-{u,v} je vrch. rez v G. |A| ≥ k => |R'| = |A| ≥ k. ∃ f: w(f)≥k - k orientovanych hranove disj. cest od u k v' v siti mi da k neorientovanych vrcholove disj. cest v G.
    b) uv∈ E(G) - G' := G - uv, z lemma 5 - Kv(G') ≥ Kv(G)-1 ≥ k-1, podle a) ex. k-1 vrchol. disj. cest, hrana uv je k-ta.
  • lemma 6 - usate : kazdy vrcholove 2-souvisly graf lze vytvorit z libovolne jeho kruznice pridavanim usi (ucho - cesta, ktera ma hrany disjunktni s hranami grafu, vnitrni vrcholy disj. s vrcholy grafu, krajni vrcholy ruzne).
    Dk: indukci - vzdy mohu pridat dalsi ucho (kdyz mi chybi hrana, pridam ucho na kterem lezi, stejne vrchol).
  • lemma 7 - o kontrakci : Mam graf G, |V| ≥ 5, Kv(G) ≥ 3, potom ∃ e ∈ E(G): Kv(G◦ e) ≥ 3. Postupnou kontrakci dostanu K4 (nebo z K4 postupne tvorim 3-souvisly graf).
    Dk: sporem necht ∃ A ⊂ V(G◦ e) rez, |A|≤2. ∀ e ∃ ue : {ue,xe} je rez v (G◦ e) => {ue,x,y} je rez v G. Vezmu takovou e = xy, takovy ue, aby nejvetsi komponenta K grafu G\{x,y,ue} byla co nejvetsi. ∃ z ∈ K': zue ∈ E(G) => ∃ w: {ue,z,w} je rez v G. (zue zkontrahovaná dává spolu s w řez v G ) v G\{ue,z,w} tvori K∪{x,y}\{w} souv. podgraf G'. ∀ a,b ∈ G' ∃ v G\{ue,w} cesta (3-souv.), cesty pres vrchol z jdou zkratit pres xy => G' je souv. podgraf G\{ue,z,w} a ma ≥ |K|+2-1>|K| vrcholu - spor s vyberem nejvetsi komp.

    • Rovinne grafy

  • steny nakresleni(!!) rovinneho grafu - useky roviny ohranicene nakreslenim hran.
  • lemma 1 : G rovinny, v ∈ V(G) ( e ∈ E(G) ) => ∃ rovinne nakresleni, t.z. v (e) je nakresleno na hranici vnejsi steny. Dk: kresleni do rovin ≡ kresleni na sferu - mnou zvolena stena necht obs. sev. pol => zobrazi se na nekonecnou stenu.
  • lemma 2 : Kv(G) ≥ 2, G rovinny => v ∀ rovinnem nakresleni je hranice ∀ steny (grafova) kruznice. Dk: indukci podle usateho lemma: dostanu rovinne nakr., zvolim kruznici, pridavam dalsi => furt plati, protoze pridanim ucha rozdelim stenu na 2, byla-li jeji hranice kruznice, mam zas 2 kruznice.
  • Veta 1 - Kuratowski : G je rovinny <=> neobsahuje deleni K5, ani deleni K3,3.
    Dk: <= - indukci podle poctu vrcholu.: n ≤ 4 OK - K5 i K3,3 maj vic. n <-- n - 1, n ≥ 5.
    a) Kv(G) = 0 - vic komponent, ty jsou mensi - z indukce.
    b) Kv(G) = 1 - ex. 1-vrchol. rez. vyhodim vrchol-> mam C1,..Ck (rovinne), podle lemma 1 mohu slepit.
    c) Kv(G) = 2 - ex. u,v, tvorici vrchol. rez. - G1 := G[C1 ∪ {u,v} ] + uv, G2 := G[C2 ∪ ... Ck ∪ {u,v} ] + uv. ty jsou rovinne - sporem necht ne: ∃ deleni BUNO K5 - pokud nepouziva u,v je v G1 - spor. pokud ano, je porad v G - spor s predp. vety => z ind. predp. rovinne, z lemma 1 mohu nakreslit (uv ani nemusi byt v G)
    d) Kv(G) ≥ 3. z lemma o kontrakci ∃ e: G◦ e je 3-souvisly. G◦ e obs. deleni K3,3,K5 => je i v puv. grafu (1x K5 implikuje K3,3!) => G◦ e je roviny. podle lemma 2 v G-xe je kazda stena kruznice => nakreslim xe doprostred, spojim s ost. x, pokud y by neslo spojit - (0-2 spol. sousedu s x) K3,3, (3 spol. s.) K5.
    => - K5 ani K3,3 neni rovinny (Eulerova nerovnost/pro bip.grafy), deleni grafu je rovine <=> graf je rovinny, podgraf rovinneho grafu je roviny.

    • Parovani v obecnych grafech

  • k-faktor je F ⊂ E(G), t.z. graf (V(G), F ) je k-regularni ( ∀ vrchol ma stupen = k ). k-faktorizovatelny graf - mnozinu hran je mozne napsat jako disj. sjednoceni k-faktoru. 1-faktor odpovida perfektnimu parovani.
  • lemma 1 : H neni disj. sjednoceni uplnych grafu <=> graf "tresnicka" (K1,2) ⊂ H. Dk: <= jasne, => ex.komponenta, ve ktere nejsou 2 vrcholy spojene hranou, vezmu lib. 3 vrcholy na NEJKRATSI ceste mezi nimi.
  • Veta 1 - Tutte : G ma perfektni parovani <=> ∀ mn. vrcholu A ⊂ V(G) : cl(G\A) (pocet komponent souvislosti s lichym poctem vrcholu v ind. podgrafu ) ≤ |A| tj. splnuje Tutteovu podminku.
    Dk: => zrejme - "liche" body z cl nemuzou vest jinam nez do A, tam musi byt dost bodu.
    <= pozorovani 1: graf splnujici T.P. ma sudy pocet vrcholu (pro A = ∅), pozorovani 2: G splnuje T.P => G+e taky - e vede mezi cli a clj - cl((G+e)\A) o 2 mensi; jinak stejny. pozorovani 3: uplny graf - splnuje T.P => ma perfektni parovani (musi mit sudy pocet vrcholu -> parovani hladovym zpusobem OK).
    Dukaz vety indukci podle m =|E(G)| pri |V(G)|≡ n. 1) uplny graf z pozorovani 3. 2) m <-- m+1: G+e splnuje T.P (pozorovani 2), z ind. predp. ma perfektni parovani. W := {x|∀ u∈ V(G)-x : ux∈ E(G) } = {x|deg(x) = n-1 }. G[W] je uplny.
    A) G\W je disj. sjednoceni uplnych grafu - vrcholy z cli mohu spojit s W, protoze T.P. plati i pro A=W, W a csi sparuji libovolne.
    B) G\W neni d.s.u.g. - ∃ x,y,s ∈ V; xy ∉ E, xs,ys ∈ E (lemma 1). s ∉ W => ∃ t, st ∉ E(G). G+xy, G+st - perfektni parovani M1, M2. (BUNO xy∈ M1, st∈ M2). M1 xor M2: necht C je komp. (V(G), M1 xor M2), obs. xy. -> a) st ∉ C => F = (C∩ M2) ∪ (M1 -C) je perf.parovani v G. b) st ∈ C: C1:= x,...s; C2:=t,...y; F = (C1 ∩ M2)∪ (C2 ∩ M1)∪{sy}∪(M1 -C) je p.p.
  • Veta 2 - Petersen : Kazdy 3-regularni graf bez mostu obsahuje perfektni parovani.
    Dk: z T.P.: A ⊂ V(G), ve 3-reg. grafu vedou z cli do A ≥ 3 hrany (1 nelze=>most, 2 nelze=>neni 3-reg.) --> 3|A| (3-reg.!) ≥ |E(A,cli)| ≥ 3 cl(G-A) => splnuje T.P.

    • Edmondsuv algoritmus na max. parovani v obecnych grafech

  • M - parovani, volny vrchol: v, degM v = 0 (nepatri do zadne hrany parovani); stridava cesta - v0 v1 ... vk - v2i, v2i+1 ∉ M, v2i+1 v2i+2 ∈ M ∀ i. volna stridava cesta - stridava cesta, ktera zacina i konci ve volnych vrcholech.
  • lemma 2 : M je nejvetsi mozne parovani v G <=> neex. volna stridava cesta. Dk: => - ∃ v.s.c. P => neni nejvetsi: M'= P xor M, |M'| = |M|+1. <= ∃ M', |M'|>|M|, M* = M xor M'. M* je disj. sjednoceni kruznic, cest a izol. vrcholu. kruznice nebo suda cesta - |M∩ C|=|M'∩ C|, licha cesta zac. a koncici v M - |M∩ C| > |M'∩ C| (o 1), v M' naopak - |M|<|M'|=> ex. licha cesta v M*, zac. a konc. v M', tj. v.s.c vuci M.
  • lemma 3 : graf G, parovani M. ∃ licha kruznice c2k+1 v G obs. volny vrchol a, t.z. | M ∩ c2k+1 | = k. Potom M je nejvetsi parovani v G <=> M \ c2k+1 je nejvetsi parovani v G ◦ c2k+1.
    Dk: ∃ v.s.c. v G <=> ∃ v.s.c. v G' := G◦ c2k+1.
    => - necht p je v.s.c. v G, BUNO p ∩ c2k+1 ≠ ∅, potom bud z c2k+1 (=kvetu) vede s.c. zac. parovaci hranou (=stonek) - disj. s 1 casti p => lze, neni disj., cesta po stonku jde od kvetu => spojit kus cesty az ke stonku se zbytkem stonku smerem od kvetu. ke kvetu => po v.s. ceste p k vrcholu z pruniku nejblizsimu c2k+1, odtud po stonku, od c2k+1 po p.
    <= - mimo c2k+1 - ok, c2k+1 uprostred - spravnym smerem obejit, cesta konci ve vrcholu vzniklem kontrakci c2k+1 - najdu volny vrchol.
  • Edmondsuv les - stromy: rozdeleni na hladiny, max. co do inkluze. hladina V0 - volne vrcholy, z ∀ vrcholu V2k+1 vede prave 1 parovaci hrana do V2k+2, z V2k+2 vedou neparovaci hrany. G \ les := palouk. Z palouku muze vest hrana jen do liche hladiny, a nesmi byt parovaci, mezi vsemi vrcholy palouku musi vest parovaci hrany.
  • algoritmus : M := ∅, i := 0. While ( i = |M| ), i++, do:
    1. vybuduj les
    2. jestlize ∃ hrana mezi sudymi hladinami ruznych stromu ( = volna stridava cesta), zvetsi podle ni parovani -> M'
    3. ∃ hrana mezi lichymi hladinami tehoz stromu => najdi c2k+1, kontrahuj na G', rekurzivne zavolej; prepocitej kruznici pokud je nutne -> M'
    4. jestlize neni hrana mezi sudymi hladinami, return M.
    Dk: 2) v.s.c. ex. (obr.), 3.) ex. c2k+1, aby byl vrchol nejbliz ke koreni volny, prohodim parovani na sude ceste dolu (po vraceni z rekurze doplnim c2k+1 k parovacimi hranami. 4.) v G vedou hrany jen z liche do liche hladiny různých stromů nebo z liche do sude (nejsou parovaci) => uz neni v.s.c. (nemam sanci se dostat do volneho vrcholu).
    Slozitost: tvorba lesa - M, test na hrany - M, zlepseni parovani - N, return - 1, rekurze&zlepseni - (M+N)*N. celkem provadim max N-krat. => O((M+N)*N2)

    • Ramseyova teorie

  • Veta 1 - Ramsey (1): ∀ n ∃ N : ∀ graf G, |V(G)| = N : bud α(G) ≥ n nebo w(G) ≥ n ( nezavislost (max.nez. mn.) nebo klikovost grafu ≥ n ). Jina formulace: ∀ n ∃ N : ∀( E(Kn) = a1 ∪ a2 ) ∃ i ∈ {1,2}, ∃ A ∈ ( V(Kn)2 ) : ( A2 ) ⊂ ai. ( pro kazde rozdeleni dvojic bodů Kn ex. mnozina vrcholu velikosti n, ktera ma vsechny 2jice ve stejne skupine ).
    Dk: vytv. nesymetrickou verzi: ∀ k,l ∃ N : ∀(E(KN) = a1 ∪ a2) : ( ∃ A ∈ ( V(KN)k) a ( A2 ) ⊂ a1 ) nebo ( ∃ A ∈ ( V(KN)l) a ( A2 ) ⊂ a2 ). pro k=l=n dava puvodni. indukci podle k+l:
    1.) k=1 nebo l=1 - N=1 (vsechny hrany ∅ maj spravnou barvu :)).
    2.) (k,l) <-- (k-1,l),(k,l-1) podle ind. predp. necht staci N1, resp. N2. N:= N1 + N2. vezmu x ∈ V, hrany vycházející z x obarvene barvou i : Bi := {xy, y ∈ V(KN) \{x}} ∩ ai. |B1| ≥ N1 nebo |B2| ≥ N2 ( |B1| + |B2| = N1 + N2 - 1 ). BUNO |B1|≥N1, B:={y, xy ∈ B1}. z indukce ∃ A' ⊂ B: ( A'2) ⊂ a1, |A'|=k-1 -> A := A' ∪ {x} nebo |A'|=l -> A := A'.
  • Veta 2 - Ramsey (2): ∀ k ∀ n ∃ N : ∀ ( E(Kn) = a1 ∪ a2 ... ∪ ak ) ∃ i ∈ { 1,..k }, ∃ A ∈ ( V(Kn)2 ) : ( A2 ) ⊂ ai, tj. ∀ k ∀ n ∃ N : N --> (n)k2 ( ∃ Ramseovo cislo Rk2 ( n ) ).
    Dk: nesym. verze: Rk2( a1,...ak) = min N : N --> (a1,..ak)k2 - ∀ obarveni E(KN) pomoci k barev ∃ i, ∃ A ∈ ( V(KNai ) : (A2) ⊂ ai.
    1.) k = 1, 2 uz mame. 2) k+1 <-- k. vezmu k barev, sleju do 1 + 1 zustane. Rk+12 ≤ R22( Rk2(n), n) <-- toto jsou konecna cisla (z ind.). N := R22( Rk2(n), n ), B1 = a1 ∪ ... ∪ ak, B2 = ak+1. potom bud ∃ B ⊂ V(KN), |B| = Rk2(n), (B2) ⊂ B1, potom ale ∃ A ⊂ B, |A|=n, ∃ i: ( A2 ) ⊂ Ai. --> mam A. nebo : ∃ B ⊂ V(KN), |B| = n, ( B2 ) ⊂ B2 --> A = B.
  • Veta 3 : R22 ( n, m ) ≤ ( n+m-2n-1 ) (nesymetricke pro 2 barvy).
    Dk: indukci dle n+m, podle dukazu V1. R22(1,m) = R22(n,1) = 1. R22(n,m) ≤ R22(n-1,m)+R22(n,m-1) ≤ ( n-1+m-2n-2 ) + ( n+m-1-2n-1 ) - z vzorce o komb. cislech.
  • Dusledek 4 : R22( n ) ≤ ( 2n-2n-1 ). - symetricka verze V3.
  • Veta 5 : Rk2(3) ≤ 1 + k!* ∑i=0k( 1/i! ) ≤ 1 + ⌊ e*k! ⌋.
    Dk: indukci podle k. 1) R12(3) = 3 = 1 + 1!(1/0! + 1/1!). 2) k+1 <-- k - kolik potrebuju bodu, abych mel jistotu, ze po rozdeleni do (k+1) skupin ex. alespon 1 velikosti Rk2(3)? - (k+1)(Rk2(3) -1)+1 (aspon 1 vetsi nez prumer) => Rk+12(3) ≤ 1 + ((k+1)(Rk2(3)-1) + 1 ) - z ind.
  • Veta 6 - Schurovo lemma : ∀ k ∃ N ( ≤ ⌊ e*k! ⌋ ): { 1,2,... N } = a1 ∪ ... ∪ ak => ∃ i, ∃ x,y,z ∈ ai : x + y = z.
    vezmu cisla 1 ... N-1, necham lib. obarvit. druha skupina cisel (je jich M = N-1) - obarveni: hrana ab ∈ Bi <=> |a-b| ∈ ai. z Ramseye ∃ a,b,c ∈ {1,...M}, ∃ i : {ab,bc,ac} ⊂ Bi, tj. {b-a,c-b,c-a} ⊂ ai.
  • Veta 7 - Ramsey(3): ∀ p, k, n ∃ N : N --> (n)kp ( tj. ∃ Rkp(n) ).
  • Veta 8 - Erdös-Szekerés - ∀ n ∃ N: ∀ N bodu v rovine v obecne poloze (3 nelezi v primce) ∃ n z nich, tvoricich vrcholy konvexniho n-uhelniku - ES(n) = min N, t.z. toto plati.
    Dk: pro ES(1), ES(2), ES(3) - zrejme, ES(4) = 5 (rozbor pripadu). pro n ≥ 5: ES(n) ≤ R24(n,5) =: N. dostanu mn. bodu (:= X) v rovine, obarvim: ( X4 ) = akonv ∪ anekonv <-- barvy pro 4-ce tvorici/netvorici konvexni 4-uhelnik. Z Ramseye bud ∃ |A| = n, t.z. ( A4 ) ⊂ akonv, nebo ∃ |A| = 5, t.z. ( A4 ) ⊂ anekonv, coz nemuze nastat. --> mame n bodu, každá 4-ce z nich je v konv. poloze. pokud bych nemel conv(A) = n-uhelnik, ale k-uhelnik, k<n, potom ∃ p uvnitr conv(A). Vezmu triangulaci, p lezi uvnitr jednoho z trojuhelniku --> nelezi v konv. poloze s jeho krajnimi body - spor.