Kombinatorika a grafy I

Kombinatorika a grafy I

Martin Balko

7. pˇredn´ aˇska

16. listopadu 2021

Aplikace tok˚ u v s´ıt´ıch

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf :E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf :E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacityhran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z s

v1 v2

v3 v4

12 9 16

13

14

20

4 7 π

10

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacity hran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

12 9 /16

/13

/14

/20

4 /7 /π

10

/12 11

11

/4 z

v1

v4

v3

7

19

12

/20 1

w(f) = 23

s v2

Pˇripomenut´ı z minula I

• S´ıt’ je ˇctveˇrice (G,z,s,c), kde G = (V,E) je orientovan´y graf, z ∈V je zdroj, s ∈V je stok a c: E →R⁺0 jsou kapacity hran.

• Tokje zobrazen´ıf : E →R⁺0 splˇnuj´ıc´ı 0≤f(e)≤c(e) pro kaˇzd´ee ∈E a P

v:(u,v)∈Ef(u,v) = P

v:(v,u)∈Ef(v,u) pro kaˇzd´eu ∈V \ {z,s}.

• Velikost tokuf je w(f)=P

v:(z,v)∈Ef(z,v)−P

v:(v,z)∈Ef(v,z).

• Rezˇ R je podmnoˇzinaE zasahuj´ıc´ı do kaˇzd´e orientovan´e cesty zez dos.

• Kapacita ˇrezuR je c(R)=P

e∈Rc(e).

z v1

v3

12 9 16

13

14

20

4 7 π

10

s v2

v4

c(R) = 23

Pˇripomenut´ı z minula II

Vˇeta 6.2 (Hlavn´ı vˇeta o toc´ıch)

V kaˇzd´e s´ıti existuje maxim´aln´ı tok a jeho velikost se rovn´a kapacitˇe minim´aln´ıho ˇrezu.

• M´ame Ford˚uv–Fulkerson˚uv algoritmus na nalezen´ı maxim´aln´ıho toku:

◦ Zaˇcni s nulov´ym tokem a dokud existuje cesta P ze z do s, kde

εP = min

e∈E(P)

