Forbindelseskomponent af en graf
En forbundet grafkomponent (eller blot en grafkomponent ) er en maksimal (ved inklusion) forbundet undergraf af en graf .
Med andre ord er det en undergraf genereret af et sæt af hjørner, hvor der for ethvert par af hjørner i grafen er en -kæde, og for et hvilket som helst par af knudepunkter er der ingen -kæde .
For rettede grafer er begrebet en stærkt forbundet komponent defineret .
Algoritme
Breadth-First Search eller Depth -First Search kan bruges til at udtrække forbindelseskomponenter . I dette tilfælde vil tidsforbruget være lineært i summen af antallet af hjørner og antallet af kanter på grafen.
Se også
- Forbundet graf
- Fuldstændig afbrudt graf
- Ordliste over grafteoretiske termer
- En stærkt forbundet komponent i en digraf
- Perkolation teori