Společně s Cvičením 5a.

Obecná náplň cvičení

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ů).
• 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.

Druhá část cvičení se pak soustředí jen 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á >1 vrchol. Počet hran stromu je n-1.
• Strom coby minimální souvislý (pod)graf na daných vrcholech. Kostry grafu, volitelně lze ukázat něco o počtech koster některých grafů, ale to je nad náplň předmětu.