Hlavolamy a teorie grafů

Hlavolamy a grafy

Osnova Pojem grafu Vrcholy a hrany

Hlavolamy a teorie graf˚ u

Eulerovsk´ e grafy Grafov´ a interpretace Putov´ an´ı grafem Pˇr´ıklady

Stavov´ y graf

Petr Kováˇr1 [email protected]

´ Uloha s v´ınem Barycentrick´ e souˇradnice Hanojsk´ e vˇ eˇze

Z´ avˇ er 1 Vysol´ a

ˇskola b´ an ˇsk´ a – Technick´ a univerzita Ostrava,

ˇ Skola matematického modelován´ı, 2009

Hlavolamy a grafy

Pˇrehled pˇredn´ aˇsky Osnova

Pojem grafu Vrcholy a hrany


Eulerovsk´ e grafy

Eulerovsk´ e grafy Grafová interpretace Putován´ı grafem Pˇr´ıklady Stavov´ y graf ´ Uloha s v´ınem Barycentrické souˇradnice ´ Uloha hanojských vˇeˇz´ı Z´ avˇ er

Grafov´ a interpretace Putov´ an´ı grafem Pˇr´ıklady

Stavov´ y graf ´ Uloha s v´ınem Barycentrick´ e souˇradnice Hanojsk´ e vˇ eˇze

Z´ avˇ er

ˇ ast 1. C´

Hlavolamy a grafy



Stavov´ y graf ´ Uloha s v´ınem

Pojem grafu

Barycentrick´ e souˇradnice Hanojsk´ e vˇ eˇze

Z´ avˇ er

Co nen´ı (n´ aˇs) graf ... Definice Graf je dvojice mnoˇzin (V , E ). V je neprázdná mnoˇzina vrchol˚ u, E je mnoˇzina dvouprvkových podmnoˇzin mnoˇziny V .

Hlavolamy a grafy




Z´ avˇ er

Hlavolamy a grafy

Co je graf?

Osnova

Definice (pˇreformulovan´ a) Graf je dvojice mnoˇzin (V , E ). V je mnoˇzina bod˚ u v rovinˇe a mnoˇzina hran E obsahuje spojnice vrchol˚ u v rovinˇe.



Stavov´ y graf

t u

´ Uloha s v´ınem

s


Z´ avˇ er

v

z y

w x

Graf je ˇsikovn´ y d´ıky pˇrehledn´ emu zn´ azornˇ en´ı.

Hlavolamy a grafy

t u

s


v

z y

w x I I I

objekty – vrcholy objekty spolu souvis´ı – mezi vrcholy je hrana objekty spolu nesouvis´ı – mezi vrcholy nen´ı hrana



Z´ avˇ er

Hlavolamy a grafy

Dalˇs´ı (jednoduch´ e) pojmy t u

Osnova

s


Eulerovsk´ e grafy

v

z


Stavov´ y graf

y

w x


Z´ avˇ er

I

Stupeˇ n vrcholu – poˇcet hran, které vycházej´ı z vrcholu.

I

Tah v grafu – posloupnost vrchol˚ u a hran, které na sebe “navazuj´ı”, ˇzádná hrana se neopakuje. Napˇr´ıklad u, s, z, u, x, z.

I

Souvislý graf – mezi kaˇzdými dvˇema vrcholy v grafu najdeme tah.

ˇ ast 2. C´

Hlavolamy a grafy




Eulerovské grafy


Z´ avˇ er

Historie pojmu graf Probl´ em most˚ u mˇ esta Kr´ alovce 1736 ˇ Pruské mˇesto Královec leˇz´ı na ˇrece Pregole. Reka vytváˇr´ı dva ostrovy, které byly s mˇestem spojeny sedmi mosty.

Hlavolamy a grafy




Z´ avˇ er

Ot´ azka Mohu vˇsechny mosty pˇrej´ıt tak, abych vstoupil na kaˇzdý most pouze jednou?

Hlavolamy a grafy

Leonhard Euler




Leonhard Euler (1707–1783) Problém byl vyˇreˇsen Leonhardem Eulerem v roce 1736. Euler dokázal, ˇze to moˇzné nen´ı. Vˇ eta Graf G lze nakreslit jedn´ım otevˇreným tahem právˇe kdyˇz G je souvislý a právˇe dva vrcholy v G jsou lichého stupnˇe.


