Definujte souvislou komponentu neorientovaného grafu a popište alespoň jeden algoritmus pro hledání souvislých komponent.

Souvislost grafu

Graf G je souvislý pokud, jestliže pro každé libovolné dva vrcholy v grafu existuje u-v-sled.

→ jinak je G nesouvislý.

Souvislé komponenty grafu

• Indukovaný podgraf H grafu G je souvislá komponenta, pokud
  • je souvislý
  • neexistuje žadný podgraf L takový, že L ≠ G a H ⊆ F

→ Souvislá komponenta je tedy maximální souvislý podgraf grafu G

Z definic souvislého grafu a souvislé komponenty plyne:

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