Kombinatorika a grafy I

Kombinatorika a grafy I

Martin Balko

9. pˇredn´ aˇska

30. listopadu 2021

M´ıra souvislosti graf˚ u

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula I

• Hranov´y ˇrez v grafu G = (V,E) je F ⊆E takov´a, ˇze G−F je nesouvisl´y.

• Vrcholov´y ˇrez v grafu G je A⊆V takov´a, ˇze G−A je nesouvisl´y.

• Hranov´a souvislost grafuG je k_e(G)=

(1, je-li G ∼=K₁,

min{|F|:F je hranov´y ˇrez v G}, jinak.

• Vrcholov´a souvislost grafuG je

k_v(G)=







1, je-liG ∼=K₁,

n−1, je-liG ∼=K_n sn ≥2,

min{|A|:A je vrcholov´y ˇrez v G}, jinak.

• Graf G je hranovˇe t-souvisl´y, pokudk_e(G)≥t.

• Graf G je vrcholovˇet-souvisl´y, pokud k_v(G)≥t.

Pˇripomenut´ı z minula II

• Pˇri odebr´an´ı hrany hranov´a ani vrcholov´a souvislost grafu nevzroste a obˇe klesnou nanejv´yˇs o 1.

• Pro kaˇzd´y graf G plat´ıkv(G)≤ke(G).

Fordova–Fulkersonova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_e(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t hranovˇe disjunktn´ıch cest.

Mengerova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_v(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t vrcholovˇe disjunktn´ıch cest (mimo jejich koncov´e vrcholy).

Pˇripomenut´ı z minula II

• Pˇri odebr´an´ı hrany hranov´a ani vrcholov´a souvislost grafu nevzroste a obˇe klesnou nanejv´yˇs o 1.

• Pro kaˇzd´y graf G plat´ıkv(G)≤ke(G).

Fordova–Fulkersonova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_e(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t hranovˇe disjunktn´ıch cest.

Mengerova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_v(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t vrcholovˇe disjunktn´ıch cest (mimo jejich koncov´e vrcholy).

Pˇripomenut´ı z minula II

• Pˇri odebr´an´ı hrany hranov´a ani vrcholov´a souvislost grafu nevzroste a obˇe klesnou nanejv´yˇs o 1.

• Pro kaˇzd´y graf G plat´ıkv(G)≤ke(G).

Fordova–Fulkersonova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_e(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t hranovˇe disjunktn´ıch cest.

Mengerova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_v(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t vrcholovˇe disjunktn´ıch cest (mimo jejich koncov´e vrcholy).

Pˇripomenut´ı z minula II

• Pˇri odebr´an´ı hrany hranov´a ani vrcholov´a souvislost grafu nevzroste a obˇe klesnou nanejv´yˇs o 1.

• Pro kaˇzd´y graf G plat´ıkv(G)≤ke(G).

Fordova–Fulkersonova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_e(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t hranovˇe disjunktn´ıch cest.

Mengerova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_v(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t vrcholovˇe disjunktn´ıch cest (mimo jejich koncov´e vrcholy).

Pˇripomenut´ı z minula II

• Pˇri odebr´an´ı hrany hranov´a ani vrcholov´a souvislost grafu nevzroste a obˇe klesnou nanejv´yˇs o 1.

• Pro kaˇzd´y graf G plat´ıkv(G)≤ke(G).

Fordova–Fulkersonova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_e(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t hranovˇe disjunktn´ıch cest.

Mengerova vˇeta

Pro kaˇzd´y graf G a t ∈N plat´ı: k_v(G)≥t pr´avˇe tehdy, kdyˇz mezi kaˇzd´ymi dvˇema vrcholy z G existuje aspoˇn t vrcholovˇe disjunktn´ıch cest (mimo jejich koncov´e vrcholy).

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Konstrukce vrcholovˇe 2-souvisl´ ych graf˚ u lepen´ım uˇs´ı

Poˇc´ıt´ an´ı dvˇema zp˚ usoby

Poˇc´ıt´ame-li prvky jedn´e mnoˇziny dvˇema zp˚usoby, dostaneme vˇzdy stejn´y v´ysledek.

Poˇc´ıt´ an´ı dvˇema zp˚ usoby

Poˇc´ıt´ame-li prvky jedn´e mnoˇziny dvˇema zp˚usoby, dostaneme vˇzdy stejn´y v´ysledek.

Poˇcet koster v grafu K

κ(2) = 1

Poˇcet koster v grafu K

κ(2) = 1

Poˇcet koster v grafu K

κ(2) = 1

κ(3) = 3

Poˇcet koster v grafu K

κ(2) = 1

κ(3) = 3

κ(4) = 16

Cayleyho vzorec

• Pro kaˇzd´en ≥1 se poˇcet koster grafuK_n rovn´a nⁿ⁻².

• Objevil ho Carl Wilhelm Borchardt v roce 1860.

Obr´azek:Carl Wilhelm Borchardt(1817–1880) aArthur Cayley (1821–1895).

Zdroje: http://en.wikipedia.org a http://math-physics-problems.wikia.org

Cayleyho vzorec

• Pro kaˇzd´en ≥1 se poˇcet koster grafuK_n rovn´a nⁿ⁻².

• Objevil ho Carl Wilhelm Borchardt v roce 1860.

Obr´azek:Carl Wilhelm Borchardt(1817–1880) aArthur Cayley (1821–1895).

Zdroje: http://en.wikipedia.org a http://math-physics-problems.wikia.org

Cayleyho vzorec

• Pro kaˇzd´en ≥1 se poˇcet koster grafuK_n rovn´a nⁿ⁻².

• Objevil ho Carl Wilhelm Borchardt v roce 1860.

Obr´azek:Carl Wilhelm Borchardt(1817–1880) aArthur Cayley (1821–1895).

Zdroje: http://en.wikipedia.org a http://math-physics-problems.wikia.org

Cayleyho vzorec

• Pro kaˇzd´en ≥1 se poˇcet koster grafuK_n rovn´a nⁿ⁻².

• Objevil ho Carl Wilhelm Borchardt v roce 1860.

Obr´azek:Carl Wilhelm Borchardt(1817–1880) aArthur Cayley (1821–1895).

Zdroje: http://en.wikipedia.org a http://math-physics-problems.wikia.org

Cayleyho vzorec: d˚ ukazy

• Existuje ˇrada d˚ukaz˚u. ˇCtyˇri jsou pops´any v knize Proofs from the Book.

Obr´azek:Paul Erd˝os (1913–1996) aProofs from the Book.

Zdroje: http://en.wikipedia.org

• Uk´aˇzeme nejjednoduˇsˇs´ı z nich, objeven´y Jimem Pitmanem v roce 1999.

Cayleyho vzorec: d˚ ukazy

• Existuje ˇrada d˚ukaz˚u. ˇCtyˇri jsou pops´any v knize Proofs from the Book.

Obr´azek:Paul Erd˝os (1913–1996) aProofs from the Book.

Zdroje: http://en.wikipedia.org

• Uk´aˇzeme nejjednoduˇsˇs´ı z nich, objeven´y Jimem Pitmanem v roce 1999.

Cayleyho vzorec: d˚ ukazy

• Existuje ˇrada d˚ukaz˚u. ˇCtyˇri jsou pops´any v knize Proofs from the Book.

Obr´azek:Paul Erd˝os (1913–1996) aProofs from the Book.

Zdroje: http://en.wikipedia.org

• Uk´aˇzeme nejjednoduˇsˇs´ı z nich, objeven´y Jimem Pitmanem v roce 1999.

Cayleyho vzorec: d˚ ukazy

• Existuje ˇrada d˚ukaz˚u. ˇCtyˇri jsou pops´any v knize Proofs from the Book.

Obr´azek:Paul Erd˝os (1913–1996) aProofs from the Book.

Zdroje: http://en.wikipedia.org

• Uk´aˇzeme nejjednoduˇsˇs´ı z nich, objeven´y Jimem Pitmanem v roce 1999.

Poˇcet koster v grafu K

− e

Poˇcet koster v grafu K

− e

Poˇcet koster v grafu K

− e

κ(K2−e) = 0

Poˇcet koster v grafu K

− e

κ(K2−e) = 0

Poˇcet koster v grafu K

− e

κ(K2−e) = 0

κ(K3−e) = 1

Poˇcet koster v grafu K

− e

κ(K2−e) = 0

κ(K3−e) = 1

Poˇcet koster v grafu K

− e

κ(K2−e) = 0

κ(K3−e) = 1

κ(K4−e) = 8

Zdroj:

”Proofs from the Book“ (Aigner, Ziegler)

Dˇekuji za pozornost.

Zdroj:

”Proofs from the Book“ (Aigner, Ziegler)

Dˇekuji za pozornost.