Tæl uden tang

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. september 2021; verifikation kræver 1 redigering .

I grafteori er en graf uden kløer en graf, der ikke indeholder genererede undergrafer , der er isomorfe til K 1,3 ( kløer ).

En klo er en komplet todelt graf K 1,3 (det vil sige en stjerne med tre kanter, tre blade og et centralt toppunkt). En graf uden kløer er en graf, hvor ingen genereret undergraf er en klo, dvs. der er ikke fire hjørner A , B , C og O , således at O er forbundet med A , B og C , men toppunkter A , B og C er ikke forbundet indbyrdes. Det er også muligt at definere en klofri graf som en, hvor naboskabet til ethvert toppunkt danner den trekantfri grafs komplement .

Klofrie grafer blev oprindeligt undersøgt som en generalisering af linjegrafer og modtog yderligere stimulus, da tre nøglefakta om dem blev opdaget:

det faktum, at alle forbundne grafer uden kløer af lige rækkefølge har perfekte matchninger ;
opdagelse af en tidspolynomiel algoritme til at finde det maksimale uafhængige sæt i grafer uden kløer;
beskrivelse af perfekte grafer uden klør [1] . Hundredvis af artikler og adskillige anmeldelser er blevet afsat til grafer uden kløer [2] .

Eksempler

Linjegrafen L ( G ) af enhver graf G har ikke kløer. L ( G ) indeholder et toppunkt for hver bue i G og toppunkter er konjugeret i L ( G ), når de tilsvarende kanter deler et toppunkt i G. Linjegrafen L ( G ) kan ikke have kløer, for hvis hver af de tre kanter e 1 , e 2 og e 3 i G har et fælles toppunkt med den fjerde kant e 4 , så er der efter Dirichlet-princippet mindst 2 kanter fra e 1 , e 2 og e 3 har et fælles toppunkt. Linjegrafer kan beskrives med ni forbudte undergrafer [3] og kloen er den enkleste af disse ni grafer. Dette giver et motiv til at studere grafer uden kløer [1] .

De Bruijn- grafer (grafer, hvis toppunkter svarer til n -bit binære strenge for nogle n , og hvis buer svarer til ( n −1)-bit matches) har ikke kløer. En måde at vise dette på er at konstruere de Bruijn-grafen for n -bit strenge som de Bruijn-linjegrafen for ( n − 1)-bit strenge.
Komplementet af enhver trekantfri graf har ingen kløer [4] . Disse grafer inkluderer enhver komplet graf som et specialtilfælde.
Korrekte intervalgrafer er intervalgrafer dannet som grafer over skæringspunkter efter familier af intervaller, hvor intet interval indeholder et andet interval af familien; har ikke kløer, da fire sådanne intervaller ikke kan skære hinanden i et klømønster [4] .
Mosers spindel er en graf med syv hjørner, som bruges til at bevise, at den nedre grænse for planets kromatiske tal ikke har nogen kløer.
Graferne for nogle polyedre og polytoper har ikke kløer. Dette inkluderer grafen for et tetraeder og generelt enhver simpleks (komplet graf), grafen for et oktaeder og generelt enhver krydspolytop ( isomorf til cocktailpartygrafen , som opnås ved at fjerne en perfekt matchning fra en komplet graf), grafen for et regulært icosahedron [5] og et 16-cellet tal .
Schläfli-grafen , en meget regelmæssig graf med 27 hjørner, har ingen kløer [5] .

Anerkendelse

Man kan kontrollere direkte, at en given graf med n hjørner og m kanter ikke har nogen kløer i O( n 4 ) tid ved at kontrollere hver fjerde knudepunkt for at se, om de genererer en klo [6] . Noget mere effektivt, men sværere, kan man kontrollere, at en graf ikke har kløer, ved at kontrollere for hvert toppunkt på grafen, at komplementet til toppunktets nabograf ikke indeholder en trekant. En graf indeholder en trekant, hvis og kun hvis terningen af tilstødende matrix indeholder et ikke-nul diagonalt element, så søgningen efter en trekant kan udføres i samme asymptotiske tid som n × n matrix multiplikation [7] . Ved brug af Coppersmith-Winograd-algoritmen vil den samlede tid til at bestemme, om en graf har kløer, være O( n 3,376 ).

