Kombinatorika a grafy I

Kombinatorika a grafy I

Martin Balko

8. pˇredn´ aˇska

23. listopadu 2021

M´ıra souvislosti graf˚ u

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

• Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Pˇripomenut´ı z diskr´etn´ı matematiky

• Graf G je souvisl´y, pokud kaˇzd´e dva vrcholy jsou vG spojeny cestou.

• Jinak jeG nesouvisl´y a rozpad´a se na komponenty souvislosti.

• Jak moc je graf odoln´y proti rozpadnut´ı pˇri odeb´ır´an´ı hran/vrchol˚u?

Petersen˚ uv graf

Obr´azek:Julius Petersen (1839–1910) a Petersen˚uv graf.

Zdroj: http://en.wikipedia.org

Petersen˚ uv graf

Obr´azek:Julius Petersen (1839–1910) a Petersen˚uv graf.

Zdroj: http://en.wikipedia.org

Petersen˚ uv graf

Obr´azek:Julius Petersen (1839–1910) a Petersen˚uv graf.

Zdroj: http://en.wikipedia.org

Petersen˚ uv graf

ke(Petersen) = 3

Obr´azek:Julius Petersen (1839–1910) a Petersen˚uv graf.

Zdroj: http://en.wikipedia.org

Petersen˚ uv graf

ke(Petersen) = 3

Obr´azek:Julius Petersen (1839–1910) a Petersen˚uv graf.

Zdroj: http://en.wikipedia.org

Petersen˚ uv graf

kv(Petersen) = 3 ke(Petersen) = 3

Obr´azek:Julius Petersen (1839–1910) a Petersen˚uv graf.

Zdroj: http://en.wikipedia.org

Chv´ atal˚ uv graf

Obr´azek:V´aclav Chv´atal(narozen 1946) a Chv´atal˚uv graf.

Zdroj: http://en.wikipedia.org

Chv´ atal˚ uv graf

Obr´azek:V´aclav Chv´atal(narozen 1946) a Chv´atal˚uv graf.

Zdroj: http://en.wikipedia.org

Chv´ atal˚ uv graf

Obr´azek:V´aclav Chv´atal(narozen 1946) a Chv´atal˚uv graf.

Zdroj: http://en.wikipedia.org

Chv´ atal˚ uv graf

ke(Chv´atal) = 4

Obr´azek:V´aclav Chv´atal(narozen 1946) a Chv´atal˚uv graf.

Zdroj: http://en.wikipedia.org

Chv´ atal˚ uv graf

ke(Chv´atal) = 4

Obr´azek:V´aclav Chv´atal(narozen 1946) a Chv´atal˚uv graf.

Zdroj: http://en.wikipedia.org

Chv´ atal˚ uv graf

k_v(Chv´atal) = 4 ke(Chv´atal) = 4

Obr´azek:V´aclav Chv´atal(narozen 1946) a Chv´atal˚uv graf.

Zdroj: http://en.wikipedia.org

Moser spindle

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde vR = (R²,E) plat´ı {x,y} ∈E ⇔ kx−yk= 1?

Moser spindle d´av´a χ(R)≥4, v´ı se, ˇze 5≤χ(R)≤7.

Moser spindle

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde vR = (R²,E) plat´ı {x,y} ∈E ⇔ kx−yk= 1?

Moser spindle d´av´a χ(R)≥4, v´ı se, ˇze 5≤χ(R)≤7.

Moser spindle

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde v R = (R²,E) je {x,y} ∈E ⇔ kx−yk= 1?

Moser spindle d´av´a χ(R)≥4, v´ı se, ˇze 5≤χ(R)≤7.

Moser spindle

k_e(Moser) = 3

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde v R = (R²,E) je {x,y} ∈E ⇔ kx−yk= 1?

Moser spindle d´av´a χ(R)≥4, v´ı se, ˇze 5≤χ(R)≤7.

Moser spindle

k_e(Moser) = 3

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde v R = (R²,E) je {x,y} ∈E ⇔ kx−yk= 1?

Moser spindle d´av´a χ(R)≥4, v´ı se, ˇze 5≤χ(R)≤7.

Moser spindle

kv(Moser) = 2 k_e(Moser) = 3

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

• Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde vR = (R²,E) plat´ı {x,y} ∈E ⇔ kx−yk= 1?

• Moser spindle d´av´a χ(R)≥4 a je zn´amo, ˇze 5≤χ(R)≤7.

Moser spindle

kv(Moser) = 2 k_e(Moser) = 3

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

• Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde vR = (R²,E) plat´ı {x,y} ∈E ⇔ kx−yk= 1?

• Moser spindle d´av´a χ(R)≥4 a je zn´amo, ˇze 5≤χ(R)≤7.

Moser spindle

kv(Moser) = 2 k_e(Moser) = 3

Obr´azek:Leo Moser (1921–1970) a Moser spindle.

Zdroj: http://googology.wikia.com

• Chromatick´e ˇc´ıslo roviny: ˇCemu se rovn´a χ(R), kde vR = (R²,E) plat´ı {x,y} ∈E ⇔ kx−yk= 1?

• Moser spindle d´av´a χ(R)≥4 a je zn´amo, ˇze 5≤χ(R)≤7.

Mot´ yl

Zdroj: http://img.signaly.cz

Mot´ yl

Zdroj: http://img.signaly.cz

Mot´ yl

ke(Mot´yl) = 2

Zdroj: http://img.signaly.cz

Mot´ yl

ke(Mot´yl) = 2

Zdroj: http://img.signaly.cz

Mot´ yl

kv(Mot´yl) = 1 ke(Mot´yl) = 2

Zdroj: http://img.signaly.cz

Obr´azek:Obarven´ı roviny sedmi barvami bez dvou stejnˇe obarven´ych bod˚u v jednotkov´e vzd´alenosti. Neboli d˚ukaz odhaduχ(R)≤7.

Dˇekuji za pozornost.

Obr´azek:Obarven´ı roviny sedmi barvami bez dvou stejnˇe obarven´ych bod˚u v jednotkov´e vzd´alenosti. Neboli d˚ukaz odhaduχ(R)≤7.

Dˇekuji za pozornost.

Obr´azek:Obarven´ı roviny sedmi barvami bez dvou stejnˇe obarven´ych bod˚u v jednotkov´e vzd´alenosti. Neboli d˚ukaz odhaduχ(R)≤7.

Dˇekuji za pozornost.