Zapisování grafů

Grafy potřebujeme i zapisovat (nejen kreslit)

• Větší graf rádi necháme ke zpracování počítači, ten si ale s obrázkem moc dobře neporadí.
• Graf můžeme chtít někomu předat, ale ne vždy je to možné v podobě obrázku.

Grafové notace - způsob kódování grafu.

způsob kódování grafu.

Potřebujeme najít způsob, jak graf zakódovat pomocí dané množiny znaků (např. 0 a 1).
Je přitom celkem jedno, jak je graf nakreslený co do tvaru nebo velikosti.
Důležité je, které vrcholy jsou spojeny se kterými, grafy reprezentují strukturu vztahů.

Úloha: Popis domečku

Způsob popisu grafu, který jste právě poznali, se nazývá seznam hran. Ina první pohled těžko uchopitelnou strukturu bez začátku či konce, jako je graf, můžeme reprezentovat pomocí posloupnosti znaků. 

Matice sousednosti

Seznam hran může být jako kódování dost rozsáhlý. Zabere hodně místa, takže např. trvá dlouho ho odvysílat. Nešlo by vymyslet úspornější kódování (zápis grafu pomocí znaků, obvykle čísel). Nejlíp rovnou pomocí jedniček a nul, ať hned vidíme náročnost v bitech.

Úloha: Z grafu matice

Otevřete stránku Graph Online a doplňte do levé části jedničky a nuly tak, aby se po stisku tlačítka Plot graph zobrazil náš známý domeček.

řešení:

Úloha: Z matice graf

Dekódujte a nakreslete (rukou či na počítači) tento graf:
0110000   1010011  1101010  0010101  0001010  0110100  0101000
Porovnejte svoje řešení s dalšími. Jsou stejná? Čím se liší? Je některé chybně?

Graph Online  

Úloha: Skóre grafu

Další způsob popisu grafu se nazývá skóre. Je to posloupnost tzv. stupňů jednotlivých vrcholů.

Stupeň vrcholu je počet jeho hran (v orientovaném grafu proto rozlišujeme vstupní a výstupní stupeň, tedy počet hran vedoucích "dovnitř" a počet hran vedoucích "ven"). V pražském metru je stupeň Černého Mostu 1, Malostranské 2, Florence 4. Stupeň většiny křížení v pavoučích sítích je 4. Sjezd z dálnice má vstupní stupeň 1, výstupní 2. Stejně na tom jsou dotazy v rozhodovacím stromě (pokud umožňují právě dvě odpovědi).

Úkoly:

1. Napište skóre grafu z předchozího úkolu (domeček, bez vrcholu uprostřed, prostředek berte jako křížení hran).
2. Nakreslete jiný graf se stejným skóre. Je opravdu jiný? Nebo je jen "pokroucený a zpřeházený", ale vlastně stejný?
3. Skóre je navíc mnohem kratší než seznam hran! Bylo by tedy možné používat skóre jako úspornější způsob kódování grafu? Rozmyslete, jaké vlastnosti takové kódování musí mít, aby bylo použitelné, a prozkoumejte, jestli tyhle vlastnosti skóre splňuje. Vysvětlete a zdůvodněte svůj závěr. Jestli potřebujete, použijte různé ukázkové grafy apod.

Čím je určen graf?
Pamatuj si: Graf je jednoznačně určen svými vrcholy a jejich propojením hranami.

Další informace?

Graf je definován svými vrcholy a hranami mezi nimi. Někdy ale situace vyžaduje pracovat s dalšími podrobnostmi. Např. v úloze s výletem na kopec bylo třeba počítat s délkami jednotlivých úseků. Za tím účelem ke grafům přidáváme tzv. ohodnocení hran či vrcholů. Zpravidla je to číslo, které se váže k dané hraně či vrcholu. Může jít o délky cest, propustnosti datových linek, dlužné částky mezi zeměmi, doby trvání úkolů a mnoho dalšího. Nemusí jít ale jen o čísla, často máme např. pojmenované vrcholy. V případě rozhodovacích stromů mají některé vrcholy přiřazenu otázku, hrany mají směr a odpověď. S ohodnocenými grafy můžeme řešit ještě mnohem širší škálu problémů.

Pracujeme-li se zakódovanými grafy, často se přirozené místo pro ohodnocení přímo nabízí. V seznamu hran můžeme ohodnocení hran připojit přímo ke dvojici vrcholů, která tu kterou hranu určuje. V matici pak můžeme na místo 0 a 1 psát přímo dané ohodnocení (a nějakou speciální hodnotou vyjádřit, pokud daná hrana vůbec neexistuje). V každém případě si také můžeme vytvořit vedle ještě jeden seznam a do něj zaznamenat ohodnocení jednotlivých vrcholů či hran.

Pracujeme-li s grafy nakreslenými, píšeme ohodnocení zpravidla přímo k dané hraně či vrcholu.

Závěr

Graf je přehledný a praktický, pokud potřebujeme pracovat se vztahy. Na druhou stranu, když je graf velký, je potíž jej zakreslit a dále zpracovávat ručně. V takové situaci (a takových situací je většina) graf vhodně zakódujeme a k jeho zpracování využijeme počítač. Jednoznačný způsob zakódování nám mimo jiné umožní zpracovávat grafy automatizovaně. Popsat, jak spočítat např. počet vrcholů a hran daného grafu, je jednodušší, pokud máme v rukou (či v souboru) seznam hran či matici sousednosti, než obrázek.