Kloks, Kratsch og Müller ( Kloks, Kratsch, Müller ) [8] gjorde opmærksom på, at i en graf uden kløer har hvert toppunkt et maksimum af naboer, ellers vil området til toppunktet ifølge Turan-sætningen ikke have nok kanter til at danne komplementet til grafen uden trekanter. Denne observation giver os mulighed for at kontrollere naboerne ved hjælp af den tidligere nævnte hurtigmatrixproduktalgoritme i samme asymptotiske tid . Det værste tilfælde af denne algoritme opstår, når Ω(√ m ) hjørner hver har Ω(√ m ) naboer, og de resterende hjørner har få naboer, i hvilket tilfælde den samlede tid er ( m 3.376/2 ) = O( m 1.688 ). $2{\sqrt {m))$ $2{\sqrt {m}}{\sqrt {m}}$

Optælling

Fordi klofri grafer inkluderer alle komplementer til trekantfri grafer, vokser antallet af klofri grafer med n toppunkter mindst med samme hastighed som antallet af trekantfrie grafer, det vil sige eksponentielt fra roden af n . Antal forbundne klofri grafer med n kanter, for n = 1, 2, …

1, 1, 2, 5, 14, 50, 191, 881, 4494, 26389, 184749, ... OEIS -sekvens A022562 .

Hvis graferne kan afbrydes, er antallet af grafer større:

1, 2, 4, 10, 26, 85, 302, 1285, 6170, ... OEIS -sekvens A086991 .

Teknikken til Palmer, Read, Robinson ( Palmer, Read, Robinson, 2002 ) [9] gør det muligt at beregne antallet af klofri kubiske grafer meget effektivt, hvilket er usædvanligt for grafoptællingsproblemer .

Matchende

Sumner ( Sumner, 1974 ) [10] og uafhængigt af hinanden Las Vergnas ( Las Vergnas, 1975 ) [11] beviste, at enhver forbundet graf uden kløer med et lige antal hjørner har en perfekt match [12] . Det vil sige, at der er et sæt kanter i grafen, således at hvert toppunkt er endepunktet på præcis én kant fra matchningen. Det følger heraf, at det for linjegrafer med et lige antal kanter er muligt at opdele alle kanter på en sti med længde to. Perfekte matchninger kan bruges til en anden karakteristik af grafer uden kløer - det er præcis de grafer, hvor enhver forbundet genereret subgraf af lige rækkefølge har en perfekt matchning [12] .

Sumners bevis viser strengt taget, at man i enhver forbundet graf uden kløer kan finde et par konjugerede hjørner, hvis fjernelse efterlader grafen forbundet. For at bevise dette finder Sumner et par toppunkter u og v , der er så langt fra hinanden som muligt, og vælger w blandt naboerne til toppunktet v , der er så langt fra u som muligt. Som han viste, kan hverken v eller w ligge på den korteste vej fra noget andet toppunkt til u , så fjernelse af v og w efterlader grafen forbundet. Successiv fjernelse af sådanne par danner en perfekt matchning i en graf uden kløer.

Den samme idé om beviset fungerer i det mere generelle tilfælde: hvis u er et hvilket som helst toppunkt, er v et hvilket som helst toppunkt, der er så langt som muligt fra u , og w er ethvert nabopunkt til v , der er så langt som muligt fra u . Fjernelse af v og w fra grafen ændrer ikke afstandene til u . Processen med at danne matchninger ved at finde og fjerne par af vw , der er maksimalt fjernt fra u , kan således fuldføres i lineær tid ved blot at krydse bredden-første søgetræet , startende fra toppunktet u . Chrobak, Naor og Novick ( 1989 ) [13] gav en anden tids-lineær algoritme baseret på dybde-først søgning , samt effektive parallelle algoritmer til det samme problem.

Faudree , Flandrin, Ryjáček [2] gav flere nært beslægtede resultater, herunder følgende:

En ( r − 1)-forbundet graf, der ikke indeholder K 1, r- undergrafer af ulige rækkefølge, har perfekte matchninger for enhver r ≥ 2.
Grafer af ulige rækkefølge uden kløer med højst et toppunkt af grad en kan opdeles i en ulige cyklus og en matchende.
For enhver k , der er mindst halvdelen af minimumsgraden af en klofri graf, hvor enten k eller antallet af hjørner er lige, har grafen en k -faktor.
Hvis en graf uden kløer er ( 2k + 1)-forbundet, så kan enhver k -kant-matchning udvides til en perfekt matchning.

Uafhængige sæt

