Základní pojmy z teorie grafů

graf, rozdělení a typy grafů, vážený graf, podgraf, cesta, kružnice, strom, kostra grafu, různé reprezentace grafu a jejich výhody a nevýhody

Definice grafu

Graf je množina objektů, mezi kterými existuje určitá vazba, která tyto objekty spojuje.

  • Tato množina objektů je uspořádaná trojice (U,H,F), kde U je množina uzlů, H je množina hran a f: H -> U2

Vlastnosti grafu

  • Neorientovaný graf: V základu je každý graf orientovaný, jestliže hrany jsou uspořádané dvojice. Hrany neuspořádaného grafu jsou dvouprvkové množiny. Hrany orientovaného grafu mají tedy pevně danou orientaci. Pokud máme orientovaný graf, lze k němu sestrojit graf neorientovaný tím, že z orientovaného grafu odstraníme informaci o směru hran.
  • Prostý graf: Prostý graf je takový graf, jenž neobsahuje žádnou rovnoběžnou hranu.
    • graf obsahuje rovnoběžnou hranu, pokud existují dvě hrany, které propojují dva totožné uzly
  • Prázdný a nekonečný graf: Prázdná a nekonečné množina uzlů U.
  • Diskrétní a úplný graf: Diskrétní graf je takový graf, v němž žádné dva uzly nejsou spojené hranou. Úplný graf je takový neorientovaný graf v němž jsou každé dva různé uzly spojené hranou.
  • Biparitní graf: Takový graf, jehož množinu uzlů je možné rozdělit na dvě disjunktní (naprosto odlišné) množiny tak, že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou.
  • Regulární graf: Takový graf, jehož všechny uzly mají stejný stupeň. Stupeň uzlu je hodnota, označující počet hran tohoto uzlu.
  • Podgraf: Část grafu, pokud obsahuje všechny uzly jedná se o faktor.
  • Sled: Posloupnost hran, které na sebe navazují, se nazývá sled. Pokud se žádná hrana neopakuje, jedná se o tah. Tah, ve kterém se neopakuje žádný vrchol se nazývá cesta.
  • Kružnice a cyklus: ­ Uzavřená cesta v neorientovaném a orientovaném grafu
  • Souvislý graf: Mezi každými dvěma uzly existuje sled. Každý maximální souvislý podgraf je komponenta
  • Uzlové a hranové řezy: množina uzlů / hran jejichž odstraněním se zvýší počet komponent Uzlový řez s jedním uzlem je artikulace (Množina obsahuje jeden uzel, jehož odstraněním vytvoříme jednu či více komponent). Hranový řez s jednou hranou je most (Množina obsahuje jednu hranu, kterou když odstraníme, vytvoříme jednu či více komponent).
  • Komponenta : Samostatná část grafu, která není spojená s dalšími částmi grafu.
  • Klika a nezávislá množina: Klika je úplný podgraf, nezávislá množina je diskrétní podgraf.

Charakteristiky uzlů

  • Uzly: následníci, předchůdci, sousedi uzlu
    • Následníci a předchůdci : Lze určit u stromu.
    • Sousedi uzlu: Uzly, jež jsou spojeny s uzlem skrze hrany, se nazývají sousedi.
  • Hrany: výstupní okolí, vstupní okolí, okolí uzlu
    • Výstupní okolí : Hrany, jež vystupují z uzlu
    • Vstupní okolí : Hrany jež vstupují do uzlu
    • Okolí uzlu : Množina hran, jež vstupuje/vystupuje z uzlu. U neorientovaného grafu můžeme určit pouze okolí uzlu.
  • Stupně: výstupní stupeň, vstupní stupeň, stupeň uzlu
    • Výstupní stupeň : Počet výstupních hran směřujících od uzlu
    • Vstupní stupeň : Počet vstupních hran směřujících do uzlu
    • Stupeň uzlu : Počet hran patřících k uzlu. U neorientovaného grafu lze uzlu určit pouze tento stupeň (Chybí informace o směru hran).

Ohodnocené grafy

Uzlové ohodnocení grafu

Zobrazení \(k: U > R\), nazývá se klíč a dá se využít při řazení, vyhledávání či kódování.

Hranové ohodnocení grafu

Zobrazení \(d: H > R\), každá hrana má k sobě přiřazenou hodnotu (váhu).

Strom

Jedná se o souvislý graf, který neobsahuje žádnou kružnici. Základem stromu je uzel, pojmenovaný kořen (root). Bezprostředně následující uzel ve směru z kořene do uzlu se nazývá „dítě“ nebo „syn“ uzlu (anglicky child); uzel bezprostředně předcházející je „rodič“ uzlu (anglicky parent). Kořen stromu nemá rodiče a list stromu nemá žádné syny. Ostatní uzly mohou mít libovolný počet synů.

Kostra grafu

Kostrou grafu budeme rozumět libovolný podgraf, který hranami spojuje všechny vrcholy původního grafu a zároveň sám neobsahuje žádnou kružnici (→ jde o strom).