Z´ avˇ er

Pˇreformulov´ an´ı do ˇreˇ ci teorie graf˚ u

Hlavolamy a grafy



Stavov´ y graf

Sestav´ıme graf: I vrcholy – oba bˇ rehy a oba ostrovy I hrany – mosty, kter´ e bˇrehy a ostrovy spojuj´ı

Proch´ azka v grafu: posloupnost vrchol˚ u a hran, které na sebe navazuj´ı.


Z´ avˇ er

Vˇ eta o kreslen´ı jedn´ım tahem Definice Tah v grafu G je taková posloupnost vrchol˚ u a hran

Hlavolamy a grafy


v0 , v0 v1 , v1 , v1 v2 , v2 , . . . , vn−1 vn , vn , kde vi jsou vrcholy grafu G a vi vi+1 jsou hrany grafu G a ˇzádná hrana se neopakuje. V cestˇe se neopakuj´ı ani vrcholy. Poˇcet hran tahu nazveme délkou tahu/cesty v0 vn . Definice Eulerovský tah je tah, který obsahuje vˇsechny hrany daného grafu. Graf, ve kterém existuje eulerovský tah se nazývá eulerovský graf. Vˇ eta Graf G je moˇzno nakreslit jedn´ım (uzavˇreným) tahem, právˇe kdyˇz G je souvislý a vˇsechny vrcholy v G jsou sudého stupnˇe. D˚ ukaz matematickou indukc´ı vzhledem k poˇctu hran.



Z´ avˇ er

Proch´ azka Kr´ alovcem nen´ı moˇ zn´ a

Hlavolamy a grafy




Z´ avˇ er

Vid´ıme ihned, uˇzit´ım Eulerovy vˇety.

Myˇslenka d˚ ukazu Indukc´ı vzhledem k poˇctu hran (jen myˇslenka d˚ ukazu). I Z´ aklad indukce: Lze pouˇz´ıt triviáln´ı graf. Pro netriviáln´ı souvislý graf G je kaˇzdý vrchol stupnˇe alespoˇ n 2. Nejmenˇs´ı takový graf je cyklus Cn . G je jistˇe moˇzno nakreslit jedn´ım uzavˇreným tahem (proˇc?). I Indukˇ cn´ı krok: Pˇredpokládejme, ˇze kaˇzdý souvislý graf s ménˇe neˇz |E | hranami je moˇzno nakreslit jedn´ım uzavˇreným tahem. V G najdeme cyklus C (kaˇzdý vrchol stupnˇe alespoˇ n 2). V grafu G − C jsou vrcholy sudého stupnˇe a nebo izolované vrcholy. Pokud G − C nen´ı souvislý, lze kaˇzdou jeho komponentu dle indukˇcn´ıho pˇredpokladu nakreslit jedn´ım tahem. Nyn´ı pˇridáme do cyklu C uzavˇrený tah pro kaˇzdý vrchol dalˇs´ı vi , který leˇz´ı v nˇekteré komponentˇe. Z´ıskáme uzavˇrený tah grafem G . Podle principu matematické indukce je d˚ ukaz hotov.

Hlavolamy a grafy




Z´ avˇ er

Dalˇs´ı vˇ eta o kreslen´ı jedn´ım a v´ıce tahy tahem

Hlavolamy a grafy


Vˇ eta Graf G lze nakreslit jedn´ım otevˇreným tahem, právˇe kdyˇz G je souvislý a právˇe dva vrcholy v G jsou lichého stupnˇe.



Vˇ eta Graf G lze nakreslit k otevˇrenými tahy, právˇe kdyˇz G je souvislý a právˇe 2k vrchol˚ u v G je lichého stupnˇe. Dokáˇz´ı se jako d˚ usledek prvn´ı vˇety.


Z´ avˇ er

Dalˇs´ı aplikace

Hlavolamy a grafy

Osnova

Jednotaˇ zky


I

kdy jde obrázek nakreslit jedn´ım tahem?

I

kdy nejde obrázek nakreslit jedn´ım tahem?

