Afstandsarvet graf

I grafteori er en afstandsarvet graf (eller fuldstændig adskillelig graf ) [1] en graf, hvor afstandene i enhver forbundet genereret subgraf er de samme som i den originale graf. Enhver genereret undergraf arver således afstandene fra den større graf.

Afstandsarvede grafer blev navngivet og først studeret af Howorka [2] , selvom det for en tilsvarende klasse af grafer allerede blev vist i 1970 af Olaru og Sachs, at klassen indeholder perfekte grafer [3] .

Det har været kendt i nogen tid, at afstandsnedarvede grafer udgør klassen af skæringsgrafer [4] , men skæringsmodellen var ikke kendt, før den blev givet af Gioan og Paul ( Gioan, Paul 2012 ).

Definition og beskrivelse

Den oprindelige definition af en afstandsarvet graf er en graf G sådan , at hvis to spidser u og v tilhører en forbundet genereret undergraf H af G , så skal en eller anden korteste vej, der forbinder u og v i G , være i undergrafen H , så afstanden mellem u og v i H vil være den samme som i G .

Afstandsarvede grafer kan beskrives på flere andre tilsvarende måder: [5]

Disse er grafer, hvor enhver genereret vej er den korteste.
Disse er grafer, hvor enhver cyklus med længde på mindst fem har to eller flere diagonaler, og hvor enhver cyklus med længde nøjagtig fem har mindst ét par krydsende diagonaler.
Disse er grafer, hvor enhver cyklus af længde fem eller mere har mindst ét par krydsende diagonaler.
Disse er grafer, hvor for alle fire hjørner u , v , w og x mindst to af de tre summer af afstande d ( u , v )+ d ( w , x ), d ( u , w )+ d ( v , x ) og d ( u , x ) + d ( v , w ) er ens.
Dette er grafer, der ikke har isometriske undergrafer af nogen cyklus af længde fem eller mere, eller nogen af de andre tre grafer: en 5-cyklus med en akkord, en 5-cyklus med to usammenhængende akkorder og en 6-cyklus med en akkord forbinder modsatte hjørner.

Disse er grafer, der kan oprettes fra et enkelt toppunkt ved hjælp af en sekvens af tre operationer (vist i illustrationen):
1. Tilføjelse af et nyt dinglende toppunkt forbundet med en enkelt kant til et eksisterende grafvertex.
2. Udskiftning af ethvert toppunkt i grafen med et par toppunkter, som hver har de samme naboer som det fjernede toppunkt. Det nye par knudepunkter kaldes tvillinger .
3. Udskiftning af et hvilket som helst toppunkt i grafen med et par toppunkter, som hver har de samme naboer som det fjernede toppunkt, inklusive et andet toppunkt fra parret. Det nye par knudepunkter kaldes tvillinger .
Det er grafer, der fuldstændigt kan dekomponeres i kliker og stjerner ( komplette todelte grafer K 1, q ) ved hjælp af splittende dekomponering . Ved en sådan opdeling opnås dekomponeringer af grafen i to delmængder, således at opdelingskanterne, der danner en komplet todelt undergraf , danner to mindre grafer ved at erstatte hver side af den todelte graf med hjørner med en rekursiv opdeling af disse to undergrafer [6 ] .
Det er grafer, der har enhedsrangbredde, hvor grafens rangeringsbredde er bestemt af mindst den maksimale rangorden over alle hierarkiske opdelinger af hjørner blandt visse submatricer af grafens tilstødende matrix , defineret ved division [7] .

Forholdet til andre familier af grafer

Enhver afstandsarvet graf er perfekt [2] , mere præcist en fuldstændig bestillingsbar graf [8] . Enhver afstandsarvet graf er også en lige graf , en graf, hvor to vilkårlige stier mellem det samme par af hjørner samtidig er enten lige eller ulige i længden [9] . Enhver lige grad af en afstandsnedarvet graf G (det vil sige en graf G 2 i dannet ved at forbinde par af hjørner i en afstand, der ikke overstiger 2 i i G ) er en akkordgraf [10] .

Enhver afstandsarvet graf kan repræsenteres som en graf over skæringspunkter mellem akkorder i en cirkel, det vil sige som en cirkelgraf . Dette kan vises ved at konstruere en graf ved at tilføje dinglende spidser, "tvillinger" og "tvillinger", hvilket ved hvert trin danner et sæt akkorder, der repræsenterer grafen. Tilføjelse af et dinglende toppunkt svarer til at tilføje en akkord nær slutningen af en eksisterende akkord, så den nye akkord kun vil skære den akkord. Tilføjelse af en "tvilling" svarer til at erstatte en akkord med to parallelle akkorder, der skærer det samme sæt akkorder. Tilføjelse af en "tvilling" svarer til at erstatte en akkord med to næsten parallelle krydsende akkorder, der skærer det samme sæt af andre akkorder.

En afstandsnedarvet graf er todelt , hvis og kun hvis den ikke har trekanter . En todelt afstandsnedarvet graf kan bygges ud fra et enkelt toppunkt ved kun at tilføje dinglende hjørner og tvillinger, da enhver tvilling danner en trekant, og tilføjelse af et dinglende toppunkt og tvillinger bevarer todelthed.

