Souvislost grafu

  • Graf je souvislý, jestliže v něm pro každé jeho 2 vrcholy existuje --cesta
  • Jinak je nesouvislý
Pozorování

Graf je souvislý právě tehdy, když obsahuje právě 1 souvislou komponentu

  • Nemůže existovat nesouvislý graf, jehož doplněk by byl takové nesouvislý (tj. doplněk musí být souvislý)

Souvislé komponenty grafu

  • Indukovaný podgraf grafu je souvislou komponentou, pokud:
    • je souvislý a zároveň
    • neexistuje žádný souvislý podgraf , grafu takový, že

../Attachments/02-souvisle-komponenty.png

Binární relace

  • Značíme
  • --cesta v

Algoritmy pro vyšetřování souvislosti

  • Lze využít BFS
    • Když doběhne, uzavře všechny vrcholy, do kterých existuje cesta ze startu
    • Lze najít souvislou komponentu ve které leží
    • Pokud uzavře všechny vrcholy, je celý graf souvislý

Slabá souvislost orientovaného grafu

Souvisí s 01 Orientovaný graf

  • Je slabě souvislý, pokud je souvislá jeho symetrizace

Silná souvislost

  • Je silně souvislý, pokud pro každé vrcholy existuje orientovaná cesta tam i nazpátek (nemusí být přímo jen délky 1)

Vytvořeno: 7. 8. 2024, 13:25
Poslední aktualizace: 7. 8. 2024, 13:25