I

kolika (minimálnˇe) tahy jde obrázek nakreslit?

Pˇr´ıklady, kdy preferujeme “kreslen´ı jedn´ım tahem” I

ukl´ızen´ı snˇehu z ulic

I

vyváˇzen´ı odpadk˚ u

I

roznáˇsen´ı poˇsty

I

vyˇs´ıván´ı

I

v teorii kódován´ı



Z´ avˇ er

Samozˇrejmˇe nˇekdy má smysl ˇreˇsit u ´lohy v´ıce tahy.

Hlavolamy a grafy

Pˇr´ıklady Jde následuj´ıc´ı obrázek nakreslit jedn´ım tahem?




Z´ avˇ er

Ano!

Hlavolamy a grafy

Pˇr´ıklady Jde následuj´ıc´ı obrázek nakreslit jedn´ım tahem?




Z´ avˇ er

Ne!

ˇ ast 3. C´

Hlavolamy a grafy




Stavový graf


Z´ avˇ er

´ Uloha s v´ınem Máme osmi litrovou nádobu s v´ınem a dvˇe prázdné nádoby – pˇetilitrovou a tˇr´ılitrovou. Rozdˇelte osm litr˚ u na ˇctyˇri a ˇctyˇri litry jen s uˇzit´ım tˇechto nádob, bez pouˇzit´ı odmˇerky. Ve zjednoduˇsené verzi pouˇzito ve filmu Smrtonosná past 3: John McClain (Bruce Willis) a Zeus (Samuel L. Jackson) mus´ı odmˇeˇrit 4 galony vody; maj´ı k dispozici nádoby o objemu tˇri a pˇet galon˚ u.

Hlavolamy a grafy




Z´ avˇ er

´ Ulohu zformulujeme v ˇreˇci teorie graf˚ u, vyˇreˇs´ıme, zobecn´ıme a zobecnˇenou u ´lohu také vyˇreˇs´ıme.

Hlavolamy a grafy

Stavov´ y graf

Osnova

8 litru


Eulerovsk´ e grafy

3 litry

5 litru


Stavov´ y graf

Je tˇreba vhodnˇe zvolit graf. Evidentnˇe nestaˇc´ı. Sestav´ıme tzv. stavový graf: I

kaˇzdý vrchol reprezentuje pˇr´ıpustné rozdˇelen´ı osmi litr˚ u do tˇr´ı nádob

I

hrany spoj´ı dva vrcholy, pokud je moˇzno z jednoho rozdˇelen´ı obdrˇzet pˇrelit´ım druhé rozdˇelen´ı a naopak

Orientované hrany, kdy je moˇzné pˇrelit´ı jen jedn´ım smˇerem, zavádˇet nebudeme.


Z´ avˇ er

ˇ sen´ı ve stavov´ Reˇ em grafu

Hlavolamy a grafy

Osnova

Dostaneme následuj´ıc´ı graf a snadno najdeme ˇreˇsen´ı.


(6, 2, 0)

(6, 0, 2)

Eulerovsk´ e grafy

(1, 5, 2)

(3, 2, 3) (1, 4, 3) (3, 5, 0)


Stavov´ y graf

(4, 4, 0) (8, 0, 0)

(0, 5, 3) (4, 1, 3)

(5, 0, 3) (7, 1, 0) (5, 3, 0) (2, 3, 3)

(7, 0, 1) (2, 5, 1)

I

existuje nˇekolik ˇreˇsen´ı (kolik?)

I

nejkratˇs´ı na sedm pˇrelit´ı


Z´ avˇ er

Hlavolamy a grafy

Jin´ y postup – barycentrick´ e souˇradnice

Osnova

Zvol´ıme v rovinˇe libovolný troj´ uheln´ık A1 A2 A3 .


A3 (0, 0, t3 )

A3 (0, 0, t3 )


t 1 + t2

Stavov´ y graf

t2

P (t1 , t2 , t3 )

t1

´ Uloha s v´ınem

P t3

t3 t2 t1 A1 (t1 , 0, 0) Q (t1 , t2 , 0) A2 (0, t2 , 0)

Eulerovsk´ e grafy

A1 (t1 , 0, 0)