(c(e)−f(e) e je dopˇredn´a hrana v P, f(e) e je zpˇetn´a hrana vP

je kladn´e, tak zvyˇs tok o ε_P po dopˇredn´ych hran´ach zP a sniˇz jej oε_P po zpˇetn´ych hran´ach z P.

◦ Pot´e vrat’ aktu´aln´ı tok (ten uˇz bude m´ıt maxim´aln´ı velikost).

Vˇeta 6.6 (Vˇeta o celoˇc´ıselnosti)

V kaˇzd´e s´ıti s celoˇc´ıseln´ymi kapacitami Ford˚uv–Fulkerson˚uv algoritmus najde po koneˇcnˇe mnoha kroc´ıch tok maxim´aln´ı velikosti a ta je celoˇc´ıseln´a.

Pˇripomenut´ı z minula II

Vˇeta 6.2 (Hlavn´ı vˇeta o toc´ıch)

V kaˇzd´e s´ıti existuje maxim´aln´ı tok a jeho velikost se rovn´a kapacitˇe minim´aln´ıho ˇrezu.

• M´ame Ford˚uv–Fulkerson˚uv algoritmus na nalezen´ı maxim´aln´ıho toku:

◦ Zaˇcni s nulov´ym tokem a dokud existuje cesta P ze z do s, kde

εP = min

e∈E(P)

(c(e)−f(e) e je dopˇredn´a hrana v P, f(e) e je zpˇetn´a hrana vP

je kladn´e, tak zvyˇs tok o ε_P po dopˇredn´ych hran´ach zP a sniˇz jej oε_P po zpˇetn´ych hran´ach z P.

◦ Pot´e vrat’ aktu´aln´ı tok (ten uˇz bude m´ıt maxim´aln´ı velikost).

Vˇeta 6.6 (Vˇeta o celoˇc´ıselnosti)

V kaˇzd´e s´ıti s celoˇc´ıseln´ymi kapacitami Ford˚uv–Fulkerson˚uv algoritmus najde po koneˇcnˇe mnoha kroc´ıch tok maxim´aln´ı velikosti a ta je celoˇc´ıseln´a.

Pˇripomenut´ı z minula II

Vˇeta 6.2 (Hlavn´ı vˇeta o toc´ıch)

V kaˇzd´e s´ıti existuje maxim´aln´ı tok a jeho velikost se rovn´a kapacitˇe minim´aln´ıho ˇrezu.

• M´ame Ford˚uv–Fulkerson˚uv algoritmus na nalezen´ı maxim´aln´ıho toku:

◦ Zaˇcni s nulov´ym tokem a dokud existuje cesta P ze z do s, kde

εP = min

e∈E(P)

(c(e)−f(e) e je dopˇredn´a hrana v P, f(e) e je zpˇetn´a hrana vP

je kladn´e, tak zvyˇs tok o ε_P po dopˇredn´ych hran´ach zP a sniˇz jej oε_P po zpˇetn´ych hran´ach z P.

◦ Pot´e vrat’ aktu´aln´ı tok (ten uˇz bude m´ıt maxim´aln´ı velikost).

Vˇeta 6.6 (Vˇeta o celoˇc´ıselnosti)

V kaˇzd´e s´ıti s celoˇc´ıseln´ymi kapacitami Ford˚uv–Fulkerson˚uv algoritmus najde po koneˇcnˇe mnoha kroc´ıch tok maxim´aln´ı velikosti a ta je celoˇc´ıseln´a.

Pˇripomenut´ı z minula II

Vˇeta 6.2 (Hlavn´ı vˇeta o toc´ıch)

V kaˇzd´e s´ıti existuje maxim´aln´ı tok a jeho velikost se rovn´a kapacitˇe minim´aln´ıho ˇrezu.

• M´ame Ford˚uv–Fulkerson˚uv algoritmus na nalezen´ı maxim´aln´ıho toku:

◦ Zaˇcni s nulov´ym tokem a dokud existuje cesta P ze z do s, kde

ε_P = min

e∈E(P)

(c(e)−f(e) e je dopˇredn´a hrana v P, f(e) e je zpˇetn´a hrana v P

je kladn´e, tak zvyˇs tok o ε_P po dopˇredn´ych hran´ach zP a sniˇz jej oε_P po zpˇetn´ych hran´ach z P.

◦ Pot´e vrat’ aktu´aln´ı tok (ten uˇz bude m´ıt maxim´aln´ı velikost).

Vˇeta 6.6 (Vˇeta o celoˇc´ıselnosti)

V kaˇzd´e s´ıti s celoˇc´ıseln´ymi kapacitami Ford˚uv–Fulkerson˚uv algoritmus najde po koneˇcnˇe mnoha kroc´ıch tok maxim´aln´ı velikosti a ta je celoˇc´ıseln´a.

Pˇripomenut´ı z minula II

Vˇeta 6.2 (Hlavn´ı vˇeta o toc´ıch)

V kaˇzd´e s´ıti existuje maxim´aln´ı tok a jeho velikost se rovn´a kapacitˇe minim´aln´ıho ˇrezu.

• M´ame Ford˚uv–Fulkerson˚uv algoritmus na nalezen´ı maxim´aln´ıho toku:

◦ Zaˇcni s nulov´ym tokem a dokud existuje cesta P ze z do s, kde

ε_P = min

e∈E(P)

(c(e)−f(e) e je dopˇredn´a hrana v P, f(e) e je zpˇetn´a hrana v P

je kladn´e, tak zvyˇs tok o ε_P po dopˇredn´ych hran´ach zP a sniˇz jej oε_P po zpˇetn´ych hran´ach z P.

◦ Pot´e vrat’ aktu´aln´ı tok (ten uˇz bude m´ıt maxim´aln´ı velikost).

Vˇeta 6.6 (Vˇeta o celoˇc´ıselnosti)

V kaˇzd´e s´ıti s celoˇc´ıseln´ymi kapacitami Ford˚uv–Fulkerson˚uv algoritmus najde po koneˇcnˇe mnoha kroc´ıch tok maxim´aln´ı velikosti a ta je celoˇc´ıseln´a.

K˝ onigova–Egerv´ aryho vˇeta

K˝ onigova–Egerv´ aryho vˇeta

Vˇeta 7.1 (K˝onigova–Egerv´aryho vˇeta, 1931)

V kaˇzd´em bipartitn´ım grafu je velikost minim´aln´ıho vrcholov´eho pokryt´ı rovna velikosti maxim´aln´ıho p´arov´an´ı.

Obr´azek: D´enes K˝onig(1884–1944) aJen˝o Egerv´ary (1891–1958).

Zdroj: http://en.wikipedia.org

K˝ onigova–Egerv´ aryho vˇeta

Vˇeta 7.1 (K˝onigova–Egerv´aryho vˇeta, 1931)

V kaˇzd´em bipartitn´ım grafu je velikost minim´aln´ıho vrcholov´eho pokryt´ı rovna velikosti maxim´aln´ıho p´arov´an´ı.

Obr´azek: D´enes K˝onig (1884–1944) aJen˝o Egerv´ary (1891–1958).

Zdroj: http://en.wikipedia.org

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

G

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

G

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

1 1

M = 9 G

z s

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

1 1

M = 9 G

z s

f 1/

1/

1/

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

G

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

1 1

M = 9 G

z s

f 1/

1/

1/

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

G

z s

R

1 1

M = 9

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

G

z s

R

1 1

M = 9

C

K˝ onigova–Egerv´ aryho vˇeta: pˇr´ıklad

G

C

Hallova vˇeta

Hallova vˇeta

Vˇeta 7.2 (Hallova vˇeta, 1935)

Mnoˇzinov´y syst´em (Mi: i ∈I) m´a syst´em r˚uzn´ych reprezentant˚u pr´avˇe tehdy, kdyˇz pro kaˇzd´e J ⊆I plat´ı| ∪_j∈J M_j| ≥ |J|.

Obr´azek: Philip Hall(1904–1982).

Zdroj: http://en.wikipedia.org

• V angliˇctinˇe se tato vˇeta naz´yv´a

”Hall’s marriage theorem“.

Hallova vˇeta

Vˇeta 7.2 (Hallova vˇeta, 1935)

Mnoˇzinov´y syst´em (Mi: i ∈I) m´a syst´em r˚uzn´ych reprezentant˚u pr´avˇe tehdy, kdyˇz pro kaˇzd´e J ⊆I plat´ı| ∪_j∈J M_j| ≥ |J|.

Obr´azek:Philip Hall (1904–1982).

Zdroj: http://en.wikipedia.org

• V angliˇctinˇe se tato vˇeta naz´yv´a

”Hall’s marriage theorem“.

Hallova vˇeta

Vˇeta 7.2 (Hallova vˇeta, 1935)

Mnoˇzinov´y syst´em (Mi: i ∈I) m´a syst´em r˚uzn´ych reprezentant˚u pr´avˇe tehdy, kdyˇz pro kaˇzd´e J ⊆I plat´ı| ∪_j∈J M_j| ≥ |J|.

Obr´azek:Philip Hall (1904–1982).

Zdroj: http://en.wikipedia.org

• V angliˇctinˇe se tato vˇeta naz´yv´a

”Hall’s marriage theorem“.

Hallova vˇeta: pˇr´ıklad

Hallova vˇeta: pˇr´ıklad

Hallova vˇeta: pˇr´ıklad

Hallova vˇeta: pˇr´ıklad

Hallova vˇeta: pˇr´ıklad

Hallova vˇeta: pˇr´ıklad

Hallova vˇeta: pˇr´ıklad

Rozˇsiˇrov´ an´ı latinsk´ ych obd´eln´ık˚ u

Zdroj: www.britainexpress.com

Shall wee all dye wee Shall dye all

all dye Shall wee dye all wee Shall

Deska v St. Mawgan Church pˇripom´ınaj´ıc´ı Hanniballa Basseta ( 1709).

Dˇekuji za pozornost.

Zdroj: www.britainexpress.com

Shall wee all dye wee Shall dye all

all dye Shall wee dye all wee Shall

Deska v St. Mawgan Church pˇripom´ınaj´ıc´ı Hanniballa Basseta ( 1709).

Dˇekuji za pozornost.

Zdroj: www.britainexpress.com

Shall wee all dye wee Shall dye all

all dye Shall wee dye all wee Shall

Deska v St. Mawgan Church pˇripom´ınaj´ıc´ı Hanniballa Basseta ( 1709).

Dˇekuji za pozornost.

Zdroj: www.britainexpress.com

Shall wee all dye wee Shall dye all

all dye Shall wee dye all wee Shall

Deska v St. Mawgan Church pˇripom´ınaj´ıc´ı Hanniballa Basseta ( 1709).

Dˇekuji za pozornost.