Et uafhængigt sæt i en linjegraf svarer til en matchning i den originale graf, det vil sige et sæt kanter, hvor ikke to kanter har et fælles punkt. Som Edmonds ( 1965) [14] viste , kan den maksimale overensstemmelse i enhver graf findes i polynomisk tid; Sbihi ( 1980 ) [15] udvidede denne algoritme, så den nye algoritme finder det maksimale uafhængige sæt i enhver graf uden kløer [16] . Minty ( Minty, 1980 ) [17] (korrigeret af Nakamura og Tamura ( Nakamura, Tamura, 2001 ) [18] ) gav endnu en udvidelse af Edmonds algoritmer for grafer uden kløer, som transformerer problemet til matchning i en hjælpegraf, der er opnået fra original graf uden kløer. Mintys tilgang kan bruges til at løse det mere generelle problem med at finde et uafhængigt sæt af maksimal vægt i polynomisk tid. Der er en generalisering af disse resultater til en bred klasse af grafer [16] .

Som Sbihi bemærkede, hvis er et uafhængigt sæt i en graf uden kløer, så kan et hvilket som helst toppunkt på grafen højst have to nabospidser ud af - tre nabospidser ville danne en klo. Sbihi kalder et toppunkt for mættet , hvis det har to naboer fra og umættet , hvis det ikke hører til og samtidig har mindre end to naboer fra . Det følger af Sbyhas observation, at hvis og der er uafhængige sæt, skal grafen genereret af , højst have grad to. Det er således foreningen af stier og cykler. Især, hvis det ikke er et maksimalt uafhængigt sæt, adskiller det sig fra ethvert maksimalt uafhængigt sæt af cyklusser og komplementære stier , det vil sige stier, hvor toppunkter fra og ikke fra alternerende, og for hvilke begge endelige toppunkter ikke er mættede. Den symmetriske forskel af grafer og færdiggørelsesstien er det maksimale uafhængige sæt (Den symmetriske forskel af graferne H og G med det samme sæt af toppunkter V er en graf med det samme sæt af toppunkter V, der indeholder kanterne G og H, men ikke indeholder fælles kanter tilhørende både G og H). Sbihas algoritme øger trinvist størrelsen af det uafhængige sæt ved at finde komplementære stier, så længe sådanne stier kan findes. $jeg$ $jeg$ $jeg$ $jeg$ $jeg$ $jeg$ $J$ $I\cup J$ $jeg$ $jeg$ $jeg$ $jeg$

Det er vanskeligt at finde en forstærkende sti, fordi en stiudvidelse muligvis ikke eksisterer, hvis den indeholder en kant mellem to hjørner, som ikke hører til . Heldigvis kan dette kun ske i to tilfælde: to tilstødende hjørner kan være de sidste hjørner på stien, eller der er et hjørne mellem dem, der støder op til begge. Ethvert andet tilstødende toppunkt vil føre til en klo. Tilstødende endepunkter kan bortskaffes ved midlertidigt at fjerne alle tilstødende v -hjørner, før man leder efter en færdiggørelsessti, der starter ved v . Hvis stien ikke findes, kan toppunktet v fjernes fra grafen indtil afslutningen af algoritmen. Efter en sådan reduktion af grafen kan problemet beskrives i form af en switch graph , selvom Sbihy ikke brugte denne terminologi. En skiftegraf er en ikke-rettet graf, hvor buerne af ethvert toppunkt er opdelt i to grupper, og enhver sti, der passerer gennem toppunktet, skal indeholde kanter fra begge grupper. Det er muligt at konstruere en omskiftergraf på sættet af mættede og umættede hjørner af en kloløs graf, hvis kanter forbinder hjørnerne, hvis de ikke støder op til den oprindelige graf, og der er en bane på længde 2 mellem dem, der går gennem et vertex fra I . De to sæt kanter ved hvert toppunkt er dannet af de to toppunkter I , gennem hvilke disse baner af længde 2 passerer. Stien i skiftegrafen mellem to umættede hjørner svarer til den komplementære sti i den originale graf. Skiftegrafen har kvadratisk kompleksitet, og stien i den kan findes i lineær tid, og i hele algoritmens tid kan det være nødvendigt at finde O( n ) genopfyldningsstier. Sbihas algoritme kræver således O( n 3 ) køretid. $jeg$

Farvelægning, klik og dominans

En perfekt graf er en graf, hvor det kromatiske tal og størrelsen af den maksimale klike er ens, og hvor denne lighed eksisterer i enhver induceret subgraf. Det er kendt (ved den strenge perfekte grafsætning ), at perfekte grafer kan karakteriseres som grafer, der ikke har ulige cyklusser eller komplementerer til ulige cyklusser (de såkaldte ulige huller) som inducerede undergrafer (de såkaldte ulige huller ) [ 5] . Men i mange år forblev denne kendsgerning en formodning, kun bevist for specielle underklasser af grafer. En sådan underklasse var familien af grafer uden kløer - flere forfattere fandt ud af, at grafer uden kløer og uden ulige cyklusser og huller er perfekte. Fuldkommenheden af en graf uden kløer kan kontrolleres i polynomiel tid. I en perfekt graf uden kløer danner naboskabet til ethvert toppunkt komplementet til en todelt graf . Du kan farvelægge en perfekt graf uden kløer eller finde den maksimale klike i den i polynomiel tid [19] .