Minimální kostra

Úloha hledání minimální kostry nám popisuje, jak máme spojit všechny vrcholy grafu "co nejlevněji" - hranami s nejnižší váhou (ohodnocením). Praktickým využitím mohou být například rozvody elektřiny mezi městy - jak propojit města co nejmenší délkou elektrického vedení.

Hledání minimální kostry

K tomuto účelu se používají algoritmy pro hledání kostry grafu. Jedná se o tzv. hladové algoritmy. Velmi používaným algoritmem je Kruskalův algoritmus. Pracuje na principu spojování hran s nejmenším ohodnocením, dokud tyto hrany nespojí vrcholy celého grafu.

Popis Kruskalova algoritmu

  • Všechny hrany si seřadíme podle velikosti (vzestupně - od hrany s nejmenší váhou).
  • Hranu s nejmenší váhou použijeme jako první hranu kostry.
  • Pokud jsme tím už vytvořili kostru (graf měl jen dva vrcholy), končíme. V opačném případě vezmeme hranu s druhou nejmenší váhou. POZOR! Pokud by nám v grafu vznikla kružnice, hranu nepoužijeme.
  • Opakujeme minulý krok, dokud vznikající kostra nespojí všechny vrcholy grafu.

Další algoritmy pro hledání minimální kostry

Borůvkův algoritmus

Funguje na principu skládání komponent. Na začátku jsou všechny uzly grafu považovány za samostatné komponenty. Algoritmus v každém svém kroku propojí každou komponentu s jinou komponentou pomocí nejkratší možné hrany. Jelikož Borůvkův algoritmus vyžaduje, aby měly všechny hrany unikátní váhu, tak při propojení komponent nikdy nemůže vzniknout cyklus.

Jarník-Primův algoritmus

Algoritmus vychází z libovolného uzlu a udržuje si seznam již objevených uzlů a jejich vzdáleností od propojené části grafu. V každém svém kroku připojí ten z uzlů, mezi nímž a propojenou částí grafu je hrana nejnižší délky a označí sousedy nově připojeného uzlu za objevené, případně zkrátí vzdálenosti od již známých uzlů, pokud byla nalezena výhodnější hrana. V okamžiku, kdy jsou propojeny všechny uzly, algoritmus terminuje.

Reprezentace grafů

Jedná se o způsob, kterým zobrazit graf.

Obrázkem

Grafická reprezentace grafu. (kolečkové uzly, čárky mezi nimi aneb hrany)

Výhody

  • Přehlednost pro lidské oko
  • Lze použít pro jakýkoliv typ grafu

Nevýhody

  • Pro zpracování za pomocí programu je nutné graf reprezentovat jinak
  • Velké grafy se stávají nepřehledné

Matice sousednosti

Zápis grafu pomocí matice.

  • Postup vytváření matice sousednosti
    • Nejprve si všechny vrcholy očíslujeme.
    • Za rozměr matice musíme zvolit počet vrcholů. Kdybychom měli například graf se 4 vrcholy ale matici rozměrů jen 3×3, nemohli bychom zapsat hrany vedoucí do/z čtvrtého vrcholu.
    • Pokud vede mezi dvěma vrcholy hrana, zapíšeme do matice na pozici [číslo jednoho vrcholu, číslo druhého vrcholu] a na pozici [číslo druhého vrcholu, číslo prvního vrcholu] číslo 1. Jinak zapíšeme 0.

Výhody

  • Maticová reprezentace je vhodná pro programové zpracování
  • Lze použít pro orientovaný graf i neorientovaný graf (pro neorientovaný graf je matice symetrická, protože hodnota prvku na souřadnicích např. (1,2) je stejná jako hodnota prvku na pozici (2,1))

Nevýhody

  • Pro lidské oko nepřehledné

Existují i další druhy zápisů pomocí matice

  • Matice incidence : Řádky jsou uzly sloupce jsou hrany. V poli se nachází 1, pokud se jedná o výstupní hranu uzlu. 0 pokud hrana nepatří do okolí uzlu a 1 pokud se jedná o vstupní hranu uzlu.
  • Matice vzdáleností : Řádky i sloupce jsou uzly. Do pole se zapisuje vzdálenost mezi jednotlivými uzly. Získává se pomocí výpočtu minimální vzdálenosti mezi jednotlivými uzly.
  • Matice dostupnosti: Řádky i sloupce jsou uzly. V poli je 1, pokud existuje orientovaná cesta z uzlu A (sloupec) do uzlu B (řádek). Nelze použít pro neorientované grafy.

Seznam vrcholů se seznamem hran

Jedná se o seznam vrcholů (1,2,3) a seznam hran, jež jsou mezi těmito vrcholy. (1-2,1-3,2-3)

Výhody

  • přehledný, pokud máme hodně vrcholů, jež jsou spojeny malým počtem hran

Nevýhody

  • Při velkém počtu vrcholů se reprezentace stává nepřehlednou
  • lze použít pouze pro neorientovaný graf

Citace