MA2BP_PDM1 Diskrétní matematika 1
8. Rovinné grafy, barvení grafů, Platónova tělesa
Lukáš Másilko
Středisko pro pomoc studentům se specifickými nároky
Masarykova univerzita
29. 11. 2017
29. 11. 2017       1 / 34
Program prezentace
□ Rovinné grafy B Eulerova věta Q Barvení grafů
□ Platónova tělesa H Použité zdroje
29. 11. 2017       2 / 34
Rozplétání propletence
Na obrázku nalevo je zobrazeno osm kuliček, které jsou vzájemně spojeny gumičkami. Které kuličky posunete, abyste dostali jejich rozestavení na obrázku napravo?
Ukol spočívající v nalezení rovinné reprezentace grafu.
29. 11. 2017       3 / 34
Rozpletaní propletence - řešení
Zkusíme posunout dvojici vrcholů g,h.
29. 11. 2017       4 / 34
Rozplétání propletence - řešení
Výsledek posunutí vrcholů g,h doprava společně s hranami, které jsou s nimi incidentní:
29. 11. 2017       4 / 34
Rozpletaní propletence - řešení
Zkusíme posunout dvojici vrcholů b, d, a to tak, že uzel b s jeho hranami posuneme dolů, uzel d a jeho hrany směrem nahoru.
29. 11. 2017       4 / 34
Rozplétání propletence - řešení
Výsledek posunutí vrcholů g,h doprava společně s hranami, které jsou s nimi incidentní:
29. 11. 2017       4 / 34
Rozpletaní propletence - řešení
Rovinné zobrazení obou grafů je již stejné, dosáhli jsme toho posunutím kuliček b, c/, g", h.
29. 11. 2017       4 / 34
Rovinný graf
Definice 2.4 (MILKOVA): Rovinný graf je graf, ke kterému existuje tzv. rovinná reprezentace (rovinné nakreslení), tj. můžeme jej nakreslit do roviny tak, aby se žádné dvě hrany nekřížily (neprotínaly ve vnitřním bodě) - hrany se mohou protínat jen ve vrcholech.
Platí následující dvě tvrzení poskytující nutné podmínky pro to, aby byl graf rovinný.
Tvrzení 2.4 (MILKOVA): Pro každý graf G = (\/, E) s alespoň třemi vrcholy platí:    Jestliže je G rovinný graf, pak \ E\ < 3 • | V\ — 6.
Tvrzení 2.5 (MILKOVA): Pro každý graf G = (V, E) s alespoň třemi vrcholy, který neobsahuje K3 jako podgraf, platí: Jestliže je G rovinný graf, pak \E\ < 2 • | V\ — 4.
29. 11. 2017       5 / 34
Kuratowského grafy
■ Významným matematikem, který významně přispěl k problematice rovinných grafů, byl Polák Kazimierz Kuratowski (1896-1980). Dva nejznámější grafy, které nejsou rovinné, dostaly jeho jméno.
■ Kuratowského grafy: K5 (nalevo) a K33 (napravo).
Skóre K5\ (4, 4, 4, 4, 4) Skóre K-$^\ (3, 3, 3, 3, 3, 3)
29. 11. 2017       6 / 34
Kuratowského grafy - proč nejsou rovinné?
Skóre K5: (4, 4, 4, 4, 4) =4> K5 má 5 vrcholů a 10 hran, jako svůj podgraf obsahuje K3. Můžeme ověřit pouze nutnou podmínku v Tvrzení 2.4:
E\ = 10,3 • \ V\ - 6 = 9     vztah \E\<3-\V\-6 neplatí.
U grafu K5 není splněna nutná podmínka Tvrzení 2.4, není proto rovinný.
29. 11. 2017       7 / 34
Kuratowského grafy - proč nejsou rovinné?
Skóre K33. (3, 3, 3, 3, 3, 3) =4> K33 má 6 vrcholů a 9 hran, jako svůj podgraf neobsahuje K3. Můžeme ověřit obě podmínky v Tvrzeních 2.4, 2.5.
3 • \ V\ - 6 = 12     vztah \E\ < 3 • \ V\ - 6 platí.
2 • | V\ - 4 = 8     vztah \E\ < 2 • | V\ - 4 neplatí.
U grafu /<3?3 není splněna nutná podmínka Tvrzení 2.5, není proto rovinný.
29. 11. 2017       8 / 34
Příklad 2.5
U následujícího grafu ověřte, zda je splněna podmínka v Tvrzení 2.4. Pokud ano, nakreslete jeho rovinnou reprezentaci.
29. 11. 2017       9 / 34
Příklad 2.5 - řešení
Skóre: (3, 3, 3,4,4,2,2,3,2) - (2,2,2,3,3, 3,3,4,4)     | V\ = 9, |£ 3 -|V| - 6 = 3-9-6 = 21 > 13,
podmínka Tvrzení 2.4 tedy je splněna. Zkusíme nyní uspořádat vrcholy v rovině jiným způsobem, aby se hrany nekřížily.
29. 11. 2017       10 / 34
Příklad 2.5 - řešení
Nejprve dvojici vrcholů a, d posuneme nad vrchol b
Příklad 2.5 - řešení
Vrchol e posuneme blíže k vrcholu f, abychom rozšířili oblast danou kružnicí (c, /, /7, e, c). Do středu této kružnice posuneme vrchol g.
□    g ► < -e ► < =
29. 11. 2017       10 / 34
Příklad 2.5 - řešení
Zbývá vyřešit vrchol c, který posuneme napravo od ostatních uzlů, čímž zrušíme poslední tři křížení hran.
29. 11. 2017       10 / 34
Nutná a dostačující podmínka rovinných grafů
Věta 2.3 (MILKOVA): Pro každý graf G = (V, E) platí:
Graf G je rovinný právě tehdy, když žádný podgraf grafu G není ani graf
K33, ani graf K$, ani libovolné dělení těchto dvou grafů.
Tuto větu formuloval a dokázal v r. 1929 Kazimierz Kuratowski - důkaz je velmi obtížný, nebudeme si jej uvádět. Použil pojem dělení grafu, který si vysvětlíme následující definicí.
Definice 2.5 (MILKOVA): Nechť je dán graf G = (V, E), hrana e = {x, y} G E a vrchol v £ V.
m Graf vzniklý z grafu G půlením hrany e je graf
(V U {v}, (E \ {e}) U {{x, v}; {v,y}}).
m Dělením grafu G nazýváme každý graf, který vznikl z grafu G postupným půlením hran.
29. 11. 2017       11 / 34
Dělení grafu - príklad
Na následujícím obrázku došlo k půlení hrany {c/, c}. Graf napravo je dělením grafu nalevo.
29. 11. 2017       12 / 34
Mapy
Definice 7.7 (FUCHS): Buď G = (\/, E) rovinný souvislý graf a je dáno některé jeho rovinné nakreslení. Označme 1/1/ množinu všech oblastí, na něž je tímto nakreslením rovina rozdělena (včetně "vnějšku"). Pak trojici M = (\/, E, l/l/) nazveme mapou.
Příklad: na následujícím obrázku jsou tři různá nakreslení grafu K4. Které z nich jsou mapy? Určete počet prvků množiny 1/1/ pro graf K4.
29. 11. 2017       13 / 34
Mapy
Definice 7.7 (FUCHS): Buď G = (\/, E) rovinný souvislý graf a je dáno některé jeho rovinné nakreslení. Označme W množinu všech oblastí, na něž je tímto nakreslením rovina rozdělena (včetně "vnějšku"). Pak trojici M = (\/, E, l/l/) nazveme mapou.
Řešení příkladu: Pouze na 2. a 3. obrázku jsou mapy obsahující čtyři oblasti (počítáme i "vnějšek" grafu).
29. 11. 2017       13 / 34
Eulerova věta
Věta 7.9 - Eulerova věta (FUCHS): Buď M = (V,E,W) libovolná mapa. Pak platí vztah
(*) +
E = 2
Důkaz: matematickou indukcí vzhledem k počtu hran mapy, tj. k číslu E
29. 11. 2017       14 / 34
Eulerova věta
Věta 7.9 - Eulerova věta (FUCHS): Buď M = (V, E, W) libovolná mapa. Pak platí vztah
(*)   |I/1/| + |V
E = 2
Důkaz: matematickou indukcí vzhledem k počtu hran mapy, tj. k číslu E
Báze: \E\ = 0, tedy mapa nemá žádnou hranu. Aby byla souvislá, musí mít pouze jeden vrchol, který rovinu nedělí na více oblastí. Platí tedy E = 0,\V\ = 1, W = 1,
z čehož W+V- E =1 + 1-0 = 2. Báze platí.
29. 11. 2017       14 / 34
Eulerova věta
Věta 7.9 - Eulerova věta (FUCHS): Buď M = (V, E, W) libovolná mapa. Pak platí vztah
(*) +
E = 2
Důkaz: matematickou indukcí vzhledem k počtu hran mapy, tj. k číslu E
Báze: \E\ = 0, tedy mapa nemá žádnou hranu. Aby byla souvislá, musí mít pouze jeden vrchol, který rovinu nedělí na více oblastí. Platí tedy E = 0,\V\ = 1, W = 1,
z čehož W+V- E =1 + 1-0 = 2. Báze platí.
Indukční předpoklad: Pro mapu M = (V, E, W) s \E\ < n (n G No) platí
(*) +
E =2
□        g ►   < -E ►   < =
•fy <\ (y
29. 11. 2017       14 / 34
Indukční krok důkazu Eulerovy věty
Indukční krok: Mějme mapu Mř = (V, E1\ l/l/7), pro kterou \Ef\ = n + 1 Rozlišíme dva případy:
(a) Mapa M' obsahuje most e = {x,y}.
(b) Mapa M' neobsahuje most.
□ s
=
29. 11. 2017       15 / 34
Indukční krok důkazu Eulerovy věty - případ (a)
□   g ► < -e ►
Indukční krok důkazu Eulerovy věty - případ (a)
Odebráním mostu e dostaneme nesouvislý graf M" — (V7, E' — {e}, W") o dvou komponentách - mapách Q\ — (Vi, Ei, l/l/i), Q2 = (v2, e2, I/I/2).
Obě mapy Qi, q2 niajř < n hran, dle indukčního předpokladu tedy platí:
|Wi| + |Vi|-|Ei| = 2 \W2\ + \V2\-\E2\ = 2
29. 11. 2017       16 / 34
Indukční krok důkazu Eulerovy věty - případ (a)
Porovnejme nyní oba grafy /Vf, M". Co se změnilo? H Počet vrcholů zůstal stejný: | Vr\ — \ V\ \ + | V2 B Počet hran se snížil o jednu, platí tedy |E;
Ei + E2 +1
Počet oblastí se odebráním mostu nezměnil, avšak "vnějšek" mapy Mf počítáme v mapách Qi a Q2 dvakrát, takže: W/ = l/l/i + I/I/2 — 1
29. 11. 2017       16 / 34
Indukční krok důkazu Eulerovy věty - případ (a)
Porovnejme nyní oba grafy M', M". Co se změnilo?
Počet vrcholů zůstal stejný: \ V'\ = \ Vi\ + \V2\
Počet hran se snížil o jednu, platí tedy \E'\ = \E±\ + \E2\ + 1
Počet oblastí se odebráním mostu nezměnil, avšak "vnějšek" mapy M' počítáme v mapách Qi a Q2 dvakrát, takže: \ W\ = \Wi\ + \ W2\ — 1
Nyní počítejme:
W + V - E'
=   {\W!\ + \W2\ - 1) + (\V!\ + \V2\)-
- (|Ei| + |E2| + l) =   {m\ + \Vi\-\E!\) + {\W2\ + \V2\ ■ = 2+2-2=2
I pro mapu M' s mostem a n + 1 hranami tedy tvrzení platí.
E2\)-2
□
13"
29. 11. 2017       16 / 34
Indukční krok důkazu Eulerovy věty - případ (b)
Případ (b) - M' o n + 1 hranách nemá most. Buď e G E' libovolná hrana. Dle Důsledku 1.2 (Milkova) tedy leží na nějaké kružnici.
□    g ► < -e ► < =
29. 11. 2017       17 / 34
Indukční krok důkazu Eulerovy věty - případ (b)
Označme C kružnici maximální délky, na níž leží hrana e.
□    g ► < -e ►
Indukční krok důkazu Eulerovy věty - případ (b)
□   g ► < -e ►
Indukční krok důkazu Eulerovy věty - případ (b)
Odebráním hrany e z mapy M' vznikne nová mapa M" — {V"\ E"\ l/l/") Uvnitř kružnice C jistě byla oblast, která odebráním hrany e zanikne.
Protože navíc E" — n, platidle indukčního předpokladu
l/l/" + V
E" =2
□        g ►   < -E ►   < =
•fy <\ (y
29. 11. 2017       17 / 34
Indukční krok důkazu Eulerovy věty - případ (b)
Porovnejme nyní oba grafy M7, M". Co se změnilo? h Počet vrcholů zůstal stejný: \ V\ — \ V"\. El Počet hran se snížil o jednu, platí tedy \E'\ = \E"\ + 1 B Počet oblastí se odebráním hrany e také snížil o jednu:
l/l/'
W" + 1
□ r3>
29. 11. 2017       17 / 34
Indukční krok důkazu Eulerovy věty - případ (b)
7/
Porovnejme nyní oba grafy /Vf, M". Co se změnilo?
H Počet vrcholů zůstal stejný: \ V'\ — {V1
B Počet hran se snížil o jednu, platí tedy |E'| = \E"\ + 1
B Počet oblastí se odebráním hrany e také snížil o jednu: \W'\ = \ W"\ + 1.
Nyní počítejme:
l/l/' + V1 - E1
=   (|I/H + 1) + |\/"|-(|E"| + 1)
= (i^i + i^i-ie^d + i-i
= 2+0=2
I pro mapu Mf s n + 1 hranami, která neobsahuje most, tvrzení platí
29. 11. 2017       17 / 34
V Příkladu 2.5 jsme zjistili, že následující graf G = (\/, E) je rovinný
Zjistěte pomocí Eulerovy věty, kolik oblastí obsahuje mapa vzniklá rovinným zakreslením grafu G.
Příklad 1 - řešení
Platí: \ V\ =9,\E\ = 13.
Eulerův vztah: |W| + |V|-|E| =2, z čehož | W\ + 9 - 13 = 2 =^ | W\ = 6, viz následující obrázek s rovinným zakreslením grafu G:
Tréninkové plochy pro hokejová družstva
Hokejový klub zajišťuje potřebný počet ledových ploch ke každodennímu tréninku jeho družstev. Z ekonomických důvodů chce zajistit minimální počet ledových ploch. Kolik ledových ploch musí zajistit, když ví, že jednotlivá družstva potřebují ledovou plochu k tréninku následovně.
Záci A		12:00-	-14:00
Žáci B		14:30-	-16:30
Dorostenci	A	15:30-	-17:30
Dorostenci	B	11:30-	-13:30
Junioři		17:00-	-19:00
Muži		18:00-	-19:30
29. 11. 2017       20 / 34
Barvení grafu
Definice 3.1, 3.2 (MILKOVA):
□ Obarvení grafu (obarvení vrcholů grafu) je ohodnocení vrcholů grafu hodnotami z množiny B (takzvanými barvami), a to takové, že žádné dva sousední vrcholy nejsou ohodnoceny (obarveny) stejnou barvou.
B Graf nazýváme r-barevným, jestliže existuje jeho obarvení r barvami.
Q Barevnost grafu (neboli vrcholová barevnost, též chromatické číslo) je nejmenší počet barev, který je potřebný k obarvení grafu. Značíme ji pricemz G je grat.
Poznámka: Mějme G = (\/, E). Pak platí:
■ x(G) = 1 pro graf neobsahující žádnou hranu (tzv. diskrétní graf).
■ x(G) = 2 pro strom či bipartitní graf.
■ x(G) ^ 3 pro graf obsahující kružnici liché délky.
■ x(G) = n pro úplný graf Kn.
29. 11. 2017       21 / 34
Tréninkové plochy pro hokejová družstva
Problém manažera hokejového klubu lze řešit grafově. Vrcholy grafu budou jednotlivá družstva. Dva uzly (družstva) spojíme hranou, pokud se jejich časový požadavek "kříží". Ještě jednou si zobrazíme tabulku s požadavky:
zA	Záci A		12:00-	-14:00
zB	Žáci B		14:30-	■16:30
dA	Dorostenci	A	15:30-	■17:30
dB	Dorostenci	B	11:30-	■13:30
j	Junioři		17:00-	-19:00
m	Muži		18:00-	■19:30
Převedeme ji do grafu (viz následující slajd).
< rS ► <     ► <     *■     -š    -O Q, O
29. 11. 2017       22 / 34
Tréninkové plochy pro hokejová družstva
zA	Záci A	12:00-	■14:00
zB	Žáci B	14:30-	■16:30
dA	Dorostenci A	15:30-	-17:30
dB	Dorostenci B	11:30-	■13:30
j	Junioři	17:00-	■19:00
m	Muži	18:00-	-19:30
Tréninkové plochy pro hokejová družstva
Graf můžeme obarvit např. takto:
Tréninkové plochy pro hokejová družstva
Graf můžeme obarvit např. takto:
Platí        = 2, tedy hokejový klub bude zajišťovat dvě ledové plochy.
29. 11. 2017       23 / 34
Problém čtyř barev
■ Kolik barev stačí na obarvení států zobrazených na mapě či globusu?
■ Poprvé si tuto otázku položil Francis Guthrie (1831-1899) a oslovil s ní učitele svého bratra, Augusta de Morgana (1806-1871) na University College v Londýně.
■ A. de Morgan poslal 23. října 1852 dopis W. R. Hamiltonovi a začal sdílet problém i s ostatními.
■ Alfred Bray Kempe (1849-1922), londýnský advokát, zveřejnil 17. července 1879 důkaz a byl nadšeně oslavován.
■ V r. 1890 upozornil Percy John Heawood (1861-1955) na chybu v důkazu Kempeho, který ji poté sám přiznal.
■ Řada dalších významných matematiků problém zkoumala ve 20. století.
29. 11. 2017       24 / 34
Problém čtyř barev
Věta 3.1 - Problém čtyř barev (MILKOVA): Pro libovolný graf G = (V,E) platí:
Jestliže je graf G rovinný, pak barevnost grafu G je menší nebo rovna 4.
Až v 70. letech 20. století vyřešili problém čtyř barev Američané Kenneth Appel a Wolfgang Haken. Provedli jej s pomocí počítačů IBM. Přípravě programu a ověření dat věnovali 4 roky svého života, počítače pracovaly 1200 hodin strojového času. Potvrdili tak velmi důležitou větu teorie grafů.
Podrobnosti k Problému čtyř barev včetně popisu metod, jak se matematici snažili větu dokázat, lze nalézt v [SISMA].
29. 11. 2017       25 / 34
Historie Platónových těles
■ Již staří Rekové znali pět pravidelných mnohostěnů (čtyřstěn, šestistěn, osmistěn, dvanáctistěn, dvacetistěn), nazývají se podle řeckého filozofa Platóna (427-347 př. n. I.).
■ Eukleidés (též Euklides či Euklid, 325-260 př. n. I.) Platónova tělesa matematicky popsal a podal návod, jak je zkonstruovat. Tvrdil, že jiný pravidelný mnohostěn neexistuje.
■ Platónovo těleso - pravidelný konvexní mnohostěn (polyedr) v 3D, tj. z každého vrcholu vychází stejný počet hran a všechny stěny tvoří shodné pravidelné mnohoúhelníky (citujeme z Wikipedie)
29. 11. 2017       26 / 34
Hvězdovitá množina
Definice (FUCHS, str. 145): Omezená množina T C E3 se nazývá hvězdovitá, když existuje bod s £ T takový, že každá polopřímka s počátečním bodem s má s hranicí množiny T právě jeden společný bod.
Poznámka:
■ Většina známých těles (koule, hranol, válec, atd.) jsou hvězdovitá množiny. Též pravidelné konvexní mnohostěny jsou hvězdovitá.
■ Hranici hvězdovitá množiny lze zobrazit spojitou bijekcí na sféru (kulovou plochu).
29. 11. 2017       27 / 34
Stereografická projekce
Stereografická projekce - zobrazení sféry s vyjmutým jedním bodem na rovinu.
N
Každý bod x sféry S (s výjimkou N) zobrazíme na rovinu pomocí polopřímky vedené z bodu N přes x na rovinu E2. Toto zobrazení ŕ je spojitá bijekce.
29. 11. 2017       28 / 34
Jak dokázat, že více Platónových těles není?
■ Libovolnou hvězdovitou množinu zobrazíme na sféru =4> vznikne
mapa .
■ Mapu na sféře zobrazíme pomocí stereografické projekce na rovinu E2 =4> dostaneme mapu v rovině, pro níž platí Eulerova věta =4> i pro mapy na sféře platí Eulerova věta.
■ Pomocí Eulerovy věty, několika dalších faktů a algebraického počítání ukážeme, že není více než 5 Platónových těles.
■ Uvažujme nyní pravidelný mnohostěn T. Označme
Q R = počet jeho stěn,
h /W = počet jeho hran,
h A/ = počet jeho vrcholů,
Q n = počet stran jedné stěny,
0 p = počet hran sbíhajících se v jednom vrcholu.
■ Řetězec [r?,p] se nazývá Schlafliův symbol pravidelného mnohostěnu, např. [4,3] označuje krychli.
29. 11. 2017       29 / 34
Co budeme k důkazu potřebovat?
■ Máme pravidelný mnohostěn T = [r?, p], pro něhož platí toto označení: R = počet jeho stěn, M = počet jeho hran, N = počet jeho vrcholů, n = počet stran jedné stěny, p = počet hran sbíhajících se v jednom vrcholu.
■ Každá hrana spojuje dva vrcholy a v každém vrcholu se sbíhá p hran, platí tedy
(*)   A/p = 2M
■ Každá stěna je omezena n hranami a každá hrana sousedí se dvěma stěnami, platí tedy
(**)   Rn = 2M
■ Platí Eulerova věta:
(***)   N + R - M = 2
29. 11. 2017       30 / 34
Matematická část důkazu
Máme tedy tři rovnice o proměnných M, N, R a parametrech n, p:
Np  = 2M Rn   = 2M N + R - M  = 2
29. 11. 2017       31 / 34
Matematická část důkazu
Máme tedy tři rovnice o proměnných M, A/, R a parametrech n,p:
Np   = 2M Rn   = 2M N + R - M  = 2
Úpravou dostaneme následující vyjádření proměnných:
2r?p
M =
N =
2p + 2n — np 4n
2p + 2n — np
R = _*E_
2p + 2n — np
29. 11. 2017       31 / 34
Matematická část důkazu
Úpravou dostaneme následující vyjádření proměnných:
2np
2p + 2n — np 4n
2p + 2n — np 4p
2p + 2n — np
Protože všechny proměnné jsou kladné a n > 3, p > 3, musí být jmenovatel zlomků 2p + 2n — np > 0. Další úpravou dostaneme:
2p + 2n-np   > 0 np — 2p — 2n   < 0 (n-2)(p-2)   < 4
M = N = R =
29. 11. 2017       31 / 34
Matematická část důkazu
Protože všechny proměnné jsou kladné a n > 3, p > 3, musí být jmenovatel zlomků 2p + 2n — np > 0. Další úpravou dostaneme:
Protože n>3Ap>3A(n — 2)(p — 2) < 4, musí n, p € {3,4,5} a máme těchto pět možných případů:
O (n - 2)(p - 2) = 1 =>• n = 3, p = 3 ... čtyřstěn [3, 3]
B (n-2)(p-2) = 2^(n = 4,p = 3)V(n = 3,p = 4) ... krychle [4,3] nebo osmistěn [3,4]
M (n- 2)(p - 2) = 3     (n = 5, p = 3) V (n = 3, p = 5) ... dvanáctistěn [5,3] nebo dvacetistěn [3,5]
2p + 2n np-2p (n-2)(p
np > 0 2n < 0 2)   < 4
29. 11. 2017       31 / 34
Závěrečný přehled
	1/1/	N	M	n	P
v Čtyřstěn	4	6	4	3	3
Krychle	6	12	8	4	3
Osmistěn	8	12	6	3	4
Dvanáctistěn	12	30	20	5	3
Dvacetistěn	20	30	12	3	5
Legenda: Počet stěn (l/l/), počet hran (A/), počet vrcholů (M), počet stran jedné stěny (r?), počet hran u vrcholu (p)
29. 11. 2017       32 / 34
Příklad 2
Nakreslete rovinnou reprezentaci pravidelného čtyřstěnu, krychle a osmistěnu. Poté ve všech rovinných grafech najděte hamiltonovskou kružnici.
29. 11. 2017       33 / 34
Nakreslete rovinnou reprezentaci pravidelného čtyřstěnu, krychle a osmistěnu. Poté ve všech rovinných grafech najděte hamiltonovskou kružnici.
Řešení:
Hamiltonovskou kružnici není těžké nakreslit ani u jednoho z grafů.
Použité zdroje
✓ _
□ MILKOVA, Eva. Teorie grafů a grafové algoritmy. 1. vyd. Hradec Králové: Nakladatelství Gaudeamus, 2013. 123 s. ISBN 978-80-7435-267-6.
B FUCHS, Eduard. Diskrétni matematika pro učitele. 1. vyd. Brno: Masarykova univerzita, 2001. 178 s. ISBN 80-210-2703-7.
B SISMA, Pavel. Teorie grafů 1736-1963. 1. vyd. Praha: Přírodovědecká fakulta Masarykovy univerzity v Brně, 1997. ISBN 80-7196-065-9.
29. 11. 2017       34 / 34