Hvis grafen uden klør ikke er perfekt, bliver problemet med at finde den maksimale klike NP-hårdt [6] . Problemet med at finde den optimale farvning af en sådan graf er også NP-hårdt, da (gennem linjegrafen) dette problem generaliserer det NP-hårde problem med at beregne det kromatiske tal for en graf [6] . Af samme grund er det NP-svært at finde en farvealgoritme, hvis garanterede effektivitet er bedre end 4/3. Imidlertid kan en garanteret effektivitet på to opnås i den grådige farvealgoritme , da det kromatiske tal for en klofri graf er større end halvdelen af dens maksimale effekt.

Selvom ikke alle klofri grafer er perfekte, opfylder klofri grafer en anden egenskab relateret til perfektion. En graf kaldes en perfekt dominansgraf , hvis den har et minimalt dominerende sæt , som er et uafhængigt sæt af hjørner, og hvis alle genererede undergrafer har den samme egenskab. Grafer uden blus har denne egenskab. For at vise dette, lad os antage, at D er et dominerende sæt i en graf uden kløer, og lad v og w være to konjugerede hjørner af D . Så skal det sæt af hjørner, der domineres af v , men ikke af w , være en klike (ellers ville v være midten af kloen). Hvis hvert hjørne af denne klike allerede er domineret af mindst ét medlem af D , så kan v fjernes for at generere et mindre uafhængigt dominerende sæt. Ellers kan v erstattes af et af de ikke-dominerede hjørner fra kliken, hvilket genererer et dominerende sæt med færre tilstødende hjørner. Ved at gentage disse substitutioner vil vi nå frem til en dominerende mængde, der ikke er større end D , så hvis den initiale D er den minimale dominerende mængde, vil processen ende med et lige så stort uafhængigt dominerende sæt [20] .

På trods af den perfekte dominansegenskab er det et NP-hårdt problem at bestemme størrelsen af det mindste dominerende sæt i en graf uden kløer [6] . Men i modsætning til mere generelle klasser af grafer har det parametrisk kompleksitet at finde det mindste dominerende sæt i en graf uden kløer med faste parametre — problemet kan løses i tide, der afhænger polynomisk af størrelsen af grafen og eksponentielt på størrelsen af det dominerende sæt [21] [22] .

Struktur

I en række artikler beviste Chudnovskaya og Seymour [23] en klofri strukturel grafteori svarende til grafstruktursætningen for familier af mindre lukkede grafer bevist af Robertson og Seymour , og den strukturelle teori for perfekte grafer, som Chudnovsky ), Seymour og deres medforfattere plejede at bevise den strengt perfekte grafsætning [5] . Teorien er for kompleks til at beskrive i detaljer her, men for at vise dens skønhed beskriver vi et par af deres resultater. For det første, for en særlig underklasse af grafer uden kløer, som de kaldte kvasi-line grafer (eller lokalt kvasi-todelte grafer), hævder de, at hver sådan graf har en af to former:

En fuzzy cirkulær intervalgraf er en klasse af grafer, der kan repræsenteres geometrisk som punkter og buer på en cirkel.
En graf, der kan bygges ud fra en multigraf ved at erstatte hver kant med en fuzzy lineær intervalgraf . Dette generaliserer konstruktionen af linjegrafer, hvor hver kant af multigrafen er erstattet af et toppunkt. Fuzzy lineære intervalgrafer er konstrueret på samme måde som fuzzy cirkulære intervalgrafer, kun på et segment og ikke på en cirkel.

Chudnovskaya og Seymour klassificerede vilkårlige forbundne grafer uden kløer som følger:

Seks specifikke grafer uden kløer. Tre af dem er linjegrafer, nogle buegrafer og genererede undergrafer af icosahedron . De resterende tre kræver yderligere definitioner.
Grafer dannet på fire enkle måder ud fra mindre grafer uden kløer.
Antiprismatiske grafer , en klasse af tætte grafer , er defineret som grafer uden kløer, hvor fire spidser genererer en undergraf med mindst to kanter.