A2 (0, t2 , 0)

P je hmotný stˇred soustavy s hmotnostmi t1 , t2 , t3 ve vrcholech A1 , A2 , A3 . Pro kaˇzdý bod v rovinˇe m˚ uˇzeme zvolit vhodné (i záporné) hmotnosti ti , dostaneme barycentrické souˇradnice.

Z´ avˇ er

Hlavolamy a grafy

Barycentrick´ e souˇradnice Rozm´ıst´ıme-li do vrchol˚ u A1 , A2 , A3 body o souˇctu hmotnost´ı t1 + t2 + t3 = k, dostaneme s´ıt’:


I

vrcholy na obrázku maj´ı celoˇc´ıselné souˇradnice,

I

hrana, jestliˇze se dvˇe souˇradnice liˇs´ı o jedniˇcku.


Stavov´ y graf

600 510

Eulerovsk´ e grafy

´ Uloha s v´ınem

501

420 330 240


402 303

Z´ avˇ er

204

150

105 006

060 051 042 033 024 015

I

Jak zobecnit pro v´ıce bod˚ u?

I

Jak by vypadal graf pro ˇctyˇrmi celoˇc´ıselné souˇradnice?

August M¨ obius (1790 – 1868)

Hlavolamy a grafy




Barycentrické souˇradnice zavedl August Möbius, matematik a astronom.

Möbi˚ uv ˇzebˇr´ık


Z´ avˇ er

ˇ sen´ı uˇ Reˇ zit´ım barycentrick´ ych souˇradnic Sestav´ıme graf:

Hlavolamy a grafy

Osnova

I

vrcholy – body o celkové hmotnosti 8,

Pojem grafu

I

hrany – dva vrcholy, jejichˇz barycentrické souˇradnice se liˇs´ı o jedniˇcku ve dvou sloˇzkách.

Eulerovsk´ e grafy

800 710 620 530 440 350 260

Vrcholy a hrany


Stavov´ y graf 701

´ Uloha s v´ınem

602


503 404

Z´ avˇ er

305 206

170

107 008

080 071 062 053 044 035 026 017

Prvn´ı souˇradnice odpov´ıdá osmilitrové nádobˇe, druhá pˇetilitrové nádobˇe a tˇret´ı tˇr´ılitrové nádobˇe. ˇ Cerven´ e hrany ohraniˇcuj´ı oblast, která odpov´ıdá omezen´ım u ´lohy.

ˇ sen´ı uˇ Reˇ zit´ım barycentrick´ ych souˇradnic

Hlavolamy a grafy

800 710 620 530 440 350

Osnova

701 602

Pojem grafu

503

Vrcholy a hrany

404

Eulerovsk´ e grafy

305

260

206

170

107 008

080 071 062 053 044 035 026 017

ˇ Cervenˇ e – výchoz´ı stav. Modˇre – hledané ˇreˇsen´ı. Mus´ıme vˇzdy pˇrel´ıt I

celý obsah jedné nádoby

I

nebo dol´ıt jinou nádobu do plna.

Pohybu po hranách uvnitˇr ˇcerveného oblasti “od kraje ke kraji”. Hledáme posloupnost ˇcar z ˇcerveného vrcholu do modrého vrcholu.



Z´ avˇ er

Hlavolamy a grafy

Kroky ˇreˇsen´ı 800 710 620 530 440 350 260

Osnova

701 602

Pojem grafu

503

Vrcholy a hrany

404

Eulerovsk´ e grafy

305 206

170

107 008

080 071 062 053 044 035 026 017

Vyjdeme z vrcholu (800). 1. 2. 3. 4. 5. 6. 7.

napln´ıme pˇetilitrovou nádobu; pˇrejdeme do (350). z 5-litrové napln´ıme 3-litrovou; pˇrejdeme do (323). obsah 3-litrové do 8-litrové; pˇrejdeme do (620). obsah 5-litrové do 3-litrové nádoby; pˇrejdeme do (602). z 8-litrové 5-litrovou nádobu; pˇrejdeme do (152). z 5-litrové odlijeme do 3-litrové 1litr; pˇrejdeme do (143). obsah 3-litrové do 8-litrové nádoby; pˇrejdeme do (440).



