Komponenta grafu

Komponenta grafu (Komponenta souvislosti) je maximální souvislý podgraf, tj. v tomto podgrafu najdeme cestu z vrcholu ${\displaystyle a}$ do vrcholu ${\displaystyle b}$ pro jakékoliv vrcholy ${\displaystyle 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říklad algoritmus prohledávání do hloubky.^[1]

• Silně souvislá komponenta
• Souvislý graf

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.