Det meste af deres klassifikationsarbejde er afsat til analyse af antiprismatiske grafer. Schläfli-grafen , en stærkt regulær klofri graf med parametre srg(27,16,10,8), spiller en vigtig rolle i denne del af analysen. Denne strukturteori har ført til nye fremskridt inden for kombinatorik af polyedre og nye grænser for de kromatiske antal af klofri grafer [5] , såvel som nye faste parameter parametriske kompleksitetsalgoritmer til at dominere sæt i klofri grafer [22] .

Noter

↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , s. 88.
↑ 1 2 Faudree, Flandrin, Ryjáček, 1997 .
↑ LW Beineke. Beitrage zur Graphentheorie. - Teubner, 1968. - S. 17-33 .
↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , s. 89.
↑ 1 2 3 4 5 Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. Den stærke perfekte grafsætning. - 2006. - T. 164 , no. 1 . - S. 51-229 . doi : 10.4007 / annals.2006.164.51 .
↑ 1 2 3 4 Faudree, Flandrin, Ryjáček, 1997 , s. 132.
↑ Alon Itai, Michael Rodeh. Find et minimumskredsløb i en graf // SIAM Journal on Computing . - 1978. - V. 7 , no. 4 . - S. 413-423 . - doi : 10.1137/0207033 .
↑ Ton Kloks, Dieter Kratsch, Haiko Müller. Finde og tælle små inducerede subgrafer effektivt // Informationsbehandlingsbreve. - 2000. - T. 74 , no. 3-4 . - S. 115-121 . - doi : 10.1016/S0020-0190(00)00047-8 .
↑ Edgar M. Palmer, Ronald C. Read, Robert W. Robinson. Optælling af klofri kubikgrafer // SIAM Journal om diskret matematik . - 2002. - T. 16 , no. 1 . - S. 65-73 . - doi : 10.1137/S0895480194274777 .
↑ David P. Sumner. Grafer med 1-faktorer. - 1974. - T. 42 , no. 1 . - S. 8-12 . - doi : 10.2307/2039666 . — .
↑ M. Las Vergnas. En note om matchninger i grafer // Cahiers du Centre d'Études de Recherche Opérationnelle. - 1975. - T. 17 , no. 2-3-4 . - S. 257-260 .
↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , s. 120-124.
↑ Marek Chrobak, Joseph Naor, Mark B. Novick. Algoritmer og datastrukturer : Workshop WADS '89, Ottawa, Canada, august 1989, Proceedings. - Springer, 1989. - T. 382 . - S. 147-162 . - doi : 10.1007/3-540-51542-9_13 .
↑ Jack Edmonds. Stier, træer og blomster // Canadiske J. Math. - 1965. - T. 17 , no. 0 . - S. 449-467 . - doi : 10.4153/CJM-1965-045-4 .
↑ Najiba Sbihi. Algorithme de recherche d'un stabil de cardinalité maximum dans un graphe sans étoile // Diskret matematik. - 1980. - T. 29 , no. 1 . - S. 53-76 . - doi : 10.1016/0012-365X(90)90287-R .
↑ 1 2 Faudree, Flandrin, Ryjaček, 1997 , s. 133-134.
↑ George J. Minty. Om maksimalt uafhængige sæt af knudepunkter i klofri grafer // Journal of Combinatorial Theory. Serie B. - 1980. - T. 28 , no. 3 . - S. 284-304 . - doi : 10.1016/0095-8956(80)90074-X .
↑ Daishin Nakamura, Akihisa Tamura. En revision af Mintys algoritme til at finde et maksimalt vægtet stabilt sæt af en klofri graf // Journal of the Operations Research Society of Japan. - 2001. - T. 44 , no. 2 . - S. 194-204 .
↑ Faudree, Flandrin, Ryjáček, 1997 , s. 135-136.
↑ Faudree, Flandrin, Ryjáček, 1997 , s. 124-125.
↑ Marek Cygan, Geevarghese Philip, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk. Det dominerende sæt er fast parameter, der kan føres i klofri grafer. – 2010.
↑ 1 2 Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard Woeginger. Dominans, når stjernerne er ude. – 2010.
↑ Maria Chudnovsky, Paul Seymour. Undersøgelser i kombinatorik 2005. - Cambridge Univ. Presse, 2005. - T. 327 . - S. 153-171 .

Litteratur

Ralph Faudree, Evelyne Flandrin, Zdeněk Ryjáček. Klofri grafer - En undersøgelse // Diskret matematik. - 1997. - T. 164 , no. 1-3 . - S. 87-147 . - doi : 10.1016/S0012-365X(96)00045-3 .