Komponenta grafu

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Nesouvislý graf, který má tři komponenty.

Komponenta grafu (Komponenta souvislosti) je maximální souvislý podgraf, t.j. v tomto podgrafu najdeme cestu z vrcholu a do vrcholu b pro jakékoliv vrcholy a, b v podgrafu.

Jsou to všechny indukované podgrafy na jednotlivých třídách ekvivalence souvislosti. Je to souvislý podgraf, který není obsažen v žádném větším souvislém podgrafu. Souvislý graf má právě jednu komponentu.

Z algoritmického hlediska je určení komponent a testování souvislosti grafu snadným problémem. K oběma problémům lze použít např. Dijkstrův algoritmus.

Související články[editovat | editovat zdroj]