Úvod do teorie grafů
Teorie grafů je obor diskrétní matematiky, který zkoumá vlastnosti takzvaných grafů. Graf je
matematická struktura, definovaná množinou vrcholů a množinou hran, kde každá hrana je určena
povinně dvěma vrcholy a volitelně směrem nebo váhou; váha může odrážet např. délku, náklady
na přesun nebo průchodnost. Graf si lze dobře představit jako mapu, na které vrcholy představují
města a hrany představují dálnice, přičemž každá z těchto dálnic přímo spojuje dvě města.
Problém 1: Sedm mostů města Královce
Sedm mostů města Královce (též Königsberg, nyní Kaliningrad) je slavný, již
vyřešený matematický problém. Otázka zní, zda je možné všechny mosty přejít tak, aby ten, kdo se
o to pokouší, vstoupil na každý most pouze jednou. Zdůvodněte svou odpověď.
Video:
Problém 2: Eulerovské grafy (jednotažky)
Video: Úvod do teorie grafů https://www.youtube.com/watch?v=8EGOLgZR5gs
Problém 3: Eulerovské grafy (jednotažky)
Rozhodněte, zda lze obrázky nakreslit jedním tahem (otevřeným, uzavřeným). Poté tah navrhněte.
Problém 4: Silničáři (Hledání minimální kostry)
Napadne sníh a silničáři musí pluhem prohrabat cesty a tím propojit spojení mezi 12 městy
(12 vrcholů grafu). Chtějí, aby práce byla hotova co nejdříve, tzn. pluhař odhrabal co nejkratší úsek.
Pokud pluhař pojede po nějaké cestě podruhé, už se její délka nepočítá, neboť cesta zůstala
odhrabaná a pluh pouze projíždí bez námahy. Na obrázku je u každé cesty zapsaná její délka
v kilometrech. Co musí silničáři minimálně prohrabat?
Pozn.: Je nutné zvýraznit
v obrázku takovou variantu,
aby byl počet prohrabaných
kilometrů co nejkratší, a
přesto se obyvatelé
kteréhokoliv města mohli
dostat do ostatních měst.
Zdroje:
Sedm mostů města Královce
https://cs.wikipedia.org/wiki/Sedm_most%C5%AF_m%C4%9Bsta_Kr%C3%A1lovce
Eulerovské grafy (jednotažky)
https://teorie-grafu.cz/vybrane-problemy/jednotazky.php
Klasické úlohy teorie grafů na školách
http://home.pf.jcu.cz/~sbml/wp-content/uploads/Voracova.pdf
Videa:
Euler, grafy a 7 mostů kdesi v Rusku
https://www.youtube.com/watch?v=cZdlDgDhm70&list=PLbRLrrkYHYe6JUKa4yCY3ys1vCmtNuSUf
Řešení bludišť za využití teorie grafů
https://www.youtube.com/watch?v=Dcpmd5ae1kc
Úvod do teorie grafů
https://www.youtube.com/watch?v=8EGOLgZR5gs
Řešení:
Problém 1: Sedm mostů města Královce:
Leonhard Euler jako první dokázal, že to možné není, odpovídající graf totiž nelze projít pomocí
tzv. eulerovského tahu. Pouze eulerovské grafy mají tu vlastnost, že je možné je „nakreslit jedním
tahem“. Pokud tedy sedm mostů města Královce eulerovský graf netvoří, dokazuje to, že mosty není
možné tímto způsobem přejít.
Věta: Graf je možno nakreslit jedním tahem právě tehdy, když je souvislý a všechny vrcholy jsou
sudého stupně (vychází z nich sudý počet hran), nebo má právě dva vrcholy lichého stupně.
- Jsou-li v grafu dva vrcholy lichého stupně, potom tah začíná v jednom z těchto stupňů a končí
ve druhém.
Problém 2: Jednotažky - Brloh
Problém 3: Jednotažky
První nelze jedním tahem (více jak dva vrcholy s lichým počtem
hran). Druhý lze jedním uzavřeným tahem (všechny vrcholy
sudého stupně, lze začít v libovolném vrcholu a skončit v něm).
Třetí graf má dva vrcholy lichého stupně, lze zkonstruovat
otevřen tah (začneme v jednom vrcholu lichého stupně a
skončíme v druhém).
Problém 4: Silničáři (Hledání minimální kostry)
1) Seřaďme cesty (= hrany grafu) podle jejich délky od nejkratší po nejdelší
2) Zkoumejme postupně jednotlivé cesty, nejdříve 1 km dlouhou, potom 2 km dlouhou…
3) Pokud cesta spojuje města, která zatím nejsou nijak propojena (neexistuje mezi nimi žádná
cesta ani delší přes jiná města), zvýrazníme ji pastelkou (= přidáme ji na seznam pluhaře =
přidáme ji do našeho grafu), pokud však města již nějak propojena jsou (viz obr. 33), tuto
cestu nezvýrazníme a pluhař ji prohrabávat nebude.
4) Jestliže jste tímto způsobem prověřili všechny cesty, ověřte sami, že jsou opravdu všechna
města navzájem propojena a je možno se z jakéhokoliv dostat po vyhrabané cestě do
kteréhokoliv jiného.