Grafer, der kan bygges fra et enkelt toppunkt ved at tilføje dinglende hjørner og skabe "tvillinger" uden at skabe "tvillinger" er specielle tilfælde af ptolehemske grafer og inkluderer blokgrafer . Grafer, der kan skabes fra et enkelt vertex ved at skabe tvillinger og tvillinger, men uden at tilføje dinglende knudepunkter, er kografer , som dermed er afstandsarvede. Kografer er præcis den usammenhængende forening af afstandsarvede grafer med diameter 2. Et kvarter til ethvert hjørne af en afstandsarvet graf er en kograf. Den transitive lukning af en rettet graf dannet ved at vælge ethvert sæt kantorienteringer af ethvert træ er afstandsarvet. Det specielle tilfælde, hvor træet er orienteret væk fra et eller andet toppunkt, danner en underklasse af afstandsnedarvede grafer kendt som trivielt perfekte grafer , som også kaldes akkordkografer [11] .

Algoritmer

Afstandsarvede grafer kan genkendes og dekomponeres i en sekvens af hængende hjørner og fordoblingsoperationer i lineær tid [12] .

Da afstandsarvede grafer er perfekte, kan nogle optimeringsproblemer løses i polynomiel tid, selvom disse problemer er NP-svære for mere generelle grafklasser. Det er således muligt i polynomisk tid at finde den maksimale klike eller uafhængige mængde i en afstandsnedarvet graf eller finde dens optimale farve [13] . Fordi afstandsarvede grafer er cirkelgrafer, arver de polynomielle-tidsalgoritmer til cirkelgrafer. For eksempel kan man bestemme i polynomisk tid træbredden af enhver cirkelgraf, og derfor enhver afstandsnedarvet graf [14] [15] . Derudover overstiger klikbredden af enhver afstandsarvet graf ikke tre [16] . Som en konsekvens, ifølge Courcelles sætning , er der for mange problemer på disse grafer effektive algoritmer baseret på dynamisk programmering [17] [18] .

Nogle andre optimeringsproblemer på afstandsarvede grafer kan løses effektivt ved hjælp af algoritmer, der er specielt designet til sådanne grafer. Som de Atri og Moscarini [19] har vist , kan et minimalt forbundet dominerende sæt (eller tilsvarende et spændingstræ med det maksimalt mulige antal blade) findes i polynomiel tid på afstandsnedarvede grafer. Hamilton-grafen eller Hamilton-stien for enhver afstandsarvet graf kan findes i polynomisk tid [20] [21] .

Noter

↑ Hammer, Maffray, 1990 .
↑ 12 Howorka , 1977 .
↑ Olaru og Sachs viste α-perfektionen af grafer, hvor enhver cyklus af længde fem eller mere har et par krydsende diagonaler ( Sachs, 1970 , sætning 5). Ifølge Lovász ( Lovász 1972 ) er α-perfektion en ækvivalent form for definitionen af perfekte grafer.
↑ McKee, McMorris, 1999 .
↑ Howorka (1977 ); Bandelt, Mulder (1986 ); Hammer, Maffray (1990 ); Brandstädt, Le, Spinrad (1999 ), Sætning 10.1.1, s. 147.
↑ Gioan, Paul (2012 ). En tæt beslægtet nedbrydning bruges til visualisering af grafer af Epstein, Goodrich og Meng ( Eppstein, Goodrich, Meng (2006 )) og (for todelte afstandsarvede grafer) af Hui , Schaefer, Štefankovič (2004 )).
↑ Oum, 2005 .
↑ Brandstädt, Le, Spinrad, 1999 , s. 70–71, 82.
↑ Brandstädt, Le, Spinrad, 1999 , s. 45.
↑ Brandstädt, Le, Spinrad, 1999 , s. 164 Sætning 10.6.14.
↑ Cornelsen, Di Stefano, 2005 .
↑ Damiand, Habib, Paul (2001 ); Gioan, Paul (2012 ). Forud for dette var grænsen angivet af Hammer og Maffray (1990 ), men Damiand opdagede en fejl i ræsonnementet.
↑ Cogis og Thierry Cogis, Thierry (2005 ) præsenterede en simpel direkte algoritme til at finde maksimalt vægtede uafhængige sæt i afstandsarvede grafer baseret på nedbrydning af grafen i dinglende hjørner og dobbelte hjørner, idet Hammer og Maffray korrigerede et tidligere forsøg på en sådan algoritme. ( Hammer, Maffray). (1990 )). Fordi afstandsarvede grafer er velordnede, kan de farvelægges optimalt i lineær tid ved hjælp af LexBFS's perfekte bestillingsalgoritme og anvendelse af grådig farvelægning .
↑ Kloks, 1996 .
↑ Brandstädt, Le, Spinrad, 1999 , s. 170.
↑ Golumbic, Rotics, 2000 .
↑ Courcelle, Makowski, Rotics, 2000 .
↑ Espelage, Gurski, Wanke, 2001 .
↑ D'Atri, Moscarini, 1988 .
↑ Hsieh, Ho, Hsu, Ko, 2002 .
↑ Müller, Nicolai, 1993 .

Litteratur