Komponent (grafteori) - Component (graph theory)

En graf med tre komponenter.

I grafteori er en komponent i en ikke-rettet graf en indusert undergraf der to hjørner er koblet til hverandre med baner , og som ikke er koblet til noen ekstra hjørner i resten av grafen. For eksempel har grafen vist i illustrasjonen tre komponenter. Et toppunkt uten innfallende kanter er i seg selv en komponent. En graf som i seg selv er koblet til har nøyaktig en komponent, som består av hele grafen. Komponenter kalles også noen ganger tilkoblede komponenter .

En ekvivalensforhold

En alternativ måte å definere komponenter involverer ekvivalensklassene til en ekvivalensrelasjon som er definert på hjørnene i grafen. I en rettet grafe, et toppunkt v er tilgjengelig fra et topp-punkt u hvis det er en bane fra u til v . I denne definisjonen telles et enkelt toppunkt som en sti med lengde null, og det samme toppunktet kan forekomme mer enn en gang i en bane. Nåbarhet er et ekvivalensforhold , siden:

• Det er refleksivt : Det er en triviell bane med lengde null fra ethvert toppunkt til seg selv.
• Det er symmetrisk : Hvis det er en bane fra u til v , danner de samme kantene en bane fra v til u .
• Det er transitivt : Hvis det er en sti fra u til v og en sti fra v til w , kan de to stiene sammenkobles for å danne en sti fra u til w .

Komponentene er da de induserte subgrafene dannet av ekvivalensklassene i denne relasjonen.

Antall komponenter

Antall komponenter er en viktig topologisk invariant i en graf. I topologisk grafteori kan det tolkes som null- Betti-tallet i grafen. I algebraisk grafteori er det lik multiplikasjonen 0 som en egenverdi av den laplaciske matrisen til grafen. Det er også indeksen for den første ikke-nul-koeffisienten til det kromatiske polynomet i en graf. Antall komponenter spiller en nøkkelrolle i Tutte-setningen som karakteriserer grafer som har perfekt samsvar , og i definisjonen av grafens seighet .

Algoritmer

Det er greit å beregne komponentene i en graf i lineær tid (når det gjelder antall hjørner og kantene på grafen) ved hjelp av enten bredde-første søk eller dybde-første søk . I begge tilfeller vil et søk som begynner på et bestemt toppunkt v finne hele komponenten som inneholder v (og ikke mer) før den returneres. For å finne alle komponentene i en graf, gå gjennom hjørnene, start en ny bredde først eller dybde første søk når løkken når et toppunkt som ikke allerede er inkludert i en tidligere funnet komponent. Hopcroft & Tarjan (1973) beskriver i hovedsak denne algoritmen, og sier at den på det tidspunktet var "velkjent".

Det er også effektive algoritmer for dynamisk å spore komponentene i en graf når hjørner og kanter legges til, som en enkel anvendelse av usammenhengende datastrukturer . Disse algoritmene krever amortisert O ( α ( n )) tid per operasjon, der å legge til hjørner og kanter og bestemme komponenten der et toppunkt faller, begge operasjoner, og α ( n ) er en veldig sakte voksende Ackermann-funksjon . Et beslektet problem er å spore komponenter ettersom alle kanter blir slettet fra en graf, en etter en; en algoritme eksisterer for å løse dette med konstant tid per spørring, og O (| V || E |) tid for å opprettholde datastrukturen; Dette er en amortisert kostnad på O (| V |) per kantsletting. For skog kan kostnadene reduseres til O ( q + | V | log | V |) , eller O (log | V |) amortisert kostnad per kant-sletting ( Shiloach & Even 1981 ).

Forskere har også studert algoritmer for å finne komponenter i mer begrensede beregningsmodeller, for eksempel programmer der arbeidsminnet er begrenset til et logaritmisk antall bits (definert av kompleksitetsklasse L ). Lewis & Papadimitriou (1982) spurte om det er mulig å teste i logspace om to hjørner hører til den samme komponenten i en ikke-rettet graf, og definerte en kompleksitetsklasse SL for problemer logspace-ekvivalent med tilkobling. Endelig lyktes Reingold (2008) i å finne en algoritme for å løse dette tilkoblingsproblemet i logaritmisk rom, og viste at L = SL .

Komponenter i tilfeldige grafer

I tilfeldige grafer er størrelsen på komponentene gitt av en tilfeldig variabel, som igjen avhenger av den spesifikke modellen.

Den modellen har tre regioner med tilsynelatende forskjellig oppførsel: ${\ displaystyle G (n, p)}$

Subkritisk ${\ displaystyle np <1}$

Alle komponentene er enkle og veldig små, den største komponenten har størrelse ;${\ displaystyle | C_ {1} | = O (\ log n)}$

Kritisk ${\ displaystyle np = 1}$

${\ displaystyle | C_ {1} | = O (n ^ {2/3})}$;

Superkritisk ${\ displaystyle np> 1}$

${\ displaystyle | C_ {1} | \ approx yn}$hvor er den positive løsningen på ligningen${\ displaystyle y = y (np)}$${\ displaystyle e ^ {- pny} = 1-y.}$

hvor og er henholdsvis de største og nest største komponentene. Alle andre komponenter har størrelsen på bestillingen${\ displaystyle C_ {1}}$${\ displaystyle C_ {2}}$${\ displaystyle O (\ log n).}$

Se også

• Kjempekomponent
• Sterkt tilkoblet komponent , et beslektet konsept for dirigerte grafer
• Biconnected komponent
• Modulær spaltning for riktig generalisering av komponenter på ikke-rettet grafer
• Merking av koblet komponent , en grunnleggende teknikk i dataanalyseanalyse basert på grafikkomponenter
• Perkolasjonsteori , en teori som beskriver oppførselen til komponenter i tilfeldige underbilder av rutenettgrafer
• Sentralitet
• Bridge (grafteori)

Referanser

• Hopcroft, J .; Tarjan, R. (1973), "Algoritme 447: effektive algoritmer for grafmanipulering ", Kommunikasjon av ACM , 16 (6): 372–378, doi : 10.1145 / 362248.362272
• Lewis, Harry R .; Papadimitriou, Christos H. (1982), "Symmetric space-bounded computation", Theoretical Computer Science , 19 (2): 161–187, doi : 10.1016 / 0304-3975 (82) 90058-5
• Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM , 55 (4): Article 17, 24 sider, doi : 10.1145 / 1391289.1391291
• Shiloach, Yossi; Even, Shimon (1981), "An on-line edge-deletion problem", Journal of the ACM , 28 (1): 1–4, doi : 10.1145 / 322234.322235

Eksterne linker

• MATLAB-kode for å finne komponenter i ustyrte grafer , MATLAB File Exchange.
• Tilkoblede komponenter , Steven Skiena, The Stony Brook Algorithm Repository