Z´ avˇ er

Hlavolamy a grafy

Jin´ e probl´ emy

Osnova

Proˇc tak sloˇzitˇe?

Pojem grafu

Hod´ı se pro sloˇzitˇejˇs´ı problém!

Vrcholy a hrany

Eulerovsk´ e grafy

Zmˇen ˇte objem jedné nádoby tak, aby u ´loha nemˇela ˇreˇsen´ı. 800 710 620 530 440 350 260


Stavov´ y graf 701

´ Uloha s v´ınem

602


503 404

Z´ avˇ er

305 206

170

107 008

080 071 062 053 044 035 026 017

Nemus´ıme zkouˇset r˚ uzná ˇc´ısla, z grafu s barycentrickými souˇradnicemi uvid´ıme hned: tˇreba 8, 6 a 5 litr˚ u. Na zelenou “smyˇcku” nen´ı moˇzné podle pravidel vstoupit!

´ Uloha hanojsk´ ych vˇ eˇ z´ı

Hlavolamy a grafy




Máme tˇri kol´ıky a sadu osmi disk˚ u r˚ uzných velikost´ı. Vˇsechny ´ disky jsou seˇrazeny podle velikosti na prvn´ım k˚ ulu. Ukolem je pˇrem´ıstit vˇsechny disky na jiný k˚ ul. I

Vˇzdy se pˇresunuje pouze jeden disk,

I

nikdy nesm´ı leˇzet vˇetˇs´ı disk na menˇs´ım.

Najdˇete nejmenˇs´ı moˇzný poˇcet pˇresun˚ u, které jsou nutné pro pˇrem´ıstˇen´ı celé vˇeˇze.

Z´ avˇ er

Autor hlavolamu hanojsk´ ych vˇ eˇ z´ı

Hlavolamy a grafy




Z´ avˇ er

´ Edouard Lucas (1842 – 1891)

Grafov´ a formulace – stavov´ y graf

Hlavolamy a grafy

Osnova Pojem grafu

Pˇri ˇreˇsen´ı opˇet sestav´ıme stavový graf: I

vrcholy – kaˇzdé rozm´ıstˇen´ı disk˚ u na k˚ uly

I

hrany – existuje regulérn´ı tah mezi vrcholy

Vrcholy a hrany



Z´ avˇ er

´ Uloha s jediným diskem.

Grafov´ a formulace – stavov´ y graf

Hlavolamy a grafy




Z´ avˇ er

´ Uloha se dvˇema disky. Pro dva disky rozliˇs´ıme tˇri moˇznosti, kde leˇz´ı nejvˇetˇs´ı disk. Pro kaˇzdou z nich zkop´ırujeme stavový graf pro jeden disk. Pˇridáme hrany, pokud m˚ uˇzeme pˇresunout nejvˇetˇs´ı disk.

Hlavolamy a grafy

Grafov´ a formulace




Z´ avˇ er

Podobnˇe pro tˇri disky.

Hlavolamy a grafy

Grafov´ a formulace




Z´ avˇ er

Pro pˇet disk˚ u.

ˇ sen´ı Reˇ

Hlavolamy a grafy


Eulerovsk´ e grafy

Máme-li n disk˚ u, tak I

existuje 3n moˇzných stav˚ u 3n

I

graf má

moˇzných stav˚ u

I

vˇsechny disky na jednom k˚ ulu – “rohové” vrcholy grafu

I

nejrychlejˇs´ı ˇreˇsen´ı = nejkratˇs´ı cesta

I

vˇzdy nejménˇe 2n − 1 tah˚ u



Z´ avˇ er

Dalˇs´ı aplikace

Hlavolamy a grafy


I

Problém obchodn´ıho cestuj´ıc´ıho

I

Jezdec na ˇsachovnici

I

Domino na ˇsachovnici

I

Triomino/tetramino na ˇsachovnici



Z´ avˇ er

Reklama: web: http://homel.vsb.cz/ kov16/ulohy Google: “zaj´ımavé u ´lohy”

Hlavolamy a grafy



Dˇekuji za pozornost.


Z´ avˇ er

Hlavolamy a teorie grafů

Recommend Documents