KMA/TGD1 Teorie graf˚ u a diskr´ etn´ı optimalizace 1 Zdenˇek Ryj´aˇcek, KMA UK 620
[email protected] http://www.kma.zcu.cz/Ryjacek 15.45 – 17.15, s pˇrest´avkou 15 minut Pˇredpokl´adan´e znalosti: v rozsahu KMA/DMA Diskr´etn´ı matematika. Skripta DMA: ˇ ˇ Plzeˇ - R. Cada, T. Kaiser, Z. Ryj´aˇcek: Diskr´etn´ı matematika. Skripta ZCU n, 2004. ´ - J. Holenda, Z. Ryj´aˇcek: Line´arn´ı algebra II - Uvod do diskr´etn´ı matematiky. ˇ Plzeˇ Skripta ZCU n, 1995. Literatura - Z´akladn´ı: http://www.kma.zcu.cz/TGD1
→ Nejsou to skripta, jen pomocn´y text k pˇredn´aˇsce ←
- Dalˇs´ı literatura: - L. Kuˇcera: Kombinatorick´e algoritmy. SNTL, Praha 1989. - J. Demel: Grafy a jejich aplikace. Academia, 2002. - J. Plesn´ık: Grafov´e algoritmy. Veda, Bratislava, 1983. - Dalˇs´ı jen v angliˇctinˇe
1
Forma v´ yuky - Folie z pˇredn´aˇsek budou pr˚ ubˇeˇznˇe na www str´ance pˇredmˇetu http://www.kma.zcu.cz/TGD1 - Cviˇcen´ı - RNDr. Jakub Teska, PhD,
[email protected] - RNDr. Jan Ekstein,
[email protected] - K samostatn´emu procviˇcov´an´ı a hran´ı“ jsou k disposici v´ yukov´e programy ” (aplety), odkaz ze str´anky pˇredmˇetu. Zkouˇska - P´ısemn´a - 3 pˇr´ıklady ´ ı - 2 ot´azky - Ustn´ Dotazy?
2
Definice. Graf je uspoˇr´adan´a dvojice G = (U, H), kde U je koneˇcn´a mnoˇzina a H ⊂ ( ) U 2
∪ U 2.
Graf G = (U, H) se naz´ yv´a – neorientovan´ y graf, jestliˇze H ⊂
( ) U 2 , 2
– orientovan´ y graf, jestliˇze H ⊂ U .
Definice. Bud’te G a G′ grafy. Zobrazen´ı f : U (G) −→ U (G′ ) se naz´ yv´a homomorfismus grafu G do grafu G′ , jestliˇze (x, y) ∈ H(G) ⇒ (f (x), f (y)) ∈ H(G′ ), a {x, y} ∈ H(G) ⇒ {f (x), f (y)} ∈ H(G′ ). Znaˇc´ıme f : G −→ G′ .
Definice. Bud’te G a G′ grafy a f : U (G) −→ U (G′ ) zobrazen´ı. Pak zobrazen´ı f ∗ : H(G) −→ H(G′ ), definovan´e vztahy f ∗ ({u, v}) = {f (u), f (v)}, a f ∗ ((u, v)) = (f (u), f (v)), se naz´ yv´a zobrazen´ı indukovan´e zobrazen´ım f . Tedy: f : U (G) −→ U (G′ ) je homomorfismus pr´avˇe kdyˇz h ∈ H(G) ⇒ f ∗ (h) ∈ H(G′ ).
3
Definice. Bud’te G, G′ grafy, f : G −→ G′ homomorfismus. Pak ˇrekneme, ˇze f je uzlov´ y monomorfismus, je-li f prost´e, uzlov´ y epimorfismus, je-li f na, hranov´ y monomorfismus, je-li f ∗ prost´e, hranov´ y epimorfismus, je-li f ∗ na, monomorfismus, je-li f i f ∗ prost´e, epimorfismus, je-li f i f ∗ na, isomorfismus, je-li f i f ∗ prost´e a na.
Pozn´ amky. 1. Ekvivalentnˇe, f : U (G) −→ U (G′ ) je isomorfismus, jestliˇze f je prost´e a na (bijekce), a plat´ı (x, y) ∈ H(G) ⇐⇒ (f (x), f (y)) ∈ H(G′ ), a {x, y} ∈ H(G) ⇐⇒ {f (x), f (y)} ∈ H(G′ ). 2. Znaˇc´ıme G ≃ G′ . 3. Relace ≃ je ekvivalence.
4
1. Kter´e z tˇechto graf˚ u jsou isomorfn´ı? •
•
•
............................................................................................................................... ............ .......... ..... ........ ....... .... ..... ........ ....... ..... ..... ....... ....... ..... ....... ..... ....... ........ . . ....... . . ..... . . ... ....... ..... ..... ................... .... ..... ..... ..... .......... ..... ............. ............. ......... . . . . . . . . . . . . . . . . . ... .. .. .... ....... ......... ..... .............. ....... ..... ....... ..... ....... ....... ..... ........ ....... . ..................................................................................................................................................... ....... . ..... .. . . . ....... ..... ....... .. . . . . . . . . ....... . . . ..... ... . ....... ........ . . . . . . . . ..... ...... ........... . ......... .......... ..... ............. ............. ......... . ..... ..... .................. . ..... ..... . . . . . . . . ....... .. .... ....... ..... ....... ....... ........ ..... ............ . . . ....... ..... .. ........ . . ....... ..... . . . ............. ....... .... . . . . ........ ....... ...............................................................................................................................
•
• •
•
•
.......................................................................... ...... . ... ... ... .... ... .... ... ..... ... ... .. ... . ... .. . ... . . . . ... ... . ... ... ... ... .. . . . ... . . . ... . .. ... . . . . . ... ... . . ... . . . ... ... . .. . . ... . . . ... . ... . ... . . ......................................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......................... ...... ... .. ...... ...................... . ... .. ... .. . . . . ... ... .... ... ... .. ..... . . . ... . . ... . .. ... . . . . . ... . .. ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. ... ... . . . . . ... . ... .. ... ... ... ... ... .. ... ..... .. .... ... ... .....................................................................................
•
•
•
•
•
•
.................................................................................................................................... .. ... ...... ..... .. ... ....... ..... .... ..... ... ..... ... ..... ..... . ..... . .... . ... . ..... ..... .... ... ..... ..... . . ..... . ... ... . ..... .... . . . ... ... ..... ... . . . ..... ... ... . ... . ..... . . ... ... . ..... ... . . . ... ... . ..... . ..... ........ ... ... ........ ... ... ... ....... . . . ... ... . ..... ... . . . . . ... ... . ..... ... . . . . . ... ... . ..... ... . . . . . ... ... . ..... ... . . . . . . ... ... .................................................................... . . . . ... ... ..... ... . . . . ... ... . . ..... ... . . . . ... ... . . ..... .. . ..... ... ......... ..... .... ... ....... ..... .. ....... .......... ...........................................................................................................................
•
• •
•
•
•
....... ........ ... ... ... .. .... .... . . ... ... ... ... .... ..... ... ... .... ... ... . . ... ...... ... ... ...... .. . ... . ... .... . ... . ... ... ... ... . . ... ... .. . . ... ... ... .. . . ... .. ..... ..... ... . . ... . . . . . . ... ........ ... . ... . . . . ... ... ........... . . .. . . . . ... ......... ..... . . .. . ... . . . . . . ......... .... ... . .. . . . . . . ...... . ... . ... . . . . . . . . . . . . ...... .. .. ... .......... . . . . . ...... .... .. .. ......... . . . . ...... .... . . .......... ....... . . .....................................................................................................................................
•
•
•
•
2. Kter´e z tˇechto graf˚ u jsou isomorfn´ı? (d. cv.) •
........ ..... .. ..... ..... .... ........... ...... ...... ... ..... ...... . . ... . . . ...... ... ...... ...... ..... . ...... . . . . . ... ...... .... . . . . . . ...... ... . .... . . . . ...... . . . . ... ...... ..... . . . . . . ...... . .... .... . . . . . . . ... ............. . ...... . . . . ... ............. .......... .. ............................................................................................................ .... ... ...... . . . . . . ... . . . . ... ...... . ... ... .......... ...... .... ... ... ...... .. ... ........ ... ....... ... .. ... ... .. .......... ............ . . . . . . . . . ... ............ ... ... ... ... . ....... ... ... ... ........ .......... ..... ...... .. ... .. ... ...... ........ .. ... . ............. . . . ...... ... ... ... ... ... ... ... ... ... ... ... ... ..... ... .... ... .. ... ... .............................................................................................
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
............... ......... ..... ................. ......... ......... ... ......... ......... ... ......... ......... . . . . . . . . ... . ... ........... . ....... . ... .. ...... ..... ... . ... ..... ..... .... . . .. . . . . ..... ... ... . .. .... ..... . . ... . . .. ..... ... ... ..... ... ..... ... ... ..... ..... ... ... ... ..... ..... . .. . . . . ... ..... .. ....... .. . . . ... ..... .. .... .. ..... .. ..... .. . ................................................................................................................................................................... . . . . ... . . .. . . ... ... ....... . .. ... . . . . .. . ... .. ..... .... ........ ... .. ..... ..... . . . . . . . .... ... .. .... ... ... ................................................................ ... ... ... ..... ..... ... .. ..... ..... ... ..... ..... .. ... . . . . . . . ..... .. . ... ....... ..... .. .... ... ...... ...... ... ....... ......... ....... ... ......... ......... . . . . . . . . . ......... .. ..... . . . . ......... . . . . . ......... ... ............. ..........
............................................................................... ... ............. .... .... ....... ....... ... ... ....... ....... .. ... . . ....... ............ ... ... ........... . ... . ....... . . . . . . . . ... . ....... .... .. . . . . ... . . . . . . . ....... .... ... . . . ... . . . . . . . ....... ... . ..... . . . . . . . . . . ... ..... . . . ............. ... . ... . . . . .... ... . ....... . . . ... . . . . . . . . ....... ... .... . . . . .. . ... ....... . . . . . . ... . . . ....... .......... . . . . . . . ..... ........ . . . . ..... . . . . ... ....... ... . ........... . . . .. . . ... ....... . . . . .. . .... .... . . ... ........ ... . . . . . . . . . . ....... .. ... ... .... ............. ........ ... ... ... ... ... ............. ......... ....... ... ... ... ... ... .......... . ....... .. . ... . . . . . . . . . . . . . . . . ....... .. ....... . ... . ............... .... ... ... .... . ... .. ... ..... ... .. ... .... ... ... . . . . ..... ...................................................................................
•
•
• •
•
•
•
•
5
•
•
•
•
.................. .......... ... ................... ......... .......... .... .......... .......... ........... .... . . ... ... ... ...... ... .. ... ... .... . . .. . .. .. ..... . . . . . . ... ... ... ... ... .... ... .. ... ... ... ... ... ... ... .. ... ......................... ....... .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . . . . . . . . . . . . . ............................ .... .. ................................. . . . . . . ... ..... ... . . . . . . . ... ... .. ... . .... ... ... .. ... .. ... ... .. ... ............. ............. ..... . ... . ......... .. ..... ... ... ..... ......... ... ... ... ............. ....... .... ... ... ....... ....... ... ... ... ....... ... ....... . ... . . . . . . . . . . ....... . ... ... ........ ....... .. ... ..... ........... ...... ... ... ..... . ..... ..... .... ..... ..... ... ....... . . . ..... . . . . ..... .. ..... .... . . . . . . . . . ..... ..... ... . ... . . ..... . . . . . . ..... ..... ...... .. ....... ..... .... ..................................................................
•
•
•
•
•
•
•
•
•
Neorientovan´ e grafy
´ y graf: Upln´
⟨1, n⟩ Kn = ⟨1, n⟩, 2
Cesta d´elky n ≥ 0: Kruˇznice d´elky n ≥ 3:
Pn = (⟨0, n⟩, {{i, i + 1}| i ∈ ⟨1, n − 1⟩}}) Cn = (⟨1, n⟩, {{i, i + 1}| i ∈ ⟨1, n − 1⟩} ∪ {{1, n}}) KU,U ′ = (U ∪ U ′ , {{x, y}}| x ∈ U, y ∈ U ′ })
´ y sud´y (bipartitn´ı) graf : Upln´ (U ∩ U ′ = ∅) Speci´alnˇe, Kp,q = K⟨1,p⟩,⟨p+1,p+q⟩ .
Definice. Stupeˇ n uzlu u v grafu G je poˇcet hran grafu G, kter´e obsahuj´ı uzel u. Stupeˇ n uzlu u v grafu G znaˇc´ıme dG (u).
Vˇ eta. Pro kaˇzd´ y graf G plat´ı
∑
dG (u) = 2|H(G)|.
u∈U (G)
6
Definice. Necht’ |U (G)| = n. Oˇc´ıslujeme uzly grafu G tak, ˇze dG (x1 ) ≥ dG (x2 ) ≥ . . . dG (xn ). Pak koneˇcn´a nerostouc´ı posloupnost dG (x1 ), dG (x2 ), . . . , dG (xn ) se naz´ yv´a soubor stupˇ n˚ u grafu G.
Vˇ eta. Necht’ s1 ≥ s2 ≥ . . . ≥ sn , n ≥ 2. Pak je posloupnost s1 , s2 , . . . , sn grafov´a pr´avˇe kdyˇz je grafov´a posloupnost s2 − 1, s3 − 1, . . . , ss1 +1 − 1, ss1 +2 , . . . , sn .
7
ˇ Definice. Bud’te G1 , G grafy. Rekneme, ˇze G1 je podgrafem grafu G, jestliˇze U (G1 ) ⊂ U (G) a H(G1 ) ⊂ H(G), G1 je faktorem grafu G, jestliˇze U (G1 ) = U (G) a H(G1 ) ⊂ H(G). Bud’ X ⊂ U (G). Pak graf (
( ))
G1 = X, H(G) ∩ X2 se naz´ yv´a podgraf grafu G indukovan´ y na mnoˇzinˇe X. Je-li G1 podgrafem grafu G, znaˇc´ıme G1 ⊂ G. Definice. Necht’ f : G1 −→ G je homomorfismus. Pak podgraf f (G1 ) ⊂ G, definovan´ y pˇredpisem f (G1 ) = (f (U (G1 )), f ∗ (H(G1 ))) se naz´ yv´a obraz grafu G1 pˇri homomorfismu f ( homomorfn´ı obraz“). ”
Definice. 1. Bud’ G graf, u, v ∈ U (G), a necht’ f : Pk −→ G je homomorfismus takov´ y, ˇze f (0) = u a f (k) = v. Pak se graf f (Pk ) naz´ yv´a sled d´elky k z uzlu u do uzlu v v grafu G. 2. Je-li nav´ıc f hranov´ y monomorfismus, pak se f (Pk ) naz´ yv´a tah (d´elky k z u do v v G). 3. Je-li nav´ıc f uzlov´ y monomorfismus, pak se f (Pk ) naz´ yv´a cesta (d´elky k z u do v v G).
8
ˇ Definice. Rekneme, ˇze graf G je souvisl´ y, jestliˇze pro kaˇzd´e u, v ∈ U (G) existuje v G sled z u do v.
Vˇ etiˇ cka. Graf G je souvisl´ y pr´avˇe kdyˇz pro kaˇzd´e u, v ∈ U (G) existuje v G cesta z u do v.
ˇ Definice. Bud’ G′ ⊂ G. Rekneme, ˇze graf G′ je komponenta grafu G, jestliˇze 1. G′ je souvisl´ y graf, 2. je-li G′ ⊂ G′′ ⊂ G a G′′ je souvisl´ y, pak G′ = G′′ . (Tedy: komponenty grafu G jsou jeho maxim´aln´ı souvisl´e podgrafy.)
Oznaˇ cen´ı. Minim´aln´ı stupeˇ n grafu: δ(G) = min{dG (U )| u ∈ U (G)} Maxim´aln´ı stupeˇ n grafu: ∆(G) = max{dG (U )| u ∈ U (G)} Neˇrekneme-li jinak, pak vˇzdy znaˇc´ıme |U (G)| = n a |H(G)| = m.
Vˇ etiˇ cka. Je-li δ(G) ≥ n2 , pak je G souvisl´ y.
Tvrzen´ı. (Vlastnosti souvisl´ ych graf˚ u) Necht’ G je souvisl´ y graf. Pak 1. existuje uzel u ∈ U (G) tak, ˇze graf G − u je souvisl´ y, 2. m ≥ n − 1.
9
Definice. 1. Bud’ f : Ck −→ G homomorfismus. Pak se graf f (Ck ) naz´ yv´a uzavˇren´ y sled v grafu G. 2. Je-li nav´ıc f hranov´ y monomorfismus, pak se f (Ck ) naz´ yv´a uzavˇren´ y tah v G. 3. Je-li nav´ıc f uzlov´ y monomorfismus, pak se f (Pk ) naz´ yv´a kruˇznice v G. ˇ ıslo k se naz´ C´ yv´a d´elka (uzavˇren´eho sledu, uzavˇren´eho tahu, kruˇznice).
Definice. Souvisl´ y graf, kter´ y neobsahuje jako podgraf ˇz´adnou kruˇznici, se naz´ yv´a strom.
Vˇ eta. N´asleduj´ıc´ı tvrzen´ı jsou ekvivalentn´ı. 1. G je strom. 2. Pro kaˇzd´e u, v ∈ U (G) existuje v G pr´avˇe jedna cesta z u do v. 3. G je souvisl´ y a m = n − 1. 4. G je souvisl´ y a nem´a ˇz´adn´ y souvisl´ y vlastn´ı faktor.
Definice. Bud’ G souvisl´ y graf. Graf T ⊂ G se naz´ yv´a kostra grafu G, jestliˇze 1. T je strom, 2. T je faktor grafu G.
Vˇ etiˇ cka. V kaˇzd´em souvisl´em grafu existuje alespoˇ n jedna jeho kostra.
10
Ohodnocen´ e grafy Definice. Bud’ G graf. Funkce w : H(G) −→ (0, ∞) se naz´ yv´a (hranov´e) ohodnocen´ı grafu G; graf se zadan´ ym ohodnocen´ım se naz´ yv´a ohodnocen´ y graf.
Necht’ G je ohodnocen´ y graf. Uzly grafu G oˇc´ıslujeme 1, . . . , n, a pro 1 ≤ i, j ≤ n poloˇz´ıme
w({i, j})
0
wi,j =
jestliˇze {i, j} ∈ H(G), jinak.
yv´a v´aˇzen´ a matice sousednosti grafu G. Matice W(G) = [wi,j ]ni,j=1 se naz´
Speci´alnˇe, neohodnocen´ y graf povaˇzujeme za ohodnocen´ y wi,j = 1. Matice sousednosti: A(G) = [ai,j ]ni,j=1 , kde
1
jestliˇze {i, j} ∈ H(G),
0
jinak.
ai,j =
Matice incidence (uzlo-hranov´a): oˇc´ıslujeme uzly u1 , . . . , un a hrany h1 , . . . , hm a poloˇz´ıme I(G) = [bi,j ]n,m i,j=1 , kde
1
jestliˇze ui ∈ hj ,
0
jinak.
bi,j =
Vˇ eta. I(G)(I(G))T = A(G) + S(G), kde S(G) = diag(dG (u1 ), . . . , dG (un )).
11
Minim´ aln´ı kostra grafu
Vˇ eta. Bud’ G souvisl´ y ohodnocen´ y graf a K jeho souvisl´ y faktor, pro kter´ y ˇc´ıslo
∑ {i,j}∈H(K)
nab´ yv´a minim´aln´ı hodnotu. Pak K je kostra grafu G.
Algoritmus 1. 1. Poloˇz G0 = G, i := 0. 2. Existuje v Gi kruˇznice Ci ? - Ano: v Ci najdi hranu hi s maxim´aln´ım ohodnocen´ım, poloˇz Gi+1 = (U (Gi ), H(Gi ) \ {hi }), i := i + 1 a opakuj 2. - Ne: Gi je hledan´a minim´aln´ı kostra.
Algoritmus 2. 1. Zvol u ∈ U (G) a poloˇz G0 = ({u}, ∅), i := 0. 2. Je Gi faktor grafu G? - Ne: mezi vˇsemi hranami {x, y}, pro nˇeˇz x ∈ U (Gi ) a y ∈ / U (Gi ) najdi tu, kter´a m´a nejmenˇs´ı ohodnocen´ı, poloˇz Gi+1 = (U (Gi ) ∪ {y}, H(Gi ) ∪ {{x, y}}), i := i + 1 a opakuj 2. - Ano: Gi je hledan´a minim´aln´ı kostra.
12
w
Definice. Nechť G je graf, u, v ∈ U (G). Vzdáleností uzlů u, v v grafu G (značíme dG(u, v)) rozumíme nejmenší délku cesty z uzlu u do uzlu v v grafu G. Neexistuje-li v G cesta z u do v, klademe dG(u, v) = ∞.
Věta. Nechť G je graf, x, y, z ∈ U (G). Pak platí: (i) dG(x, y) je celé číslo, (ii) dG(x, y) ≥ 0 a dG(x, y) = 0 ⇔ x = y, (iii) dG(x, y) = dG(y, x), (iv) dG(x, y) + dG(y, z) ≥ dG(x, z), (v) je-li dG(x, z) > 1, pak existuje uzel y ∈ U (G) tak, že x 6= y 6= z a dG(x, y) + dG(y, z) = dG(x, z).
Definice. Nechť G je graf s ohodnocením w. Pro každou cestu P ⊂ G definujeme w-délku w(P ) cesty P předpisem w(P ) =
X
w(h).
h∈H(P )
Nechť u, v ∈ U (G). Pak w-vzdáleností uzlů u, v v grafu G (značíme dwG(u, v)) rozumíme nejmenší w-délku cesty z uzlu u do uzlu v v grafu G. Neexistujeli v G cesta z u do v, klademe dG(u, v) = ∞.
Pro u, v ∈ U (G): cesta z u do v v G nejmenší délky: nejkratší cesta cesta z u do v v G nejmenší w-délky: minimální cesta
1
Funkce dwG má také vlastnosti metriky: Věta. Nechť G je graf s ohodnocením w a nechť x, y, z ∈ U (G). Pak platí: (i) dwG(x, y) ≥ 0 a dwG(x, y) = 0 ⇔ x = y, (ii) dwG(x, y) = dwG(y, x), (iii) dwG(x, y) + dwG(y, z) ≥ dwG(x, z), (iv) je-li dG(x, z) > 1, pak existuje uzel y ∈ U (G) tak, že x 6= y 6= z a dwG(x, y) + dwG(y, z) = dwG(x, z).
Příklad. Graf G – železniční síť ČD ρ(x, y) – cena jízdenky z x do y (obyčejné jízdné 2. třída) CENÍK OBYČEJNÉHO JÍZDNÉHO ČD Vzdálenost (km) Obyčejné jízdné 2. třída (Kč) 001 - 006
10,-
007 - 010
16,-
011 - 015
22,-
016 - 020
28,-
Plzeň hl. n. – Nezvěstice
16 km 28,- Kč
Plzeň hl. n. – Starý Plzenec 10 km 16,- Kč Starý Plzenec – Nezvěstice
6 km 10,- Kč
Funkce ρ(x, y) není metrika.
2
Příklad: převozník, koza, vlk, zelí. Převozník sám
1 hod.
Převozník se zelím 2 hod. Převozník s kozou 3 hod. Převozník s vlkem 4 hod. Otázky: (i) Lze převoz uskutečnit? (ii) Jestliže ano, v jakém minimálním čase? (iii) Kolik má úloha minimálních řešení? ......... ......... ................... ................... ................... .................. .. .. .. ..... ........ ........ ......... ... ........ ..... ..... ..... ..... .. ........ . ..... . . . .... . . ..... ........ ... ... ..... ...... . . . . . . ... . . . . . ...... ....... ... .. ... ... ... ......... ... ..... ..... ... .. ..... ........ ... ... ......... ........ ..... .... . ... ........ . . . . . . . ..... .. ..... .. ........ .......... . . . . . . . . . . . . .................... ................... .................... ................... . . . . ... ....... ... ....... ... ... .. . ... .. .. . . ... ... ... ... .. .. .. .. . . . . ......... ............................ ............................ ................... .................. ..... ..... ...... ...... .. ... ... ..... ..... ........ ....... ... ... ... ... ... ......... ..... ..... ... ... .. .. . . ..... ......... . .... . . ... ... ... . . .......... . . .... . . ... .. ........................................................... ........ . . . . . ... . . ... . ... ... ... ....... . . . . . . .. ... . . . . . . . ..... .. ... ... . . ... ........ . . . . . . . .... .... ....... ......... .. .. . . . . . . . . . . . . . . . . . . . . . . ....... ....... ... ............. ........... ... .... ............................ . ......... ....................... ... ... ... ... ... ... ... .. .. . . ... ... ... ... ... ... ... ... ... ... ... .. .. . . ... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......... ......... . . ... ........... ........ .............. ........ .............. ........ .............. . . . ......... .............. ......... .............. . . . ......... ..... . . . . . . . . .... ..... .... .... ..... ..... ..... .... ... ... ... . . . ..... . . . . . ... . . . . .... .... ... ... ... ... ... . . . . . .. . . . . . . . ... . . . . . . ... ... ... ... ... . . .. .. ... ... ... ... ... ... ... ... ... ... .... .... . . .. .............................................................. . ..... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ... ... . ... ... ... . .. .. ... . .. ... . . . . . ... ... ... ... ... . . . . . .. ... . . . . . . . . . . . . . . ... ... ... ... ... . . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ...... ...... ...... ...... ...... ...... ............................ ........................... ............................ ............................. ........................... ........................... ... ... ... ... ... .. ... ... . ... ... ... ... ... ... ... ... ... ... ... .. ... . ... ... ... ... . ......... ........................ .......................... ...... ................... .................. ..... ...... ....... . .... .... ..... ..... ........ . . . . . ............ . . . . ... . . . . ... .. .. .. ... ... ......... ......... .... ... ... .. ... ... . ..... ..... ... . ..... . . ........................................................... ....... . . ... . . . .. . . ... ... . . ... ....... . . . .. . ... . . . . ... ..... ... . . .. ... ........ . . . . . . . . . . ..... ... ... ... .......... .. .. . . . . . . . . . . . . . . . ..... ..... . ..... ..... ........ ........ ................... .................. ....................... ....................... .......... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...... ... ...... . .......... . .. . . . . . . . . . ........... ........... .................... ................... . . . . . . . . . .... . ... ..... .. ........ . . ..... ... ... ........ . . . . . ..... ..... ... ... ..... .... . . . . . . . .... . ..... .... ..... ........ ... ... .. . ......... . . . . .. ... . . . ... . ... ........ ... ......... ... .. ..... ........ ... .. ..... ........ ..... .... ... ......... ..... .... ... ......... . . . . . . . . ........ ........ ......... ......... . . . . . . . . . . .................. .................. .................. .................. .......... ..........
PZ KV
KZ PV
∅, 1
KV PZ
Z PKV
Z,2
u
PKVZ ∅
∅, 1
K,3
V,4
K,3
VZ PK
∅, 1
Z,2
K PVZ
PVZ K
V,4
Z,2
V,4
KZ PV
PKZ V
V PKZ
K,3
∅, 1
PKV Z ∅, 1
PV KZ
KV PZ
Odpovědi: (i) ANO. (ii) 17 hodin. (iii) 2 řešení.
3
∅, 1
PK VZ
K,3
∅ PKVZ
v
Nechť G je ohodnocený graf. Uzly grafu G očíslujeme 1, . . . , n, a pro 1 ≤ i, j ≤ n položíme dwi,j = dwG(i, j). Matice Dw (G) = [dwi,j ]ni,j=1 se nazývá matice w-vzdáleností (w-distanční matice) grafu G. Speciálně, neohodnocený graf považujeme za ohodnocený wi,j = 1. Distanční matice: D(G) = [di,j ]ni,j=1, kde di,j = dG(i, j).
Definice. Buď G graf, m = |H(G)|. Řekneme, že G je eulerovský, jestliže v G existuje uzavřený tah délky m.
Věta. Graf G je eulerovský právě když G je souvislý a všechny jeho uzly jsou sudého stupně.
EUL Vstup: graf G Úkol: je graf G eulerovský? Výstup: ANO / NE
Důsledek. Úloha EUL je řešitelná v polynomiálním čase.
4
Definice. Buď G graf, n = |U (G)|. Řekneme, že G je hamiltonovský, jestliže v G existuje kružnice délky n.
Věta (Dirac). Nechť G je graf s n = |U (G)| ≥ 3 a δ(G) ≥
n . 2
Pak je G hamiltonovský.
TSP (Problém obchodního cestujícího) Vstup: ohodnocený graf G X
Úkol: najít v G hamiltonovskou kružnici C s minimální hodnotou
h∈H(C)
Výstup: kružnice C 14
F •
E •
......................................................................................................................................................................................................................................................................................................... ..... ..... .. ... ..... ......... ..... ........ .... ..... . ..... .... . . ..... .... ..... ... . . . . . . . ..... ..... .... .... ..... ..... .... .... . . . . . ..... . . . . . . ..... ... ..... .... . . . . . . . . . ..... ..... .. ... . . . . . . . ..... . ..... .. ... . . . ..... . . . . . . ..... .. ... ..... . . . . . . . . ..... ..... .. ... . . . . . . . . . ..... ..... .. . ... . . . ..... . . . . ..... .. ... . ..... . . . . . . . . ..... ..... .. ... . . . . . . . . ..... ..... .. ... . . . . . . ..... . . . ..... .. . ... . . . . . . . . ..... . .................................................................................................................................................... . . . . . ......... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..... ... .... . ..... . . . ..... .... . ... ..... . . . . . . . . ..... ..... .... ..... ..... ..... .... . .... . . . . . . ..... . . . ..... ... ... ..... ..... .... .... ..... ..... ..... ..... ..... ..... .... .... ..... ..... .... .... . . ..... . . . . . . . ..... ..... .... .... ..... ..... .... .... ..... ..... ..... ..... ..... ..... .... ..... ..... .... ..... . .... . . . . . . . ..... ..... . . ..... ..... ..... ..... ..... .... ..... ..... .... ..... .... ..... ..... ........ ..... ........ . . . . ......... . . ........................................................................................................................................................................................................................................................................................................
8
6
5
G •
A •
5
7
7
• B
6
5
H •
5
9
5
• D
8
• C
w(h).
Rozhodovací strom
A
.. ... ... .... .. ... ... .... .. ... ... .. . ... ... ... .... .. ... ... .. . ... ... ... .... .. ... ... .. . ... ... ... .... .. ... ... .. . ... ... ... .... .. ... ..... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
F
B
... ... ... ... . ... ... ... ... . ... ... .. .. . . . ... ... .. .. . . . ... ... .. .. . . . ... ... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ..
.. ... ... ... ... . . ... ... ... ... . . ... ... ... .. . . . ... ... ... .. . . ... .. ... ... ..... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
E
G
G
C
... ..... ..... ..... ..... . . . . ..... ..... ..... ..... ..... . . . . .. ..... ..... ......... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .
.... .... ..... ..... .... . . . . .... ..... ..... .... ..... . . . . .... .... ..... ..... .... . . . . ........ ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
.... ..... ..... ..... . . . ... ..... ..... ..... .... . . . . ..... .... ..... ..... ..... . . . ... ........ ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
.. ..... ..... ..... ..... . . . . ..... ..... ..... ..... ..... . . . . .. ..... ..... ......... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .
D
H
H
B
F
H
H
D
.... ........ ........ ........ ........ . . . . . . . . ........ .............. ........ ........ ........ ........ ........ ........ .......
...... ...... ...... ...... . . . . . . ...... ...... ...... ...... ...... . . . . . ............................................................... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ..
. ...... ...... ...... ...... . . . . . . ...... ...... ...... ...... ...... . . . . . ............................................................. ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .
..........................................................
..........................................................
. ..... ..... ..... ..... . . . . .... ..... ..... ..... ..... . . . . .... ..... ..... .................................................................. ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ..
..... ...... ...... ...... . . . . . . ...... ...... ...... ...... ...... . . . . . ................................................................ ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ..
...... ........ ........ ........ ........ . . . . . . . ....... .............. ........ ........ ........ ........ ........ ........ .......
H
............. ............... ............... ........................... ............... ............... ..............
C
............. ............... ............... ........................... ............... ............... ..............
D
..........................................................
C
............. ............... ............... ........................... ............... ............... ..............
G E
..........................................................
..........................................................
D
............. ............... ............... ........................... ............... ............... ..............
C
............. ............... ............... ........................... ............... ............... ..............
C
...... ........ ........ ........ . . . . . . . ....... ........ .............. ........ ........ ........ ........ ........ ........ .......
E
........ ........ ........ ........ . . . . . . . ...... ........ .............. ........ ........ ........ ........ ........ ........ .......
E
............. ............... ............... ........................... ............... ............... ..............
D
............. ............... ............... ........................... ............... ............... ..............
C G
..........................................................
..........................................................
E
............. ............... ............... ........................... ............... ............... ..............
D
..........................................................
H
.............. ............... ............... ........................... ............... ............... ..............
E
.............. ............... ............... ........................... ............... ............... ..............
6
G C B H C D B B D E C D B
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
H
.............. ............... ............... ........................... ............... ............... ..............
D
.............. ............... ............... ........................... ............... ............... ..............
D
.............. ............... ............... ........................... ............... ............... ..............
H
............. ............... ............... ........................... ............... ............... ..............
F D E C D F F D E G E H F
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
B B G G B G C C B E G E D H E H C D C
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
C G H B G D B
..........................................................
A
..........................................................
A
..........................................................
A
..........................................................
A
D E E H C H C D
C F E E G F F F G G
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
..........................................................
F D G E G F H
Čas potřebný ke zpracování vstupních dat velikosti n, jestliže je nutno provést f (n) operací a provedení jedné operace trvá jednu mikrosekundu. ........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ ... ...... ... ... ...... ... ... ...... ... ... ...... ... ... ...... ... ... ....... .. ... .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... .... ....... .. ... ... .... .... ......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... .. ... ... ... ... .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ...... .. ... ... ... ... .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... .. ... ... ... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... .. ... ... ... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... .. ... ... ... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ..... ... ... ... .. .. ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ... ... ... ... ...... .. ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ..... ... ... ... .. .. ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... .. ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ..... ... ... .. .. ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... .. ...................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
velikost vstupních dat n
počet operací f (n)
2n
n!
8 ms
n4 0,2 s
1s
77 000 let
1,6 ms
64 ms
2,6 s
12 dní
—
60
3,6 ms
0,2 s
13 s
36 600 let
—
80
6,4 ms
0,5 s
41 s
3, 6 · 109 let
—
100
10 ms
1s
100 s
—
—
200
40 ms
8s
27 min
—
—
500
0,25 s
125 s
17 hod
—
—
1000
1s
17 min
12 dní
—
—
20
n2 0,4 ms
40
n3
7
Předpokládáme, že jsme schopni daným algoritmem s časovou náročností f (n) zpracovat v daném časovém limitu vstupní data velikosti n = 100 a ptáme se, jak se zvětší velikost úloh, které jsme schopni zpracovat ve stejném časovém limitu, jestliže zvýšíme rychlost výpočtu 10×, 100×, 1000×. ......................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ...... ... ... ...... ... ... ...... ... ... ...... ... .. ...... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... .. ... ... ... ... ...... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................ ... .. .. ... ... ..... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... .. ... ... ... ... ...... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... .. ... ... ... ... ...... ... .................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................. ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... .. ... ... ... ... ...... ... ................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................... ... .. .. ... ... ..... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... ... ... ... ... ... ...... ... .. .... .... .... .... ........ .... ....................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
zrychlení výpočtu 1× 10× 100× 1000×
počet operací f (n)
n2 100 316 1000 3162
n3 100 215 464 1000
n4 100 177 316 562
8
2n 100 103 106 109
n! 100 100 100 101
Orientované grafy Orientovaný úplný graf:
~ n = (h1, ni, h1, ni × h1, ni) K
Orientovaná cesta délky n ≥ 0:
P~n = (h0, ni, {(i, i + 1)| i ∈ h1, n − 1i}})
~ n = (h1, ni, {(i, i + 1)| i ∈ h1, n − 1i} ∪ {(n, 1)}) pro C ~ 1 = ({1}, {(1, 1)}). n ≥ 2; pro n = 1 dodefinujeme C Cyklus délky n ≥ 1:
~ je orientovaný graf, u ∈ U (G). ~ Definice. Nechť G ~ je číslo Výstupní (polo)stupeň uzlu u v grafu G ~ ∩ H(G)|. ~ d−~ (u) = |{(u, x)| x ∈ U (G)} G
Vstupní (polo)stupeň uzlu u v grafu G je číslo ~ ∩ H(G)|. ~ d+~ (u) = |{(x, u)| x ∈ U (G)} G
~ platí Věta. Pro každý orientovaný graf G X
~ u∈U (G)
d− ~ (u) = G
X
~ u∈U (G)
~ d+ ~ (u) = |H(G)|. G
9
Definice. ~ graf, u, v ∈ U (G), ~ a nechť f : P~k −→ G ~ je homomorfismus 1. Buď G takový, že f (0) = u a f (k) = v. Pak se graf f (P~k ) nazývá orientovaný ~ sled délky k z uzlu u do uzlu v v grafu G. 2. Je-li navíc f hranový monomorfismus, pak se f (P~k ) nazývá oriento~ vaný tah (délky k z u do v v G). 3. Je-li navíc f uzlový monomorfismus, pak se f (P~k ) nazývá orientovaná ~ cesta (délky k z u do v v G). Definice. ~ je graf a f : C ~ k −→ G ~ je homomorfismus. Pak se graf f (C ~k) 1. Nechť G ~ nazývá uzavřený orientovaný sled délky k v grafu G. 2. Je-li navíc f hranový monomorfismus, pak se f (P~k ) nazývá uzavřený ~ orientovaný tah (délky k v G). 3. Je-li navíc f uzlový monomorfismus, pak se f (P~k ) nazývá cyklus ~ (délky k v G). ~ je (slabě) souvislý, jestliže jeho Definice. Řekneme, že orientovaný graf G symetrizace je souvislý neorientovaný graf. ~ je silně souvislý, jestliže pro Definice. Řekneme, že orientovaný graf G ~ existuje v G ~ orientovaný sled z u do v. každou dvojici uzlů u, v ∈ U (G) ~ je silně souvislý právě když pro každé u, v ∈ U (G) ~ Větička. Graf G ~ orientovaná cesta z u do v. existuje v G
10
~ s alespoň 2 uzly je silně souvislý právě Věta. Souvislý orientovaný graf G když každá jeho hrana leží v alespoň jednom cyklu. ~ 0 ⊂ G. ~ Řekneme, že graf G ~ 0 je kvazikomponenta (silná Definice. Buď G ~ jestliže komponenta) grafu G, ~ 0 je silně souvislý graf, 1. G ~0 ⊂ G ~ 00 ⊂ G ~ aG ~ 00 je silně souvislý, pak G ~0 = G ~ 00. 2. je-li G ~ jsou jeho maximální silně souvislé podgrafy.) (Tedy: kvazikomponenty grafu G
~ graf. Řekneme, že G ~ je acyklický, jestliže G ~ neobsahuje Definice. Buď G jako podgraf žádný cyklus. ~ acyklický a G ~ 0 ⊂ G, ~ pak G ~ 0 je acyklický. Věta. Je-li G ~ 0) se nazývá Definice. Uzel u ∈ U (G ~ 0, jestliže d+~ = 0, (i) vstupní uzel grafu G G ~ 0, jestliže d−~ = 0. (ii) výstupní uzel grafu G G
Větička. Každý acyklický graf má vstupní a výstupní uzel.
11
~ orientovaný graf a n = |U (G)|. ~ Následující tvrzení jsou Věta. Buď G ekvivalentní: ~ je acyklický, (i) G ~ má výstupní uzel, (ii) každý neprázdný podgraf grafu G ~ má vstupní uzel, (iii) každý neprázdný podgraf grafu G ~ čísly 1, . . . , n, že (iv) existuje takové očíslování uzlů grafu G ~ ⇒ i < j. (i, j) ∈ H(G)
ACYC ~ Vstup: graf G Úkol: je graf G acyklický? Výstup: ANO / NE Důsledek. Úloha ACYC je řešitelná v polynomiálním čase. ~ orientovaný graf, G ~ 1, . . . , G ~ k jeho kvazikomponenty. Definice. Buď G ~C s Orientovaný graf G ~ C ) = {G ~ 1, . . . , G ~ k} U (G a ~ C ) = {(G ~ i, G ~ j )| i 6= j a existují x ∈ U (G ~ i) a y ∈ U (G ~ j ) tak, že H(G ~ (x, y) ∈ H(G)} ~ se nazývá kondenzace grafu G. ~ orientovaný graf. Platí: Věta. Buď G ~ C je acyklický graf, (i) G ~ je silně souvislý právě když G ~ C je graf s jediným uzlem, (ii) G ~ je acyklický graf právě když G ~ =G ~ C. (iii) G 12
Ohodnocené orientované grafy ~ graf. Funkce w : H(G) ~ −→ (0, ∞) se nazývá (hranové) Definice. Buď G ~ graf se zadaným ohodnocením se nazývá ohodnocený ohodnocení grafu G; graf.
~ je orientovaný graf s ohodnocením w. Pro každou Definice. Nechť G ~ definujeme w-délku w(P~ ) cesty P~ předpisem cestu P~ ⊂ G w(P~ ) =
X
w(h).
h∈H(P~ )
~ Pak Nechť u, v ∈ U (G). ~ (značíme d ~ (u, v)) rozumíme nejmenší (i) vzdáleností uzlů u, v v grafu G G ~ délku orientované cesty z uzlu u do uzlu v v grafu G, ~ (značíme dw~ (u, v)) rozumíme nejmen(ii) w-vzdáleností uzlů u, v v grafu G G ~ ší w-délku orientované cesty z uzlu u do uzlu v v grafu G. ~ cesta z u do v, klademe d ~ (u, v) = dw~ (u, v) = ∞. Neexistuje-li v G G G
1
~ je ohodnocený graf. Uzly grafu G ~ očíslujeme 1, . . . , n, a pro 1 ≤ i, j ≤ Nechť G n položíme
w((i, j))
0
wi,j =
~ jestliže (i, j) ∈ H(G), jinak.
~ = [wi,j ]n ~ Matice W(G) i,j=1 se nazývá vážená matice sousednosti grafu G. Speciálně, neohodnocený graf považujeme za ohodnocený wi,j = 1. ~ Matice sousednosti grafu G:
~ = [ai,j ]ni,j=1, kde ai,j = 1 A(G) 0
~ jestliže (i, j) ∈ H(G), jinak.
~ Matice w-vzdáleností (w-distanční matice) grafu G: ~ = [dw ]n , kde dw = dw~ (i, j). Dw (G) i,j i,j=1
i,j
G
~ Distanční matice grafu G: ~ = [di,j ]n , kde di,j = d ~ (i, j). D(G) i,j=1 G
2
~ Výpočet distanční matice D(G): ~ je orientovaný graf a k ≥ 0. Prvek a(k) ~ k Věta. Nechť G i,j matice (A(G)) je ~ roven počtu sledů délky (přesně) k z uzlu i do uzlu j v G. ~ je roven nejmenší mocnině k, pro kteDůsledek. Prvek di,j matice D(G) (k) ~ k nenulový. rou je prvek ai,j matice (A(G)) ~ Výpočet w-distanční matice Dw (G): ~ je ohodnocený orientovaný graf. Nechť G ~ = [ci,j ]n Definujeme matici C(G) i,j=1 předpisem:
0
ci,j = ∞
wi,j
jestliže i = j,
~ jestliže i 6= j a (i, j) ∈ / H(G), ~ jestliže i 6= j a (i, j) ∈ H(G).
~ se někdy nazývá cenová matice grafu G0. ~ (Matice C(G) Definujeme „novéÿ operace: a ⊕ b = min{a, b}, a b = a + b, ~ při těchto operacích označíme D(k)(G). ~ a k-tou mocninu matice C(G) ~ je ohodnocený orientovaný graf a r nejmenší číslo pro něž Věta. Buď G ~ = D(r+1)(G). ~ Pak D(r)(G) ~ = Dw (G). ~ D(r)(G)
3
Algoritmus 3.1 (Floydův algoritmus) ~ 1. Položíme D0 = C(G). 2. Pro k = 1, . . . , n postupně vypočítáváme matice Dk = [dki,j ]ni,j=1, kde k−1 k−1 dkij = min{dk−1 ij , dik + dkj }.
~ 3. Dn = Dw (G).
Poznámka: dkij je minimální w-délka cesty z uzlu i do uzlu j množinou uzlů {1, . . . , k}. ~ grafu G ~ Věta 3.1. Algoritmus 3.1 nalezne w-distanční matici Dw (G) v čase O(n3).
4
Dijkstrův algoritmus (minimální cesta z uzlu u do uzlu v) 1. Uzlu u přiřaď trvalou hodnotu th(u) = 0, ostatním uzlům dočasnou hodnotu dh(u) = ∞. 2. Je-li x poslední uzel, jemuž byla přiřazena trvalá hodnota th(x), pak všem ~ a které ještě nemají trvalou hodnotu, uzlům y, pro něž (x, y) ∈ H(G) přiřaď novou dočasnou hodnotu dh(y) := min{dh(y), th(x) + w(x, y)}. 3. Pro uzel z s nejmenší dočasnou hodnotou polož th(z) := dh(z). 4. Má uzel v trvalou hodnotu? – NE: vrať se na 2., – ANO: th(v) je w-délka minimální cesty z u do v.
Poznámka: hrany (x, y), na nichž w(x, y) = th(y) − th(x), určují minimální cestu z u do v.
5
~ acyklický ohodnocený orientovaný graf a u, v ∈ U (G). ~ Definice. Buď G Orientovaná cesta z u do v maximální w-délky se nazývá kritická cesta ~ (z u do v v G). Příklad. Činnost Doba Bezprostředně trvání podmiňující činnosti A B C D E F G H I J
4 2 1 7 6 1 2 4 2 8
– – – A A A,B,C A,B,C C E,F,G,H G,H
Uzly – stavy ............................... ...... ..... .... ..... ... ... .. ... . ... .... .. .... ... ... .. ... . ...... ... . . .... .. ........... ....... . .... ....... ........... ......... ....... ............ ................................. ......... ....... .................... ..... .... ....... ..... . . . ....... . ..... .... . . . . ....... . . ..... ... ... ....... . . . . . ..... ....... ... .... . . ....... . . . . ..... ....... ... ... . . . . . . ....... ..... .. ... . ....... . . . . . . ..... ... ....... ... . . . . ....... . . ..... . ....... .... . . . . . . . ..... ....... .. ... . . . ....... . . . . . ..... . ....... ... . . . . . . ....... . . ..... .. ... . ....... . . . . . . ..... ....... .... ... . . . . ....... . . ..... . ... ....... . . . . . . . . ... .. ... ..... ....... ... . . ....... . . . . . . . ..... ........ ....... .... . . . . . . ....... ..... ... ........ ... . ....... . . . . . . . . . ....... ....... ......... .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....... . . . . . . . . . . . . . . . . . . . . . ........................ . . . . . ........ ........ ........ .... ............. ........ ...... ....... .... . ....... ...... . . ........ . . . . . . . . . . . . . . . . . . . . . . . . . ..... ..... ...... .... ... ....... ..... ..... ... ... . . . . . . . . . . . . . .................................. ...... ... ... ... ... .. .. . . . ... . . . . . ... . . . . ... ... ... . . . . . . ... . .... . . ... ... ... ... ....................................................................................................... ....................................................................................................... ....................................................................................................... ... . . . . . . . . ... . . . . . . . . . . . . . . . . ... .. . . . . . . . ... ... ... . . ...... ...... ...... ... .. . . . . . . ... ... ... .. . . . ... . . . . . . . . . . . ... ... ... ... .. .. .. .. . . . . . . . . . . . ..... . . ..... ..... .. .. ...... ..... ....... ...... ...... ...... ........... ..... .......... .............. ......... ................................. ................................. ......... ............. .................................. .......... ..... ..... ..................... ... ... ..... ..... ... .. .......... .......... ..... . . . . . . . . . . . . . ..... ..... .... ..... ......... ......... ..... ..... ..... ..... ... .... ... ... .... ... ..... ..... ..... ..... ..... ... ... ..... ..... . ..... . . . ..... . . . . ..... ..... .... .... .... ..... ..... ..... ..... ..... ... ... ..... ..... ..... ..... ... ... ..... ..... ..... . . ..... . ... ... ..... . ..... .... ..... ... ... ..... ..... ..... ... ... ..... ..... ..... ..... ..... ..... ... ... ..... ..... ..... . . . . . . . . ..... ..... .... ..... .... .... ..... . ..... ..... ... .... .. ... ... ..... . . ..... ..................... ..................... ............. ................................. ......... ............. ................................. ..... ......... ............ ............ ..... ..... ... ... ... ... ... ... ... ... ... ... ... ... ............ .... .... ... ... ... ..................................................................................................... . ... ... . .. .. . . .. ... ... . . . . ... ... .. .. . . . . .... .... ... ... ..... ..... ..... ..... ....... ....... ............................ ............................
hrany – činnosti
A,4
B,2
C,1
E,6
0
D,7
F,1
G,2
0
H,4
6
I,2
0
J,8
Uzly:
...................................... ...... ........ ..... ...... ..... ..... ... .... . . ... ... ... . .. . . ........................................................................................... ... ... ..... . . ... ..... .. ... .. ... ... .. ... . . ... .. . . . ... .. .... ... .. ..... ... ... ..... ..... ... ...... ..... . . . . ........ . . .....................................
i
t(i) T (i)
i: očíslování uzlů podle věty o acyklických grafech (zároveň ověření acykličnosti) t(i): minimální časové ohodnocení – minimální doba, za kterou lze dosáhnout stavu i T (i): maximální časové ohodnocení – čas, kdy je nutno stav i opustit, aby nedošlo ke zpoždění projektu
........... .......... .............. ..... ...... .... ... ... ... .. . ................................................................. ... .... ..... . ... ... ... ... .. ... .......... ... .. . . . ....... ... ... ....... .... ....... . ........... ......... ....... ............. ................................... ......... ....... .. .................... ..... ....... . . . . . . . . ....... . . . . ..... ... ... ....... . . . . . . ..... ....... ... .... . . ....... . . . . ..... ... ... ....... . . . . . . ....... ..... .. .... ....... . . . . . . ..... ... ....... ... . . . . ....... . . ..... .. ... ....... . . . . . . . ... ..... ....... ... . . . ....... . . . . ..... . ....... ... . . . . . . . . ....... ..... .. ... . ....... . . . . . . ..... ....... ... .... . . . . ....... . ..... . ... ....... . . . . . . . . . ....... ..... ... ... . . ....... . . . . . . ... ... .. ..... ....... ... . . . . . . . . ....... ..... ........ ... . ....... . . . . . . . . ..... ... ....... ....... ... . . . . . ....... . . . .......... ................ ... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....... ..... ....... ....... .......... ...... ....... ..... ......... ...... .... . ..... . . . . . . ........... . . . . . . . . . . . . . . . ...... . ..... ..... ..... ..... .. ... . . . .... . ............................... ...... . . . ... . . . ... ... ... . . ..... . .. . . . . . . . . ............................................................ ........................................................... ........................................................... . . . .................................................................. . . . . . . ... ... ... ... ... ... ............ .. ............ .. ............ .. ... .. . . . .... . . . . . . . . . . . . .. .. .. ... ... ... ... ...................................................................................................... ...................................................................................................... ...................................................................................................... ... . . . ... ... ... ... .. .. .. .. ... .... .... .... .... ... ... ... .. .. .. .. ... . . ... . . . . . . . . . . . . ... ... ... . . . . ... .. ... ... ..... ..... ... ... .... .... .... .... ..... .... ...... ..... ...... ...... ....... ...... ........... ..... ........... ... ................ ......... ........... ... ................ ................................... ......... ............ .................................... ......... ......... ..... ..... .................... ..... ...... . . . ..... . . . . . . . ..... . .. ..... ..... .. ..... ....... ....... ..... ..... .. ..... .. ..... ..... ..... ..... ..... ..... ... .... ... ... .... ... ..... ..... ..... .... . .. . ..... . ..... . .... . ..... .... ..... ... .... ..... ..... ..... ..... ... ... ..... ..... ..... ..... ..... ... ... ..... ..... ..... . . . . . . . . ..... ..... .... ..... ..... .... .... ..... ..... ..... ..... ... ... ..... ..... ..... ..... ... ... ..... ..... ..... . . . ..... . . . . . ..... ..... .... .... .... ..... ..... ..... ..... . ..... . ..... ... ... ..... .. ... .. ..... .... .... ........ ..... . . ..................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ......... ......... .... ............... ......... ............. .......... ........... ...... ............. ............ ..... ..... ... .... ... ... ... ... ... ... .. .. . . . . . . ............................................................ ............ ................................................................. ... ... .. .. ..................................................................................................... .. ... . ... ... ... ... ... .. .. ... . ... . .. ... .... ..... ... ... ... ... . . . . . . . . . . . ..... ..... .. .. ...... ...... ..... ..... .......... .... .............. .......... .... .............. ........ ........
2
4 4
A,4
1
B,2
0 0
4
F,1
4 4
C,1
6 10 12
G,2
0
3
D,7
E,6
0
H,4
0
5
6 6
1 2
Kritická cesta: 1, 2, 4, 5, 7 Kritické činnosti: A, G, J
7
I,2
J,8
7 14 14
~ Algoritmus (kritická cesta z u do v v G) ~ podle věty o acyklických grafech. 1. Očísluj uzly grafu G 2. Konstrukce minimálního časového ohodnocení t(i): a) uzlu 1 (tj. u) přiřaď t(1) = 0, b) pro i = 2, . . . , n uzlu i přiřaď ~ t(i) = max{t(j) + w((j, i)) | (j, i) ∈ H(G)}, c) t(n) je w-délka kritické cesty. 3. Konstrukce maximálního časového ohodnocení T (i): a) uzlu n (tj. v) přiřaď T (n) = t(n), b) pro i = n − 1, . . . , 1 uzlu i přiřaď ~ T (i) = min{T (j) − w((i, j)) | (i, j) ∈ H(G)}. 4. Kritická cesta prochází těmi uzly i, pro něž T (i) = t(i), a hranami (i, j) pro něž w((i, j)) = t(j) − t(i).
8
2. Toky v sítích ~ s ohodnocením hran r : H(G) ~ −→ Definice 2.1. Síť je orientovaný graf G ~ −→ R. (0, ∞) a ohodnocením uzlů a : U (G) ~ očíslujeme 1, . . . , n, Značení: uzly G ~ budeme a(i) krátce značit ai, pro i ∈ U (G) ~ budeme r((i, j)) krátce značit rij , pro (i, j) ∈ E(G) i, j = 1, . . . , n. ~ síť s ohodnocením uzlů ai a s ohodnocením hran Definice 2.2. Buď G ~ je nezáporné hranové ohodnocení x : H(G) ~ −→ h0, ∞), rij . Tok v síti G splňující následující podmínky: ~ platí 1. pro každý uzel i ∈ U (G) X
xij −
~ j;(i,j)∈H(G)
X
~ j;(j,i)∈H(G)
~ platí 2. pro každou hranu (i, j) ∈ H(G) 0 ≤ xij ≤ rij .
~ ai: intenzita uzlu i ∈ U (G) ~ rij : propustnost hrany (i, j) ∈ H(G) ~ se nazývá Uzel i ∈ U (G) zdroj, je-li ai > 0, stok, je-li ai < 0, neutrální uzel, je-li ai = 0.
9
xji = ai ,
~ je síť, A ⊂ U (G) ~ je množina uzlů, a položme Definice 2.4. Nechť G ~ \ A. Množina hran A¯ = U (G) ¯ = {(x, y) | x ∈ A, y ∈ A} ¯ (A, A) ~ se nazývá řez sítě G. Označení. ~ −→ R funkce na U (G), ~ označíme f (A) = Je-li f : U (G)
fi ,
X
i∈A
¯ = ~ −→ R funkce na H(G), ~ označíme g(A, A) je-li g : H(G)
X
¯ (i,j)∈(A,A)
gij .
~ je síť, x je tok v G ~ a nechť A ⊂ U (G) ~ je množina Tvrzení 2.1. Nechť G ~ Pak platí uzlů G. ¯ − x(A, ¯ A). a(A) = x(A, A)
~ existuje tok právě když a(U (G)) ~ = 0 a pro každou Věta 2.1. V síti G ¯ ~ je a(A) ≤ r(A, A). množinu uzlů A ⊂ U (G)
10
Síť s jedním zdrojem a jedním stokem ~ s jedním zdrojem z a jedním stokem s, nechť x je tok v G. ~ Síť G Zdroj z má intenzitu a ≥ 0 ⇒ stok má intenzitu −a. Číslo a se nazývá velikost toku x a značí se |x|. ~ jestliže pro každý tok x0 v G ~ Definice 2.5. Tok x je maximální tok v G, platí |x0| ≤ |x|. ~ je síť s jedním zdrojem z a jedním stokem s, a Definice 2.6. Nechť G ¯ je řez sítě G. ~ nechť (A, A) ¯ se nazývá propustnost řezu (A, A). ¯ Číslo r(A, A) ¯ je minimální řez sítě G, ~ jestliže pro každý řez (A0, A¯0) Řekneme, že řez (A, A) ~ platí sítě G ¯ ≤ r(A0, A¯0). r(A, A) ¯ odděluje uzly u, ~ dva uzly G, ~ pak řekneme, že řez (A, A) Jsou-li u, v ∈ U (G) ¯ v, jestliže u ∈ A a v ∈ A.
~ je síť s jedním zdrojem z a jedním stokem s, nechť Tvrzení 2.2. Nechť G ¯ je řez sítě G, ~ oddělující z a s, a nechť x je tok v G. ~ Pak platí: (A, A) ¯ − x(A, ¯ A), (i) |x| = x(A, A) ¯ (ii) |x| ≤ r(A, A).
1
~ Polocesta z u do w je posloupnost Definice 2.7. Nechť u, w ∈ U (G). u = v0, h1, v1, h2, . . . , hk , vk = w, kde vi jsou navzájem různé uzly, hi jsou hrany a pro každé i = 1, . . . , k platí buď hi = vi−1vi (pak jde o souhlasnou hranu dané polocesty) nebo hi = vivi−1 nesouhlasná hrana). ~ Rezerva polocesty P je nezáporné číslo Nechť x je tok v síti G. Θ(P ) = min{Θs(P ), Θn(P )}, kde Θs(P ) = min{rij − xij | (i, j) je souhlasná hrana P } a Θn(P ) = min{xij | (i, j) je nesouhlasná hrana P}. Polocesta P je rezervní, jestliže Θ(P ) > 0.
~ je síť s jedním zdrojem z a jedním stokem s, a Tvrzení 2.3. Nechť G ~ Existuje-li v G ~ rezervní polocesta ze z do s vzhledem nechť x je tok v G. k x, pak tok x není maximální.
~ síť s jedním zdrojem z a jedním Věta 2.2 (Ford, Fulkerson). Buď G ~ je rovna propustnosti minimálstokem s. Velikost maximálního toku v G ního řezu, oddělujícího z a s.
2
Algoritmus 2.1 (Ford–Fulkersonův algoritmus) 1. Jako výchozí tok x zvolme nulový tok: xij := 0 pro každou hranu (i, j) ∈ ~ H(G). ~ existuje nějaká rezervní polocesta P ze z do s, upravme 2. Jestliže v grafu G podél ní tok x:
xij + Θ pokud (i, j) je souhlasná hrana polocesty P ,
xij
xij := x − Θ pokud (i, j) je nesouhlasná hrana polocesty P , ij pokud (i, j) neleží na P ,
a pokračujme bodem (2). 3. V případě, že rezervní polocesta ze z do s neexistuje, je tok x maximální.
~ propustnosti všech hran celá čísla, pak Tvrzení 2.4. Jsou-li v síti G Ford–Fulkersonův algoritmus skončí po konečném počtu kroků.
3
Edmonds–Karpův algoritmus. Myšlenka: zvolíme vždy nejkratší rezervní polocestu ze z do s. Jedna z iterací kroku (2): máme nějaký tok x a hledáme nejkratší rezervní polocestu ze z do s. (a) T je strom na jediném uzlu z, Seznam uzlů L obsahuje jedinou položku z, Zdroj je označený, ~ jsou neoznačené. Všechny ostatní uzly sítě G (b) Je-li L 6= ∅, pak nechť v je první uzel seznamu L. – Je-li v = s, algoritmus končí. Jednoznačně určená polocesta spojující z a s ve stromu T je hledaná nejkratší polocesta. Upravíme podél této polocesty tok x jako ve Ford–Fulkersonově algoritmu. – Jinak označíme všechny neoznačené sousedy w uzlu v, pro něž (v, w) je nenasycená hrana nebo (w, v) je nenulová hrana, ve stromu T je připojíme hranami k v, a přidáme je na konec seznamu L. Vyřadíme uzel v ze seznamu L a pokračujeme bodem (b). (c) je-li L = ∅, pak rezervní polocesta ze z do s neexistuje a tok x je maximální.
4
3. Grafy a matice
Definice 3.2. Čtvercová matice A se nazývá rozložitelná, lze-li ji napsat ve tvaru
A =
A11 A12 0
A22
,
kde A11 a A22 jsou čtvercové matice řádu alespoň 1 a 0 je nulová matice, anebo lze-li ji do tohoto tvaru převést permutací řádků a stejnou permutací sloupců.
Ekvivalentně: A je rozložitelná, jestliže existuje permutační matice P tak, že
PAPT =
A11 A12 0
1
A22
.
~ ohodnocený orientovaný graf. Platí: Věta 3.2. Buď G ~ silně souvislý, pak je matice W(G) ~ nerozložitelná. a) Je-li G ~ 1, . . . , G ~ k kvazikomponenty grafu G, ~ očíslované tak, že v konb) Jsou-li G ~ C jsou pouze hrany (G ~ k, G ~ `) pro k < ` a očíslujeme-li uzly denzaci G ~ souhlasně s očíslováním kvazikomponent, tj. tak, že je-li i ∈ grafu G ~k a j ∈ G ~ ` pro k < `, pak i < j, pak matice W(G) ~ má tvar G
~ = W(G)
W11 W12 W13 . . . W1k 0
W22 W23 . . . W
0
0
W33 . . . W ...
0
0
0
2k 3k
,
. . . Wkk
~ i, i = 1, . . . , k, a tyto matice jsou již nerozložitelné. kde Wii = W(G)
Důsledek 3.1. Čtvercová matice A je nerozložitelná právě když její ~ diagram G(A) je silně souvislý.
2
Definice 3.3. Řekneme, že čtvercová matice A je slabě rozložitelná, jestliže existují permutační matice P a Q tak, že
PAQ =
A11 A12 0
A22
,
kde A11 a A22 jsou čtvercové matice řádu alespoň 1 a 0 je nulová matice. Čtvercová matice, která není slabě rozložitelná, se nazývá úplně nerozložitelná.
~ jehož množinu uzlů lze rozložit Definice 3.4. Bigraf je orientovaný graf G, na disjunktní neprázdné podmnožiny U1, U2 tak, že pro každou hranu ~ je u ∈ U1 a v ∈ U2. (u, v) ∈ H(G)
Definice 3.5. Buď A = [aij ] čtvercová matice řádu n; označme U1 množinu řádkových indexů a U2 množinu sloupcových indexů matice A. Bigraf ~ matice A je orientovaný graf B(A) s množinou uzlů U = U 1 ∪ U2 a množinou hran H = {(i, j)| i ∈ U1, j ∈ U2, aij 6= 0}.
3
~ bigraf s množinou uzlů U (G) ~ = U1 ∪ U2. Množina Definice 3.6. Buď G ~ jestliže pro množinu V ⊂ U1, ∅ 6= V 6= U1, se nazývá stabilní množina v G, uzlů ~ W = {j ∈ U2| ∃i ∈ V tak, že (i, j) ∈ H(G)} platí |W | ≤ |V |.
Věta 3.3. Čtvercová matice A je slabě rozložitelná právě když v jejím ~ bigrafu B(A) existuje stabilní množina.
4
~ je lineární, jestliže pro každý uzel Definice 3.7. Řekneme, že bigraf G u ∈ U1 je d−(u) = 1 a pro každý uzel v ∈ U2 je d+(v) = 1.
~ bigraf a G ~1 ⊂ G ~ jeho lineární podbigraf, pak říDefinice 3.8. Je-li G ~ 1 je párování v G. ~ káme, že G ~ (tj. G ~ 1 je faktorem ~1 ⊂ G ~ párování v G ~ takové, že U (G ~ 1) = U (G) Je-li G ~ pak říkáme, že G ~ 1 je perfektní párování v G. ~ bigrafu G),
Věta 3.4. ~ 1. Je-li A regulární matice, pak její bigraf B(A) má perfektní párování. ~ má perfektní párování, pak existuje regulární matice 2. Jestliže bigraf G ~ ~ A taková, že B(A) = G.
5
Definice. Strukturální matice řádu n ≥ 1 je čtvercová matice řádu n, u níž je dána pouze struktura nulových a nenulových prvků, ale nejsou určeny jejich konkrétní hodnoty. (Poněkud přesněji: na strukturální matici lze pohlížet jako na funkci hodnot jejích nenulových prvků.)
Pro každou strukturální matici A nastává právě jedna z následujících možností: (i) polynom det(A) je nenulový, a při náhodné volbě nenulových prvků matice A je matice A regulární s pravděpodobností 1, (ii) polynom det(A) je nulový a matice A je singulární při každé volbě jejích nenulových prvků. V prvním případě říkáme, že strukturální matice A je genericky regulární, ve druhém případě je A genericky singulární.
Věta 3.5. Nechť A je čtvercová strukturální matice. Pak platí: ~ A je genericky regulární ⇐⇒ B(A) má perfektní párování.
6
Definice. Nechť A je strukturální matice. Největší přirozené číslo k, pro které v matici A existuje genericky regulární podmatice řádu k, se nazývá generická hodnost matice A a značí se gh(A). ~ se nazývá párovací Definice. Počet hran největšího párování v bigrafu B ~ a značí se ν(B). ~ číslo bigrafu B
Věta 3.6. Nechť A je strukturální matice. Pak ~ gh(A) = ν(B(A)).
7
Největší párování v bigrafu je možno najít v polynomiálním čase převodem na ~ s U (B) ~ = U1 ∪ U2 přiřadíme síť G ~ tak, že úlohu maximálního toku: bigrafu B ~ přidáme kB – nový uzel z (zdroj), – nový uzel s (stok), – hrany (z, u) pro všechny uzly u ∈ U1, – hrany (v, s) pro všechny uzly v ∈ U2. Propustnosti všech hran jsou rovny jedné.
U1
U2
............................................................................................................................................................................................................................................. ... ... ... ... ... ....... ....... .... ......... ....................... . ....... . . . . . . ... ......... ..... .. ....... ....... .... ... ....... ....... .. ....... ...... . . . . . .... . . ....... . .............. ..... . . . . . . . ....... . . . . . . . . . ............. ............. ....... ..... . . . . . . . . . . . . . . . . . . . . . ... ........... ....... ...... ... . ..... . . . . . . . . . ....... . . . . . . . . . . .......... . . ...... .... ....... . . . . . . . . . . . . . . . . . . . . . . . . .......... .. ...... . ...... ..... . . . . . . .......... . . . . . . . . . . . . .......... ............. . ............ . ..... ................ . . . . . . . . . . . . . .......... ....... . . ......................... ......................... . . . ..... ............... . . . . . . .......... ....... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ....................... ... .. . . ............... . . . ..................... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .............................................................. ... .... .................................... ................ ......................... .... ... ................................... ....................... . . ....... . ........... .. ....... . . ... ...... .. . ....... . ....... . . ....... .. ...... . .. . ....... . . . . . . .. ....... ....... .... .... ....... ...... ....... ... ... ....... ....... ....... ... ... ....... ...... . . . ....... . . . . . . ....... ....... .... .... ....... ...... ....... ... ... ....... ....... ....... ... .. ....... ....... . . . . ....... .... . . . .. ...... ....... . .. . ........ ......... ............................. . ....... ... ... .... ... .... ... ..........................................................................................................................................................................................................................................
nové hrany
z •
• • • . . . •
~ bigraf B
• • • . . . •
nové hrany
s •
~ (celočíselný) maximální tok, pak hrany bigrafu B ~ s nenulovým Najdeme-li v G ~ tokem určují největší párování v B.
8
4. Míry souvislosti grafu
Definice 4.1. Hrana {x, y} ∈ H(G) se nazývá most grafu G, jestliže v grafu G neexistuje žádná kružnice, která ji obsahuje.
Tvrzení 4.1. Je-li graf G souvislý a hrana {x, y} jeho most, pak graf G − {x, y}, vzniklý odstraněním hrany {x, y} z G, je nesouvislý.
Věta 4.1. Má-li souvislý graf G most, pak má alespoň dva uzly lichého stupně.
Definice 4.2. Uzel x ∈ U (G) je artikulace grafu G, jestliže existují hrany {x, y1} a {x, y2}, které nepatří současně téže kružnici grafu G.
Definice 4.3. Buď G graf, G0 ⊂ G jeho souvislý podgraf. Řekneme, že G0 je blok grafu G, jestliže: a) G0 nemá artikulaci, b) jestliže G00 je souvislý graf bez artikulace takový, že G0 ⊂ G00 ⊂ G, pak G00 = G0.
1
Tvrzení 4.2. Buď G souvislý graf. Pak G nemá artikulaci právě když pro každé dvě jeho hrany existuje kružnice, na níž obě leží.
Důsledek 4.1. Pro každé dvě hrany bloku, který není mostem, existuje kružnice, na níž obě leží.
Věta 4.2. Buďte G1, G2 dva bloky grafu G. Pak buďto G1 = G2, nebo G1 a G2 nemají žádnou společnou hranu.
Definice 4.4. Buď G souvislý graf, B1, . . . , Br všechny jeho bloky a x1, . . . , xs všechny jeho artikulace. Graf B(G), definovaný předpisem U (B(G)) = {x1, . . . , xs, B1, . . . , Br }, H(B(G)) = {{a, b} | ∃i, j tak, že a = xi, b = Bj a xi ∈ U (Bj )}, se nazývá blokový graf grafu G.
Věta 4.3. Pro každý souvislý graf G je blokový graf B(G) stromem.
2
Definice 4.5. Buď G souvislý graf a x, y ∈ U (G). Množina B ⊂ H(G) taková, že 1) každá cesta z uzlu x do uzlu y obsahuje alespoň jednu hranu množiny B, 2) žádná vlastní podmnožina množiny B nemá vlastnost 1), se nazývá hranový řez grafu G mezi uzly x a y.
Definice 4.6. Nejmenší počet prvk˚ u hranového řezu mezi uzly x a y se nazývá hranový stupeň souvislosti grafu G mezi uzly x a y a značí se hG(x, y).
Definice 4.7. Buď G souvislý graf, x, y jeho uzly. Množina A ⊂ U (G) taková, že 1) každá cesta z x do y obsahuje alespoň jeden uzel z množiny A, 2) žádná vlastní podmnožina množiny A nemá vlastnost 1), se nazývá uzlový řez grafu G mezi uzly x a y.
Definice 4.8. Nejmenší počet prvk˚ u uzlového řezu, oddělujícího uzly x a y, se nazývá uzlový stupeň souvislosti grafu G mezi uzly x a y a značí se uG(x, y). Neexistuje-li uzlový řez mezi x a y, tj. jsou-li uzly x a y sousední, klademe uG(x, y) = |U (G)| − 1.
3
Definice 4.9. (i) Nejmenší z čísel uG(x, y) nazveme uzlový stupeň souvislosti grafu G a budeme je značit u(G). (ii) Nejmenší z čísel hG(x, y) nazveme hranový stupeň souvislosti grafu G a budeme je značit h(G). Řekneme, že graf G je uzlově (resp. hranově) k-souvislý, jestliže je u(G) ≥ k (resp. h(G) ≥ k).
Věta 4.4. Pro každý graf G platí u(G) ≤ h(G) ≤ δ(G).
•
•
•
•
•
•
•
•
•
•
•
.................................................................................................................................................................................................................................................................................................................. .. .. ... ............ ........ ........ ... .... ........ ........ ........ ........ ... ... ........ . ........ . . . . . ... ... . ........ ..... . . . . . ........ . ... ... . ..... . ........ . . . . . ... ... . ........ .. ..................................................................................................................................... ... ... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ....................................................................................................................... . . . . . . . . . . . ... ... ........ ..... . . . . . . . . . . . . ... ... ........ ..... . . . . . . . . . . . ... ... ........ ..... . . . . . . . . . . ... ... . ........ ..... . . . . . . . . . . . ... ... ........ ..... . . . . . . . . . . . ... .. ........ .... ........ ... ... ............... . ...........................................................................................................................................................................................................................................................................................................
. . .............. .............. ..... .. ........ ..... .. ........ ..... .. .. ...... ..... .. .. ...... ..... .... .... ......... ..... .... .... ......... . . . . . . . . ... ... ..... ..... . . ..... ..... ..... ..... ... ... ... ... ..... ..... ..... ..... ... ... ... ... ..... ..... ..... ..... .. .. ... ... ..... ..... ..... ..... ..... ..... .. .. ..... ..... ... . . . . . . . . . . . . . . . ..... ... ..... .. . . ... ... . . . ..... . . . . . . . . . . . . . ..... ... ... ... ... . . .... . . . . . . . . . . . . . . . . ............................................................................................................................................................................................................................................................................................................................. . . . . . . . . . . ... . ... ...... ... ... .. ....... ... . . . . . . . . . ..... .. . . . . . . . . . . . ... ..... ... ... ..... . ... .... .... .... . . . .. . ..... . . . . . . . . ... . . . . . . . . ..... ... ... ..... ... ... .. . . . . . . . . . . . ... . . . . ..... .... . . ... . . . ... ..... ... ..... ..... .. . ..... .. ... ...... ....... ..... ..... ... ...... ... .. ..... ..... ...... ...... . ... .. .... ..... ..... .. .......... ... ..... .... . . . . . . .. .......... . . . . . . . . . . . . ..... . ... ... ... ... ..... .... ..... ..... ... ... ... ... ... ..... .......... ... .... ..... ......... .......... ... ... ..... ... ... ..... ... ... .. .. ..... ... ... ........ ......... ... ... .... .. .. ..... .......... ..... ......... . . . . . . . .. . . . . ... . . . . . . . . . . ..... . ... ... .. ..... ... ..... ..... ..... ... ... ..... ... .. .. .. ..... ..... ..... ..... ..... ... ... ..... ... ..... ..... .... ... ..... ..... .... ... ... .......... ..... .. .. .. ...... ..... ... ........ ..... ... .. ..... .. .... .. .......... ... ... ....... . . . . . . ....... ... ......... ............. . .... ................................................................................................................................................................................................................................................................................
•
•
•
•
•
•
u(G) = h(G) = δ(G) = 3
u(G) = 2, h(G) = 3, δ(G) = 4
Věta 4.5. V každém grafu G platí h(G) ≤
•
2|H(G)| . |U (G)|
4
Věta 4.6 (Ford, Fulkerson).
Graf G je hranově k-souvislý mezi uzly
a a b, a 6= b, právě když v něm existuje k hranově disjunktních cest, vedoucích z a do b.
Věta 4.7 (Menger).
Graf G je uzlově k-souvislý mezi nesousedními
uzly a a b, právě když v něm existuje k uzlově disjunktních cest, vedoucích z a do b.
~ Konstrukce sítě G: ~ = {(x, i)| x ∈ U (G), i = 1, 2}, U (G) ~ = {((x, 1), (x, 2)) | x ∈ U (G)} ∪ {((x, 2), (y, 1)) | {x, y} ∈ H(G)} . H(G) Propustnosti hran: u hran typu ((x, 1) (x, 2)) položíme propustnost rovnu jedné, u hran druhého typu (tj. ((x, 2), (y, 1)) ) bude propustnost nekonečná. Zdrojem je uzel (a, 2), stokem je uzel (b, 1).
G
x •
..... ............. ..... .. ..... ..... .... ......... . . . ..... ... .... ..... .... ..... ..... ... ..... .... ... .... ..... . . . . . . ..... . .... . . . ..... . . . ... ..... . . . . . ..... . ... . . . . . ..... . ... . . . ..... . . .. . . . ..... . . . . . ..... .... . . . . . ..... . ... . . . ..... . . . ... . . ..... . . . . ..... ... . . . . . ..... .. . . . . . . ..... . . .... . . ..... . . . . .. ..... . . . . . . .... .. ......... . . . ..... . .... . ..... .... . . . . . . . ..... .... .. . ..... . . . ..... ... .... .... ..... ... ..... ..... .... ..... ... .... . ..... . . . . . ..... .... .... ..... .... ..... ... ..... ..... .... ... ..... .... . . . . . . ..... .... ..... .... .... ..... ..... ... ..... ..... ... ..... .... . . ..... . ... ..... .... . ..... .... ......... ..... .. .... ..... .. ..... ............. ...
a•
•b
• y
(x, 1) •
~ G
1
(x, 2) •
...... ............................................................................................................... .................................................. . .. . ........ .............. .... ........ ..... ............. ..... . .... . . . . ... ..... . .... ........... .. ..... ..... ........ .... ... ............... ....... ..... . ..... .......... . ......... . ..... .... . . . . . . . . . . . ........ ... . .. . ..... . . . . . . . . . . . . . . . . ... ........ ......... . .... ............. . . . ........ ..... . . . . ... . ............ ............... . . . . . ... ........... ....... . . . . . . ........... . . . . ... .............. .. ........... ... ............... .. ..... ......... . . . . . . . . . . ... ..... ......... ..... ....... . . . . . . . ........ . ..... . . . ... .. . ...... ........ . . . . ..... . . . . . . . . ... ........ .. .... . ..... . . . . . . . . . ........ . . . . . ..... ... .. . ..... . . ........ . . . . . . . . . . . . ..... ... .. ........ .. ..... . . . . . . . . . ........ . . . . . ..... ... .. ... ...... ........ . . . . . . . . . . . . . . ... .. .... .. ............ ................. . . . . . . . . . . . ....................................................................................... ... ............................................................................................................ . . . ....... ........ ............. ..... ..... . . . . ........... . . . . . . . ........ ..... .... . ... ....... . . . . . . . ........ . . . . . . . ..... ... . .... ..... ........ . . . . . . . . . . . . . . . . ........ ..... . ... ........ ........ ..... ... .... .... ....... ........ ... ..... ... ..... ........ ........ ... ... .... .. ........ ........ ... .... .. ........ ........ ........ . . . . . . . . . . . . . ........ ..... ... .... ...... ........ .... ... ... .... ......... ............. ... ... .............. ......... .. ... ......... ............. .. .............. . . ... ..... ........ . . . . . . . .. . ..... ......... ... ........ ..... ... ... ..... ... ........ ....... ..... ............... .... ... .............. ........ .. ..... .... .......... ......... ..... .... . . . . . . . . . . . . . . . . . ........ ..... . ........ .............. ..... ..... ..... ... ........ ..... .. ... ..... ....... ......... .............. .............. .... .... ... ..... .............. ......................... ................................................................................................................. ..... .
∞
(a, 1) •
∞ 1 • (a, 2) ∞ ∞
• (y, 1)
5
1
∞
∞
∞
∞ (b, 1) • 1 ∞ ∞
• (y, 2)
• (b, 2)
5. Prohled´ av´ an´ı graf˚ u a algoritmy k-souvislosti
Oznaˇcme: N mnoˇzinu uzl˚ u, kter´e jeˇstˇe nebyly probr´any, M mnoˇzinu hran, kter´e jeˇstˇe nebyly probr´any, D mnoˇzinu uzl˚ u, kter´ ych jiˇz bylo dosaˇzeno, ale ze kter´ ych jeˇstˇe vedou neprobran´e hrany. Algoritmus 5.1 (Prohled´ av´ an´ı grafu). 1. N := U (G), M := H(G), D := ∅. (inicializace) 2. Je-li N = ∅, v´ ypoˇcet konˇc´ı. (test ukonˇcen´ı) 3. Zvol v ∈ N a poloˇz N := N \ {v} , D := {v}. (volba prvn´ıho uzlu v komponentˇe) 4. Zvol libovolnˇe w ∈ D. (volba poˇc´ateˇcn´ıho uzlu hrany) 5. Hledej hranu v M obsahuj´ıc´ı w: (test pouˇzitelnosti w) - neexistuje: D := D \ {w}, a je-li D = ∅, jdi na 2, je-li D ̸= ∅, jdi na 4. - existuje: jdi na 6. 6. Zvol h = {w, z}, “projdi” ji, (tj. proved’ na n´ı urˇcen´ yu ´kol), a poloˇz M := M \ {h}; je-li z ∈ N , pak N := N \ {z} , D := D ∪ {z}, jdi na 4.
1
Vˇ eta 5.1. Algoritmus 5.1 prohled´a graf G v ˇcase O(n + m), kde n je poˇcet uzl˚ uam poˇcet hran grafu G.
Tvrzen´ı 5.1. Komponenty grafu lze nal´ezt v ˇcase O(m + n).
Nalezen´ı artikulac´ı grafu (Tarjan 1972) 1. Uzly oˇc´ıslujeme poˇrad´ım, ve kter´em byly zaˇrazeny do stromu prohled´av´an´ı, a tato ˇc´ısla oznaˇc´ıme p(x). 2. Pro kaˇzd´ y uzel x soubˇeˇznˇe postupnˇe vypoˇc´ıt´av´ame doln´ı ˇc´ıslo r(x) podle n´asleduj´ıc´ıch pravidel: a) pˇri objeven´ı nov´eho uzlu poloˇz´ıme r(x) = p(x), b) pˇri nalezen´ı chordy xy poloˇz´ıme r(x) = min {p(y), r(x)}, c) pˇri zpˇetn´em kroku z x do y poloˇz´ıme r(y) = min {r(y), r(x)}.
r(x) je nejmenˇs´ı poˇradov´e ˇc´ıslo uzlu, do nˇehoˇz se lze z uzlu x dostat orientovanou cestou, skl´adaj´ıc´ı se z hran stromu a (na konci) z pr´avˇe jedn´e chordy.
Uzel x s p(x) > 1 je artikulac´ı, pr´avˇe kdyˇz existuje jeho n´asledn´ık y ve stromu prohled´av´an´ı takov´ y, ˇze plat´ı r(y) ≥ p(x).
2
Generov´ an´ı hamiltonovsk´ ych cest a cykl˚ u Obecn´e schema backtrackingu budeme modifikovat n´asleduj´ıc´ımi pravidly. 1) Nebereme v u ´vahu chordy, 2) pˇri |D| = n testujeme existenci hrany do poˇc´ateˇcn´ıho uzlu; v´ ysledkem je cesta (hrana neexistuje) nebo cyklus (hrana existuje), 3) pˇri zpˇetn´em kroku se pt´ame, zda existuje n´asledn´ık s vyˇsˇs´ım ˇc´ıslem, jakmile jej ale nalezneme, tak pˇri n´asledn´em dopˇredn´em pohybu prozkoum´av´ame opˇet vˇsechny uzly grafu, kter´e nejsou v mnoˇzinˇe D.
3
Vˇ eta 5.2 (Dirac). Necht’ G je graf na n ≥ 3 uzlech. Je-li δ(G) ≥ n2 , pak je G hamiltonovsk´ y.
Vˇ eta 5.3 (Ore). Jestliˇze pro vˇsechny dvojice nesousedn´ıch uzl˚ u x, y grafu G plat´ı d(x)+ d(y) ≥ n, pak je graf G hamiltonovsk´ y.
Lemma 5.1 (Ore). Necht’ u, v jsou dva nesousedn´ı uzly grafu G takov´e, ˇze d(u)+d(v) ≥ n. Pak G je hamiltonovsk´ y, pr´avˇe kdyˇz graf G + {u, v} (vznikl´ y pˇrid´an´ım hrany {u, v} do G) je hamiltonovsk´ y.
....... ....... ....... ....... . ... ....... ....... ....... ....... ....... ....... .. ...... .. ..... ...... ..... ...... . ....... .... ..... ...... .. .... ...... . ....... ....... .... . .... ... ....... . ... . ... .. . . ....... . . . . . . . ....... .... . . . . . . ....... . . . . ...... ..... . . . . . ...... . ... ..... ...... . . .. . ............................................................................................................................................................................................................................................................................................................................................................................................................................................................................................
• • u = x1
•
•
•
•
•
• • • xi xi+1
•
•
•
• xn = v
......................................................................... ................................................................................................. ................ ............ .................... ............... ............ ............... ............. .......... ......... ............ . ......... . . . . . . . . . . . . . . . . . . . . . . . . . . . .......... .. ........ ....... ......... .......... ....... ......... ............. ......... ....... . . . . . . . . ......... ...... ..... . . . . . . . . . . . . ..... . . . . ....... ... ..... . . . . . . . . . . . . . . . ....................................................................................................................................................................................... . ......................................................................................................................................................................................................................................................
• • u = x1
•
•
•
•
•
• • • xi xi+1
4
•
•
•
• xn = v
Definice 5.1 (Bondy, Chv´ atal). Uz´avˇerem grafu G nazveme graf cl(G), kter´ y vznikne z grafu G postupn´ ym rekurentn´ım pˇrid´av´an´ım vˇsech hran {u, v}, splˇ nuj´ıc´ıch podm´ınku Oreho lemmatu.
Tvrzen´ı 5.2. Pro kaˇzd´ y graf G je jeho uz´avˇer cl(G) urˇcen jednoznaˇcnˇe.
Vˇ eta 5.4 (Bondy, Chv´ atal). Necht’ G je graf s alespoˇ n tˇremi uzly. Je-li cl(G) u ´pln´ y graf, potom je graf G hamiltonovsk´ y.
5
6. Nezávislost, dominance, klikovost a jádro grafu 6.1. Neorientované grafy
Definice 6.1. Množina A ⊂ U (G) se nazývá nezávislá množina grafu G, jestliže žádné dva uzly množiny A nejsou spojeny hranou.
Definice 6.2. Nezávislost grafu G (značíme α(G)) je největší počet prvků nezávislé množiny grafu G.
Definice 6.3. Množina B ⊂ U (G) se nazývá (uzlové) pokrytí grafu G, jestliže pro každou hranu {x, y} ∈ H(G) je x ∈ B nebo y ∈ B.
Definice 6.4. Pokrývací číslo grafu G (značíme β(G)) je počet prvků nejmenšího pokrytí grafu G.
Věta 6.1. Množina A ⊂ U (G) je nezávislá právě když B = U (G) \ A je pokrytí G.
Důsledek 6.1. Pro každý graf G platí α(G) + β(G) = |U (G)|.
1
Věta 6.2 (Chvátal, Erd˝ os).
Nechť G je k-souvislý graf (k ≥ 2)
s α(G) ≤ k. Pak je G hamiltonovský.
Věta 6.3 (Dirac).
Nechť G je k-souvislý graf (k ≥ 2). Pak pro každou
množinu M ⊂ U (G), |M | ≤ k, existuje v grafu G kružnice C taková, že M ⊂ U (C).
Definice 6.5. Podgraf K ⊂ G se nazývá klika grafu G, jestliže a) K je úplný podgraf b) jestliže K ⊂ K 0 ⊂ G a K 0 je úplný podgraf, pak K = K 0.
Definice 6.6. Klikovost grafu (značíme ω(G)) je největší počet uzlů kliky grafu G.
Definice 6.7. Nechť G je graf. Potom graf
U (G) ¯= U (G), \ H(G) G 2
se nazývá doplněk grafu G.
Věta 6.4. Nechť G je graf. Pak ¯ α(G) = ω(G).
2
Definice 6.8. Množina B ⊂ U (G) se nazývá dominantní množina grafu G, jestliže pro každý uzel x 6∈ B existuje uzel y ∈ B takový, že {x, y} ∈ H(G).
Definice 6.9. Počet prvků nejmenší dominantní množiny grafu G se nazývá číslo dominance grafu G a značí se γ(G).
Věta 6.5. Nechť A ⊂ U (G) je nezávislá množina grafu G. Pak A je maximální nezávislá množina právě když A je dominantní.
Věta 6.5. Každá maximální nezávislá množina je minimální dominantní množina grafu G.
Důsledek 6.2. Pro každý graf G platí γ(G) ≤ α(G).
Definice 6.10. Množina uzlů C ⊂ U (G), která je současně nezávislá i dominantní, se nazývá jádro grafu G.
Věta 6.7. Každý neorientovaný graf má jádro.
3
Poznámka. Úloha zjistit, zda v daném grafu existuje nezávislá množina předepsané velikosti, je NP-úplný problém.
Algoritmus (maximální nezávislá množina v grafu). 1. X := ∅, Y := U (G). 2. Dokud je Y 6= ∅, prováděj operaci (3): 3. Zvol x ∈ Y , polož X := X ∪ {x}, z Y vynech x a všechny uzly s ním sousední.
4
6.2. Jádro orientovaného grafu
~ orientovaný graf. Říkáme, že množina A ⊂ U (G) ~ Definice 6.11. Buď G je nezávislá, jestliže žádné dva její uzly nejsou spojeny hranou.
~ orientovaný graf, C ⊂ U (G). ~ Množina C se nazývá Definice 6.12. Buď G ~ jestliže jádro grafu G, (i) C je nezávislá množina, ~ \ C existuje y ∈ U (C) tak, že (x, y) ∈ H(G). ~ (ii) pro každý x ∈ U (G)
Věta 6.8. Každý acyklický graf má jádro.
Věta 6.9. Každý orientovaný graf bez cyklů liché délky má jádro.
5
7. Barevnost grafu
Definice 7.1. Graf G se naz´ yv´a k-obarviteln´ y, jestliˇze kaˇzd´emu jeho uzlu lze pˇriˇradit jednu z “barev” 1 . . . k tak, ˇze ˇz´adn´e dva sousedn´ı uzly nemaj´ı stejnou barvu.
Definice 7.2. Nejmenˇs´ı pˇrirozen´e ˇc´ıslo k, pro kter´e je graf G k-obarviteln´ y, se naz´ yv´a chromatick´e ˇc´ıslo (barevnost) grafu G a znaˇc´ı se χ(G).
Tvrzen´ı 7.1. Necht’ G obsahuje jako podgraf u ´pln´ y graf Kk . Pak χ(G) ≥ k.
Vˇ eta 7.1. Pro kaˇzd´ y graf G plat´ı χ(G) ≤ ∆(G) + 1, kde ∆(G) je maxim´aln´ı stupeˇ n grafu G.
1
Vˇ eta 7.2 (Brooks). Pro kaˇzd´ y graf G plat´ı χ(G) ≤ ∆(G) aˇz na tyto dvˇe v´ yjimky: I. G m´a komponentu K(∆(G)+1) , II. ∆(G) = 2 a G m´a za komponentu kruˇznici lich´e d´elky.
D˚ usledek 7.1. Je-li G souvisl´ y graf, kter´ y nen´ı u ´pln´ ym grafem ani kruˇznic´ı lich´e d´elky, pak χ(G) ≤ ∆(G).
Vˇ eta 7.3. Necht’ G je graf. Pak je χ(G) = 2 pr´avˇe kdyˇz H(G) ̸= ∅ a G neobsahuje kruˇznici lich´e d´elky.
´ Vˇ eta 7.4. Uloha: “urˇcete, zda je dan´ y graf G 3-obarviteln´ y” je NP-´ upln´a.
Vˇ eta 7.5. Pro graf G s chromatick´ ym ˇc´ıslem χ(G) a nez´avislost´ı α(G) plat´ı: 1. χ(G) α(G) ≥ |U (G)|, 2. χ(G) + α(G) ≤ |U (G)| + 1.
2
. ..
.
.. ..
.....
.. . . .
. ..
.
. .. . . . .. . .. . .. .. . ..
..
...
.. ...
.......
. ..
..
.. ...
...
....
. . . . . ..
..
..
...
....... . . .
..
.. ...
..
..
.. .. .. . . . . . . . . . . .. . . . . . .. . ... . . .. . .. . . . .. .. . . .. . . ... . . . .. . . . .. . . . . . . . .. . . . . .. . . . . . . .. . . . . . . . . . . . .. ........... .. . . . . . . . . .. ... . .. .. . .... . . .. . .. . .. . .. . . . .. .. . . . . . . . . . . .. .. . . .. . .. . . . . . . . . . . . .. . . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . .. . . . . . . . . . . . . .. .. . ... . .. . . . . . .. . . . . . . . . . .. . . . .. . . .. .. . . .. .. . . . . . . . .. . .. .. . .. . . . . . . . .. .. . . .. . .. . . . . . . .. . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . .. .. . .. .. . . . .. . .. .. . . .. . . . .. . . . . . . . . . .. . . .. . .. . .. ... . .. .. . . . .. . . . . .... . . . . . . . .. .. .. . ... . . . . . . . . . . . . . . . . .. . . . . . . . . . . .. . . . .. . . . . . . . . . . . . .. .. . . .. . . . . . . . . . .. . . . . . . . . . . . . .. . . . . .... .. .. . . .. ... . . . .. ... . .. .. .. .. .. . .. .. .. .. .. . ... .. . . . . . . . . . . . .. . .. .. .. .... .. .. .. . .... .. .. . .... ... . .. .. .. . . .. .. .. . . .. .. . .... . .. . . .. .. . . . .. .. .. . . . . .. . . . .. . . .. . .. ...... .. . ... .. . .. .. ... ... .. . ... .. . .. ........... .. . .... . . .. . . . .. . .. . . . . . . .. . . . . . . . .. .. . . . . . . .. . .. .. . . . . . . . . . .. . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . .. . ... . . . . . . . . .. . .. . . . . . . . . . . . . .... . .. . .. .. . . ... . . .. .. .. . .. . . .. . . .. .. . . . . .. . . . . . . ... .. . . . .. . . . . . . . . .. .. .. . .. . . .. .. .. .. . . . . . .. . .... .. .. ... . . . .. . . . . . . . . . . . . .. . . . ... .. . . . . . . . . .. .. . . ... .. . . ... . . . .. . . . . ... .. .. ... ..... . . . . . . ..
. . . ...
....
. . . . ... . .. .. . . . . . . . . . . . . . . .. . . . . . . .. .. . . . ..
..
. .. . . ..
. .. .. ... .. .. .. .
3
..................................................................... ............ ........... ......... ......... ........ ........ ........ .... . . . ....... .. . . ....... . ... ...... . . .. . .......... . ..... ... .... . . ... . . . ... .... ..... . . .. . . . . ... ..... ... ... ... ..... ... ... ... ..... ... .. .. ..... ... .. .. .. ..... . . . . ... ................................... ... . . . ... . ............ . . ... . . ... ....... . . . ............ .. . ... . . . . . ..... . . . . . . ... ............ ... . ... ..... . . . . . . . . . . . . ... . . . ... . ............ ..... . ... .. . ... ............ . . . . ..... ... . . . ............ ... . . ... . . . ..... . . . . ... . . . ............ ... ... . . ..... . . . . . . . . . . . . . . . . . . . . . . . . . ... . . . ... . . . . . . . ............ ..... ..... . ................. . . . . . . . . . . . . ... . . . . . ............ ... . . . . . . . . . . . ..... . . . . . . . ... . ...................................... ... . ...... . ..... . . . ... ..... ... . . ..... ........ . . . . . . ... . . ... . . ..... ..... . . ... ... . ... . . . . . ..... . ... . . ..... . ... . .... ... . ..... . . . . . . ... . . . ..... ... . . ..... . .... . . . . . . ... . ... . . . . ..... ..... . . . ... . ... . . . . . . ..... . . . . . ... ..... . ... . . .... . ..... . . . . . . . . . ... . ..... ... . ..... . . ... . . . . . . . ... . . . ... . . ..... ..... . . . .... . . ... . . . . ..... . . ... . . . ..... . ... . ..... ......... .. . . . . ... . . . .. ..... .. . ..... ...... . . . . ... . . . ................................................................................................................. . . ........ . . . . . . . . . . . . . . . . . . . . . . . . ... . ....... . . .......... .. . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . ... ...... . .......... . . . . . . . . . . . . . . . . . . . . . . . . ... . . . . . . . ....... . .... ... . .. .. . . . . ................................. . . . .... .... ... ... ... ... ... ........ ...... ... ... ... ...... ... ... ... .......... .. ...... .. ...... .. ..... ... ... ... .. ..... ...... .. . . . . . .. . . . . . . . . . . . ... ...... ... . ... ...... ... .... ... ... ...... ... ...... ... ...... ... ... ... ... ... ...... ... ...... .. ... ... ... ... ...... ... .. ...... . . . . . . . . .. . . . . . . . . . ...... ... . ...... ...... ... ... .... ... ... ... ...... ...... ... ... ... ... ... ... ...... ...... ... ... ... ... ...... ... ... ...... ... .. .. .......... .. . ... . ...... . . . . . .... ..... ....... .... ... ... .... .... ...... ..... ............. ... ...... ... ... ... ................ .............................. ..... .. ...... . . ................ ............... ..... ... ... ...... .... .... ................ ............... . . . . . . . . .. . . . . . . . . . . . . . . ............... ..... ...... .... ..... ............... ..... ... .. ........................ ... ... ............... .... ... ............................. ............... ... ............................................ ......................... .... ... ............................................ ............... .............................................
•
•
•
•
•
•
•
•
•
•
•
•
Vˇ eta 7.6 (Haken, Appel). Kaˇzd´ y rovinn´ y graf je 4-obarviteln´ y.
4
8. Modely v´ ypoˇ ctu
Definice algoritmu: • Turing˚ uv poˇc´ıtaˇc • rekurzivn´ı funkce • program v nˇekter´em programovac´ım jazyku • ...
Churchova teze“: kaˇzd´a u ´loha, algoritmizovateln´a podle nˇekter´e definice, je algorit” mizovateln´a i podle vˇsech ostatn´ıch definic.
5
8.1 Poˇ c´ıtaˇ c s libovoln´ ym pˇ r´ıstupem
vstupn´ı jednotka
...................... ... ... ... ... ... ... ... ... ... ... ... ... ...................
vstupn´ı p´ aska .. ... .. ... ..
.. ... .. ... ..
pole .. ......... ......... ... .... .. ... ... ... ... ... ... .
.. ... .. ... ..
.. ... .. ... ..
.. ... .. ... ..
.. ... .. ... ..
.. ... .. ... ..
.. ... .. ... ..
.. ... .. ... ..
.. ... .. ... ..
...
vstupn´ı hlava
Programov´ a jednotka 0
Program
1
Aritmetick´ a y Programov´
...............................................................................
registr
...............................................................................
2
jednotka
3 4
............................................................................... ..................................................... ...............................................................................
v´ ystupn´ı jednotka
...................... ... ... ... ... ... ... ... ... ... ... ... ... ...................
... ... .. ...
... ... .. ...
... ... ... ... ... ... ... ... ... ... ... ... ... ... . ......... ......... ...
5
pracovn´ı registr
......................................................................................................................
indexov´ y registr
......................................................................................................................
pamˇet’ov´ a buˇ nka
......................................................................................................................
pamˇet’ov´ a buˇ nka ...
...................................................................................................................... ...................................................................................................................... ......................................................................................................................
...............................................................................
......................................................................................................................
.. .
.. .
v´ ystupn´ı hlava
pole
... ... .. ...
... ... .. ...
... ... .. ...
... ... .. ...
... ... .. ...
... ... .. ...
... ... .. ...
... ... .. ...
...
v´ ystupn´ı p´ aska
V pol´ıch vstupn´ı i v´ ystupn´ı p´asky jsou cel´a ˇc´ısla libovolnˇe velk´a. Pamˇet’ov´ ych bunˇek je neomezen´ y poˇcet a lze do nich vkl´adat neomezenˇe velk´a ˇc´ısla. ˇc´ısla pˇred registry a pamˇet’ov´ ymi buˇ nkami ud´avaj´ı adresu.
6
Konfigurace poˇc´ıtaˇce: pˇriˇrazen´ı, kter´e kaˇzd´emu – poli vstupn´ı p´asky – poli v´ ystupn´ı p´asky – pamˇet’ov´e buˇ nce – programov´emu registru pˇriˇrazuje cel´e ˇc´ıslo (= popis okamˇzit´eho stavu poˇc´ıtaˇce).
Poˇc´ ateˇcn´ı konfigurace: existuje n takov´e, ˇze – pole vstupn´ı p´asky s adresami n, n + 1, . . . – vˇsechna pole v´ ystupn´ı p´asky – vˇsechny pamˇet’ov´e buˇ nky obsahuj´ı nuly a programov´ y registr m´a hodnotu 1 (tj. na pol´ıch vstupn´ı p´asky s adresami 0, . . . , n − 1 jsou vstupn´ı data.)
V´ypoˇcet poˇc´ıtaˇce: posloupnost konfigurac´ı C0 , C1 , . . . takov´a, ˇze C0 je poˇc´ateˇcn´ı konfigurace, a krok je d´an nˇekter´ ym z pˇr´ıkaz˚ u (viz d´ale).
Program poˇc´ıtaˇce: koneˇcn´a posloupnost p1 , . . . , pn pˇr´ıkaz˚ u.
7
Pˇ r´ıkazy Pˇ resuny v pamˇ eti LOAD operand
do pracovn´ıho registru uloˇz´ı hodnotu operandu
STORE operand
(ostatn´ı nezmˇenˇeno) do pamˇet’. buˇ nky s adresou rovnou adrese operandu uloˇz´ı obsah prac. registru
Aritmetick´ e pˇ r´ıkazy ADD operand
k obsahu prac. registru se pˇriˇcte hodnota operandu
SUBTRACT operand od obsahu prac. registru se odeˇcte hodnota operandu MULTIPLY operand
obsah prac. registru se n´asob´ı hodnotou operandu
DIVIDE operand
obsah prac. registru se dˇel´ı hodnotou operandu
Vstupy, v´ ystupy READ
do prac. registru d´a obsah aktu´aln´ıho pole vstupn´ı p´asky a posune hlavu o 1 vpravo
WRITE
obsah prac. registru uloˇz´ı do aktu´aln´ıho pole v´ ystupn´ı p´asky a posune hlavu o 1 vpravo
Skoky JUMP n´avˇeˇst´ı
uloˇz´ı n´avˇeˇst´ı do programov´eho registru
JZERO n´avˇeˇst´ı
provede pˇr´ıkaz JUMP, pokud je obsah pracovn´ıho registru roven nule
JGE n´avˇeˇst´ı
provede pˇr´ıkaz JUMP, pokud obsah prac. registru je ≥ 0
N´avˇeˇst´ım rozum´ıme ˇc´ıslo instrukce ˇci pˇr´ıkazu programu, tj. pˇrirozen´e ˇc´ıslo.
8
Zastaven´ı STOP ukonˇc´ı v´ ypoˇcet ACCEPT ukonˇc´ı v´ ypoˇcet, u rozhodovac´ıch u ´loh m´a pravdivostn´ı hodnotu 1 REJECT
tot´eˇz jako ACCEPT, ale d´av´a hodnotu 0
Zp˚ usoby zad´ an´ı operandu: j (j je pˇrirozen´e ˇc´ıslo nebo nula) - adresa operandu je j, hodnota operandu je obsah buˇ nky s adresou j. ∗j (j je cel´e ˇc´ıslo) - adresa operandu je i + j, kde i je obsah indexov´eho registru, hodnota je obsah buˇ nky s adresou i + j. = j (j je cel´e ˇc´ıslo) - hodnota je j, adresa nen´ı definov´ana. Adresovac´ı chyba: nastane, kdyˇz se u operandu ∗j objev´ı okamˇzit´a hodnota i + j z´aporn´a. V´ ypoˇcet se v takov´emto pˇr´ıpadˇe zastav´ı.
9
ˇ 8.2 Casov´ a a pamˇ et’ov´ a n´ aroˇ cnost v´ ypoˇ ctu
Definice 8.1. ˇrekneme, ˇze v´ ypoˇcet poˇc´ıtaˇce trval dobu t, jestliˇze – v t-t´em kroku doˇslo k: – proveden´ı pˇr´ıkazu zastaven´ı, nebo – adresovac´ı chybˇe, nebo – dˇelen´ı nulou, – v kroc´ıch 0, 1, . . . , t − 1 ˇz´adn´ y z uveden´ ych pˇr´ıpad˚ u nenastal. ˇrekneme, ˇze v´ ypoˇcet poˇc´ıtaˇce pracoval s pamˇet´ı velikosti m, jestliˇze – nebyl proveden pˇr´ıkaz s adresou > m, – byl proveden pˇr´ıkaz s adresou = m.
Omezen´ı 1. Necht’ p je pevnˇe dan´ y polynom. Pˇripouˇst´ıme jen v´ ypoˇcty, pro nˇeˇz v ˇz´adn´e buˇ nce pamˇeti nen´ı ˇc´ıslo v absolutn´ı hodnotˇe vˇetˇs´ı neˇz p(max{n, |c1 |, |c2 |, . . . , |cn |}), kde c1 , . . . , cn jsou vstupn´ı data.
Vˇ eta 8.1. Necht’ f je funkce a M poˇc´ıtaˇc, kter´ y kaˇzdou vstupn´ı posloupnost d´elky n (
zpracuje v ˇcase f (n). Pak existuje poˇc´ıtaˇc M ′ , kter´ y zpracuje t´ yˇz vstup v ˇcase O (f (n))2
)
a v pamˇeti O(f (n)) a d´a t´ yˇz v´ ystup.
D˚ usledek 8.1. Jestliˇze existuje poˇc´ıtaˇc, kter´ y kaˇzdou vstupn´ı posloupnost d´elky n zpracuje v polynomi´aln´ım ˇcase, pak existuje poˇc´ıtaˇc, kter´ y kaˇzdou vstupn´ı posloupnost zpracuje v polynomi´aln´ım ˇcase i pamˇeti.
10
8.3 Probl´ emy (jazyky) tˇ r´ıdy P
Definice 8.2. Vstupn´ımi daty nebo slovem nazveme koneˇcnou posloupnost nul a jedniˇcek. D´elkou slova rozum´ıme poˇcet ˇclen˚ u posloupnosti vstupn´ıch dat. Jazykem nazveme koneˇcnou (nebo i nekoneˇcnou) mnoˇzinu slov.
Definice 8.3. Pˇrij´ımac´ı poˇc´ıtaˇc je poˇc´ıtaˇc, kter´ y m´a n´asleduj´ıc´ı dvˇe vlastnosti: (i) jeho program neobsahuje pˇr´ıkazy WRITE ani STOP, (ii) pro kaˇzd´e slovo w se v´ ypoˇcet zastav´ı po koneˇcn´em poˇctu krok˚ u proveden´ım pˇr´ıkaz˚ u ACCEPT nebo REJECT (aniˇz by doˇslo k adresovac´ı chybˇe nebo dˇelen´ı nulou). ˇrekneme, ˇze pˇrij´ımac´ı poˇc´ıtaˇc pˇrij´ım´a slovo w, pokud se v´ ypoˇcet zastav´ı pˇr´ıkazem ACCEPT , a odm´ıt´a slovo q, pokud v´ ypoˇcet skonˇc´ı pˇr´ıkazem REJECT. Mnoˇzina pˇrij´ıman´ ych slov se naz´ yv´a jazyk pˇrij´ıman´ y poˇc´ıtaˇcem.
ˇ Definice 8.4. Necht’ J je jazyk a f : N → N. Casov´ a (pamˇet’ov´a) sloˇzitost jazyka J je nejv´ yˇse f , jestliˇze existuje pˇrij´ımac´ı poˇc´ıtaˇc M , kter´ y pˇrij´ım´a J a kaˇzd´e slovo jazyka J d´elky n zpracuje v ˇcase (pamˇeti) f (n).
Definice 8.5. Tˇr´ıda P je tˇr´ıda vˇsech jazyk˚ u J, pro nˇeˇz existuje polynom p takov´ y, ˇze ˇcasov´a sloˇzitost jazyka J je nejv´ yˇse p.
11
9. Teorie NP-úplnosti
9.1 Logické formule
Logická (booleovská) proměnná je proměnná, která nabývá hodnot 0 (false) a 1 (true).
Logická formule: (i) konstanty 0 a 1 a každá logická proměnná jsou logickými formulemi, (ii) jsou-li f , g logické formule, pak je logická formule i výraz f¯, f ∧ g, f ∨ g, f ⇒ g, f ⇔ g, f ⊕ g. f¯
negace
f¯ = 1 právě když f = 0
f ∧g
konjunkce
f ∧ g = 1 právě když f = 1 a současně g = 1
f ∨g
disjunkce
f ⇒ g implikace
f ∨ g = 1 právě když alespoň jeden z f , g je roven 1 f ⇒ g = 1 právě když f¯ = 1 nebo g = 1
f ⇔ g ekvivalence
f ⇔ g = 1 právě když f = g
f ⊕g
vylučovací nebo f ⊕ g = 1 právě když právě jeden z f , g je roven 1
Definice 9.1. Má-li formule pro dané hodnoty proměnných hodnotu 1, říkáme, že je splněna. Formule, která je splněna pro všechny hodnoty proměnných, se nazývá tautologie. Řekneme, že formule f proměnných x1, x2, . . . , xn je splnitelná, jestliže existují hodnoty x1, x2, . . . , xn, pro které je f splněna.
1
Definice 9.2. Proměnné a jejich negace se nazývají literály. Literály a disjunkce dvou či více literálů se nazývají (disjunktivní) klauzule. Je-li formule disjunktivní klauzulí nebo konjunkcí dvou či více disjunktivních klauzulí, říkáme, že formule je v konjunktivní normální formě (tvaru). Je-li formule v konjunktivní normální formě a každá klauzule obsahuje literály všech proměnných, říkáme, že formule je v úplné konjunktivní normální formě (tvaru).
Definice 9.3. Literály a konjunkce dvou či více literálů se nazývají (konjunktivní) klauzule. Je-li formule konjunktivní klauzulí nebo disjunkcí dvou či více konjunktivních klauzulí, říkáme, že formule je v disjunktivním normálním tvaru (formě).
Věta 9.1. Každou nekonstantní logickou formuli lze vyjádřit v ÚDNF i ÚKNF.
9.2 Problém splnitelnosti logických formulí – SAT SAT Vstup: logická formule f (x1, x2, . . . , xn) v proměnných x1, x2, . . . , xn v KNF (tj. f = c1 ∧ c2 ∧ . . . ∧ cm, kde ci jsou klauzule proměnných x1, x2, . . . , xn). Úkol: zjistit, zda je formule f splnitelná.
2
9.3 Problém k-SAT a polynomialita problému 2-SAT
k-SAT Vstup: logická formule tvaru f (x1, x2, . . . , xn) =
m k ^ _
i=1 j=1
, aij
kde každé aij je rovno x` nebo x¯` pro vhodné ` = 1, . . . , n (tj. f je formule v KNF, která má m klauzulí délky k). Úkol: zjistit, zda je formule f splnitelná.
2-SAT Vstup: logická formule f (x1, . . . , xn) = (a1 ∨ b1) ∧ (a2 ∨ b2) ∧ . . . , ∧(am ∨ bm), kde každé ai, bi(i = 1, . . . m) je rovno x` nebo x¯` pro vhodné ` = 1, . . . , n (tj. f je formule v KNF s klauzulemi délky 2). Úkol: zjistit, zda je formule f splnitelná.
Věta 9.2.
2-SAT ∈ P.
f (x1, . . . , xn) = C1 ∧ C2 ∧, . . . , ∧ Cm je formule v proměnných x1, . . . , xn s klauzulemi o 2 literálech. ~ f následující konstrukcí: Sestrojíme orientovaný graf G ~ f ) = {x1, . . . , xn, x¯1, . . . , x¯n}, U (G ~ f obě hrany (¯a, b) a (¯b, a). pro každou klauzuli Ci = (a ∨ b) budou v G
3
~ f orientovaný sled z a do b, pak v G ~ f existuje Lemma 9.1. Existuje-li v G i orientovaný sled z ¯b do a¯. Splňující přiřazení: každý vektor t ∈ {0, 1}n, pro který f (t) = 1 (tj. takové přiřazení hodnot 0, 1 proměnným x1, . . . , xn, že pro tyto hodnoty je formule f splněna). Je-li a literál a t ∈ {0, 1}n vektor hodnot proměnných x1, . . . , xn, pak a(t) značí hodnotu literálu a po dosazení vektoru t. ~ f cesta z a do b, pak pro každé splňující Lemma 9.2. Existuje-li v G přiřazení t je a(t) = 1 ⇒ b(t) = 1. Lemma 9.3. Je-li t splňující přiřazení, pak pro každou kvazikomponentu ~ i grafu G ~ f a pro každé uzly a, b ∈ U (G ~ i) je a(t) = b(t) (a tedy také G a¯(t) = ¯b(t)). Lemma 9.4. Formule f je splnitelná právě když žádná kvazikomponenta ~ f neobsahuje současně některou proměnnou i její negaci. grafu G ~ 1, . . . , G ~ s – kvazikomponenty G ~ f v acyklickém očíslování G ~ 1 je vstupní, G ~ s je výstupní a hrany z Gi do Gj existují pouze pro i < j) (tj. G Konstrukce přiřazení t Postupujeme pro j = s, s − 1, . . . , 1, ~j , ∀ proměnnou xi určíme největší index j0 takový, že xi nebo x¯i je v G 0 položíme ~ j ), xi = 1, jestliže xi ∈ U (G 0 ~ j ). xi = 0, jestliže x¯i ∈ U (G 0
4
9.4 Problém existence nezávislé množiny uzlů dané velikosti - IND
IND Vstup: neorientovaný graf G na n uzlech a přirozené číslo k ≤ n. Úkol: zjistit, zda v grafu G existuje nezávislá množina uzlů velikosti alespoň k.
Příklad. Je dán graf G s uzly x1, x2, . . . , xn a číslo k. Sestrojíme formuli f (u1, u2, . . . , un) takovou, že f je splněna právě když množina N = {xi ∈ U (G)|ui = TRUE} je nezávislá množina o alespoň k prvcích.
Našli jsme polynomiální redukci IND na SAT.
Důsledek 9.1. Úloha SAT je alespoň tak těžká jako úloha IND.
Důsledek 9.2. Kdybychom měli polynomiální algoritmus na SAT, bylo by možné vytvořit polynomiální algoritmus i na IND.
5
Příklad. Naopak: je dána logická formule v KNF tvaru f (u1, u2, . . . , un) =
m ^
m _i
i=1 j=1
, aij
kde každé aij je tvaru uk nebo u¯k pro vhodné k. Sestrojíme graf G takový, že v G existuje nezávislá množina velikosti m právě když f je splnitelná.
Konstrukce grafu G: U (G) = {xij | i = 1, . . . , m ; j = 1, . . . , mi}, H(G) = {{xij , xpq }| i = p a j 6= q}∪{{xij , xpq }| i 6= p, j = q a aij = a¯pq }. Našli jsme polynomiální redukci SAT na IND.
Důsledek 9.3. Úloha IND je alespoň tak těžká jako úloha SAT.
Důsledek 9.4. Kdybychom měli polynomiální algoritmus na IND, bylo by možné vytvořit polynomiální algoritmus i na SAT.
Důsledek 9.5.
SAT ∈ P
právě když
6
IND ∈ P .
9.5 Třída NP
Definice 9.4. Nedeterministický algoritmus se v některých krocích může libovolně rozhodnout pro některé z několika možných různých pokračování.
Příklad. Uvažujme problém IND a následující algoritmus. Vstup: graf G s uzly u1, . . . , un. 1) X := 0
(inicializace)
2) pro i = 1, 2, . . . , n proveď: a) buďto X := X ∪ {ui}, b) nebo X := X (nedeterministický krok) 3) Jestliže {ui, uj } ∈ H(G) pro některé ui, uj ∈ X, pak REJECT (test nezávislosti) 4) Je-li |X| ≥ k pak ACCEPT, jinak REJECT
(test |X| ≥ k)
Vlastnosti: • v důsledku nedeterminističnosti 2. kroku je 2n možných různých výpočtů, • v G existuje nezávislá množina o alespoň k uzlech právě když existuje výpočet, končící ACCEPT.
1
Definice 9.5. Nedeterministický přijímací počítač má (navíc oproti dříve definovanému přijímacímu počítači) příkaz CHOOSE L1, L2, kde L1, L2 jsou návěští.
Definice 9.6. Řekneme, že slovo w je přijímáno nedeterministickým přijímacím počítačem M , jestliže existuje přípustný výpočet počítače M s počáteční konfigurací danou slovem w a končící ACCEPT. V opačném případě řekneme, že nedeterministický přijímací počítač odmítá slovo w. Řekneme, že M přijímá jazyk J, jestliže pro každé slovo w je w ∈ J ⇔ M přijímá w.
Definice 9.7. Řekneme, že nedeterministický přijímací počítač M zpracuje slovo w v čase nejvýše t, jestliže: - buďto M přijímá w, a existuje přípustný výpočet určený slovem w a končící ACCEPT po nejvýše t krocích, - nebo M odmítá w a každý přípustný výpočet končí po nejvýše t krocích.
Definice 9.8. Řekneme, že nedeterministický přijímací počítač M pracuje v polynomiálně omezeném čase, jestliže existuje polynom p takový, že libovolné slovo délky n zpracuje v čase nejvýše p(n).
2
Definice 9.9. Třída NP je třída všech jazyků J takových, že existuje nedeterministický přijímací počítač, který pracuje v polynomiálně omezeném čase a přijímá jazyk J.
Věta 9.3.
P ⊂ NP .
(i) Je J ∈ P? (ii) Je alespoň J ∈ NP? (iii) Hledáme přesné řešení postupy typu „hrubá sílaÿ. (iv) Použijeme heuristiku a spokojíme se s přibližným řešením.
Algoritmus
Deterministický Polynomiální
Přijímá J
(i) Dokazuje J ∈ P
ANO
ANO
ANO
(ii) Dokazuje J ∈ NP
NE
ANO
ANO
(iii) „Hrubá sílaÿ
ANO
NE
ANO
(iv) Heuristika
ANO
ANO
NE
3
Polynomiální redukce a NP-úplné problémy
Definice 9.10. Překládací počítač je počítač M s libovolným přístupem takový, že pro každý jeho výpočet (daný libovolnou počáteční konfigurací) platí: - každé provedení WRITE zapíše na vstupní pásku číslo 0 nebo 1, - po konečném počtu kroků se výpočet zastaví provedením STOP. Posloupnost nul a jedniček, zapsanou na výstupní pásce při výpočtu určeném slovem w, označíme M (w).
Definice 9.11. Řekneme, že jazyk J1 je redukovatelný na jazyk J2 (značíme J1 / J2), jestliže existuje deterministický překládací počítač M pracující v polynomiálně omezeném čase takový, že pro každé slovo w je w ∈ J1 ⇔ M (w) ∈ J2.
Věta 9.4. 1) J1 / J2, J2 / J3 ⇒ J1 / J3
(tranzitivita)
2) J1 / J2, J2 ∈ N P ⇒ J1 ∈ N P 3) J1 / J2, J2 ∈ P ⇒ J1 ∈ P
J1 / J2 znamená, že J2 je alespoň tak těžký jako J1.
4
Definice 9.12. Jazyk J se nazývá NP-úplný, jestliže platí 1) J ∈ N P 2) pro každý J 0 ∈ N P je J 0 / J. Třídu NP-úplných jazyků označíme NPC („NP-completeÿ).
Věta 9.5. Platí: buď P = N P , nebo P ∩ N P C = ∅.
Jazyk J se nazývá NP-těžký, jestliže pro každý J 0 ∈ N P platí J 0 / J.
5
NP-úplnost problému SAT – Cookova věta
Věta 9.6. (Cook)
SAT ∈ NPC.
1. SAT ∈ NP. 2. Pro každý J ∈ NP je J/ SAT. Nechť - J ∈ NP, - M je nedeterministický přijímací počítač, přijímající J v čase omezeném polynomem p. Úkol: pro každé slovo w ∈ J nalézt formuli fw v KNF tak, že fw je splnitelná, právě když M přijímá w. Označíme: n - délka slova w, m = p(n), q - počet příkazů programu počítače M . To znamená, že - pouze prvních n polí vstupní pásky obsahuje čísla 6= 0, - pouze prvních m paměťových buněk obsahje číslo 6= 0, - v žádné paměťové buňce není číslo větší než m, - počet kroků počítače je nejvýše m.
6
K popisu všech konfigurací stačí znát hodnoty logických proměnných: ai, i = 1, . . . , n : ai = 1 ⇔ v i-tém poli vstupní pásky je číslo 1 bit, i = 1, . . . , n, t = 0 . . . , m: bit = 1 ⇔ po t-tém kroku je vstupní hlava na i-tém poli pásky cijt, i = 0 . . . m, j = 0, ±1, . . . , ±m, t = 0, . . . m : cijt = 1 ⇔ v t-té konfiguraci je v i-té paměťové buňce číslo j djt, j = 1, . . . , q, t = 0, . . . , m : djt = 1 ⇔ v t-té konfiguraci je v programovém registru číslo j
7
Mají-li proměnné popisovat kroky počítače M , který v m krocích přijme slovo w, musí splňovat následující podmínky: 1) hodnoty ai se shodují s 0 a 1 ve slově w, 2) hlava nemůže být současně na dvou místech: pro každé t existuje nejvýše jedno i tak, že bit = 1, 3) v každé paměťové buňce je právě jedno číslo: pro každé i, t existuje právě jedno j tak, že cijt = 1, 4) totéž pro programový registr: pro každé t existuje právě jedno j tak, že djt = 1, 5) jestliže djm = 1, pak j je návěští některého příkazu ACCEPT, 6) vztah hodnot proměnných mezi t − 1 a t musí odpovídat prováděnému příkazu počítače.
Položíme fw = fw1 ∧ fw2 ∧ fw3 ∧ fw4 ∧ fw5 ∧ fw6, kde fwi je formule daná podmínkou i, i = 1, . . . , 6.
8
9.8 Některé další NP-úplné problémy
Problém 3-splnitelnosti logických formulí – 3-SAT. 3-SAT Vstup: logická formule f (x1, . . . , xn) = (a1 ∨ b1 ∨ c1) ∧ (a2 ∨ b2 ∨ c2) ∧ . . . , ∧(ak ∨ bk ∨ ck ), kde každé ai, bi, ci (i = 1, . . . k) je rovno x` nebo x¯` pro vhodné ` = 1, . . . , n (tj. f je formule v KNF s klauzulemi délky 3). Úkol: zjistit, zda je formule f splnitelná.
Věta 9.7.
3-SAT ∈ NPC.
1
Nezávislá množina – IND IND Vstup: neorientovaný graf G na n uzlech a přirozené číslo k ≤ n. Úkol: zjistit, zda v grafu G existuje nezávislá množina uzlů velikosti alespoň k. Věta 9.8.
IND ∈ NPC.
IND= Vstup: neorientovaný graf G na n uzlech a přirozené číslo k ≤ n. Úkol: zjistit, zda v grafu G existuje nezávislá množina uzlů velikosti k.
INDk Vstup: neorientovaný graf G na n uzlech. Úkol: zjistit, zda v grafu G existuje nezávislá množina uzlů velikosti k.
Tvrzení 9.1.
IND= ∈ NPC.
Tvrzení 9.2.
INDk ∈ P.
2
Uzlové pokrytí – COV COV Vstup: neorientovaný graf G na n uzlech a přirozené číslo k ≤ n. Úkol: zjistit, zda v grafu G existuje pokrytí velikosti nejvýše k. Věta 9.9.
COV ∈ NPC.
Existence kliky předepsané velikosti – CLIQUE CLIQUE Vstup: neorientovaný graf G na n uzlech a přirozené číslo k ≤ n. Úkol: zjistit, zda v grafu G existuje klika velikosti alespoň k. Věta 9.10.
CLIQUE ∈ NPC.
3
3-obarvitelnost grafu – 3-COL k-COL Vstup: neorientovaný graf G na n uzlech a přirozené číslo k ≤ n. Úkol: zjistit, zda je graf G k-obarvitelný. Věta 9.11.
3-COL ∈ NPC.
Graf G sestrojíme touto konstrukcí: - pro každou proměnnou xi sestrojíme dvojici uzlů xi, x¯i a spojíme ji hranou, - přidáme tři uzly u, v, w tvořící trojúhelník, - uzel w spojíme se všemi uzly xi, x¯i, - pro každou klauzuli formule f vytvoříme jednu kopii grafu G2, přičemž - uzly a, b, c budou totožné s uzly literálů této klauzule, - uzel d bude sousední s uzlem u.
4
