Společně s Cvičením 5a. Převážná část cvičení navazuje jen na Lekci 7, avšak závěr zabývající se vzdáleností v grafech je podle Lekce 8 (takže ten odsunout na cvičení 6a, pokud ještě Lekce 8 nebyla probrána - v takovém případě se bude odsunovat také 6b na 7, neboli čas v příštím cvičení bude).

Rámcová náplň cvičení

Definice grafů

Na látku využívající grafické zobrazení binárních relací a funkcí přímo navazuje abstraktní pojem grafu, který vlastně není ničím jiným než binární ireflexivní symetrickou relací, ale na druhou stranu nabízí mnohem širší možnosti použití.

• Formální definice grafu, její vztah k názornému nakreslení obrázkem a k běžným způsobům reprezentace grafu v počítači (maticí sousednosti nebo seznamy sousedů). Rozdíl mezi jednoduchým grafem a multigrafem.
• Pojmy hran, stupňů vrcholů, kružnic a cest, podgrafů a podobně. Vše k procvičení především na názorných obrázcích. Triviální důkaz toho, že součet stupňů je sudý.
• Isomorfismus grafů, jeho poznání a taky zdůvodnění neisomorfismu v různých příkladech. Při zdůvodňování různosti grafů je potřeba pochopit, že na to není "univerzální recept", ale řešení se hledají ad hoc podle aktuální situace - třeba nesouhlasící stupně, nesouhlasící jednoduché podgrafy, atd.

A pamatujme, pro správné pochopení a zvládnutí grafů je třeba si kreslit a kreslit a kreslit obrázky grafů...

Stromy

Druhá část se pak (stručně) soustředí na jeden speciální druh grafů - stromy.

• Definice jako souvislý graf bez kružnic. Běžné vlastnosti, převážně odvozené ze základního faktu, že strom obsahuje vrchol stupně 1, pokud má více než vrchol. Počet hran stromu na n vrcholech je n-1.
• Strom coby minimální souvislý (pod)graf na daných vrcholech. Les coby graf bez kružnic.

Vzdálenost v grafech

Bude probrána především základní grafová vzdálenost (počtem hran cesty) a ukázáno zobecnění na ohodnocenou vzdálenost, kdy "délky hran" jsou obecně různé od 1.

Možné příklady k procvičení základů grafů

• Zakreslete si "malé" kružnice, cesty, úplné grafy. Pro které parametry m,n je úplný bipartitní graf na m,n vrcholech zároveň cestou nebo kružnicí nebo stromem?
• Proč má každý jednoduchý graf alespoň dva vrcholy stejného stupně?
• Libovolná ukázka souvislého a nesouvislého grafu obrázkem...
• Určete stupně vrcholů a nalezněte všechny trojúhelníky v následujících grafech:
             
  Není lepší si některé z těchto grafů nejprve "překreslit" a pak teprve hledat trojúhelníky?

• Nalezněte všechny podgrafy isomorfní kružnici délky 4 ("čtyřúhelníky") v následujících grafech:
             

• Nakreslete jednoduchý graf na 5 vrcholech s největším možným počtem hran takový, že neobsahuje trojúhelník.

Možné příklady k procvičení isomorfismu

• Vyhledejte isomorfní dvojice v následujících čtveřicích grafů daných svými obrázky a zdůvodňujte, proč zbylé dvojice isomorfní nejsou. (Hledejte také "hezčí" obrázky uvedených grafů...)
  •          
  •         
  •         
• Rozhodněte, zda existují dva neisomorfní jednoduché grafy na 5 vrcholech se všemi stupni 2. Uvažujte stejnou otázku pro multigrafy na 5 vrcholech a pro jednoduché grafy na 6 vrcholech.

Možné příklady k procvičení stromů

• Zakreslete všechny neisomorfní stromy na 4 a 5 vrcholech.
• Kolik komponent souvislosti má les o 22 vrcholech a 17 hranách? A podobně...

Možné příklady k procvičení vzdálenosti

• Určete vzdálenost mezi konkrétními dvěma vrcholy ve vybraném grafu z obrázků výše. Řešte i příklady, kdy odpověď není "na první pohled jasná".
• Určete poloměr a průměr ve vybraném grafu z obrázků výše. Kolik vrcholů obsahuje centrum tohoto grafu a kolik dvojic vrcholů má vzdálenost rovnou průměru grafu?

• Určete ohodnocenou vzdálenost z A do B v každém z následujících grafů:
  

Procházení grafu, algoritmy - jen volitelné

Tato část cvičení je volitelná pro případ, že náhodou zbývá volný čas... (jinak přeskočit a jít rovnou na 6a!)

Rozebrání způsobů procházení grafu, ruční ukázky běhů algoritmů.

• Tuto část není až tak nutno probírat na cvičeních, neboť průběh algoritmů vázajících se k procházení grafu byl důkladně vysvětlen na přednášce a stejně bude znovu probírán na jiných předmětech o návrhu algoritmů.
• Pokud je přesto volný čas, lze například dokazovat, že obecné schéma procházení grafu probere všechny vrcholy a hrany souvislé komponenty. Také je možno probrat důkazy korektnost Dijkstrova a Jarníkova algoritmu.