Pseudo-skov

I grafteori er en pseudo-skov en urettet graf [1] , hvor enhver forbundet komponent har højst en cyklus . Det vil sige, at det er et system af knudepunkter og kanter , der forbinder par af knudepunkter, således at ikke to cyklusser har fælles spidser og ikke kan forbindes med en sti. Et pseudo -træ er en forbundet pseudo-skov.

Navnene er taget i analogi med velkendte træer og skove (et træ er en sammenhængende graf uden cyklusser, en skov er en forening af afbrudte træer). Gabov og Tarjan [2] tilskriver undersøgelsen af ​​pseudoskove til Danzigs bog fra 1963 om lineær programmering , hvor pseudoskove optræder i løsningen af ​​nogle trafikstrømsproblemer [3] . Pseudoskove danner også teoretiske grafmodeller af funktioner og optræder i nogle algoritmiske problemer. Pseudoskove er sparsomme grafer - de har meget få kanter i forhold til antallet af toppunkter, og deres matroide struktur tillader nogle andre familier af sparsomme grafer at blive dekomponeret til en forening af skove og pseudoskove. Navnet "pseudo-skov" kommer fra en artikel af Picard og Keran [4] .

Definitioner og struktur

Vi definerer en urettet graf som et sæt af toppunkter og kanter , således at hver kant indeholder to (muligvis matchende) toppunkter som endepunkter. Det vil sige, at flere kanter (kanter med samme endespidser) og løkker (kanter, hvis endespidser er de samme) er tilladt [1] . En undergraf af en graf er en graf, der er dannet af en delmængde af toppunkter og kanter, således at enhver kant i den delmængde har terminale hjørner i delmængden af ​​toppunkter. En forbundet komponent af en urettet graf er en undergraf bestående af spidser og kanter, som kan nås ved at følge kanterne med udgangspunkt i et starthjørne. En graf er forbundet, hvis et hvilket som helst toppunkt eller kant kan nås fra ethvert andet toppunkt eller kant. En cyklus i en urettet graf er en forbundet undergraf, hvor et hvilket som helst toppunkt falder ind på nøjagtigt to kanter eller er en sløjfe.

En pseudo-skov er en urettet graf, hvor hver forbundet komponent indeholder højst en cyklus [5] . Tilsvarende er det en urettet graf, hvor hver forbundet komponent ikke har flere kanter end hjørner [6] . Komponenter, der ikke har cyklusser, er bare træer , og komponenter, der har en enkelt cyklus, kaldes 1-træer eller en- cyklus grafer . Det vil sige, at et 1-træ er en sammenhængende graf, der indeholder præcis én cyklus. En pseudo-skov med en enkelt forbundet komponent (almindeligvis kaldet et pseudotræ , selvom nogle forfattere definerer et pseudotræ som et 1-træ) er enten et træ eller et 1-træ. Generelt kan en pseudo-skov indeholde flere forbundne komponenter, som alle er træer eller 1-træer.

Fjerner vi en af ​​løkkekanterne fra 1-træet, får vi et træ som resultat. I den modsatte retning, hvis vi tilføjer en ny kant til træet, der forbinder to vilkårlige hjørner, får vi et 1-træ. Træstien, der forbinder de to endepunkter af den tilføjede bue, danner sammen med selve den tilføjede bue en enkelt 1-træsløkke. Tilføjer vi en kant til 1-træet, der forbinder et af træets toppunkter med det nydannede toppunkt, bliver resultatet igen et 1-træ med et toppunkt mere. En anden metode til at konstruere 1-træer starter med en enkelt cyklus, og toppunkter tilføjes sekventielt til 1-træet et vilkårligt antal gange. Kanterne på ethvert 1-træ kan opdeles unikt i to undergrafer, hvoraf den ene er en cyklus, og den anden er en skov, og hvert skovtræ indeholder nøjagtigt et cyklus-toppunkt [7]

Noget smallere typer af pseudoskove bliver også undersøgt.

En 1-skov , nogle gange kaldet en maksimal pseudo -skov , er en skov, hvortil ingen kant kan tilføjes uden at danne en graf med mere end én cyklus. Hvis en pseudo-skov indeholder et træ som en af ​​dets komponenter, kan det ikke være en 1-skov, fordi du kan tilføje en kant til den komponent for at cykle gennem den komponent, eller du kan tilføje en kant, der forbinder træet med en anden komponent. Således er 1-skove præcis pseudo-skove, hvor hver komponent er et 1-træ. En spændende pseudo-skov af en urettet graf G er en spændende undergraf , der er en pseudo-skov, dvs. en pseudo-skov af graf G , der indeholder alle hjørnerne af graf G. Sådanne pseudoskove er ikke forpligtet til at have nogen kanter, da f.eks. en tom undergraf (det vil sige, der indeholder alle toppunkter på grafen G og ikke har nogen kanter) er en pseudo-skov (og dens komponenter er træer, som hver består af af et enkelt toppunkt). De maksimale pseudoskove af G er undergraferne af G , der er pseudoskove, der ikke er indeholdt i nogen større pseudoskove indeholdt i G. Den maksimale pseudo-skov i en graf G er altid et spændende pseudotræ, men det omvendte er ikke sandt. Hvis G ikke har nogen forbundne komponenter, der er træer, så er dens maksimale pseudoskove 1-skove, men hvis G har et træ som en komponent, så vil dens maksimale pseudoskove ikke være 1-skove. Mere præcist, i enhver graf G , består dens maksimale pseudoskove af alle skovene i G sammen med et eller flere 1-træer, der dækker de resterende hjørner af G .

Orienterede pseudoskove

Versioner af disse definitioner bruges også til rettede grafer . Ligesom urettede grafer består rettede grafer af hjørner og kanter, men hver kant har en retning (en rettet kant kaldes normalt en bue). En rettet pseudo-skov er en rettet graf, hvor hvert toppunkt højst har én udgående bue. Det vil sige, at grafen har en udfaldsgrad , der ikke overstiger én. En rettet 1-skov , ofte kaldet en funktionel graf (se nedenfor ) og nogle gange en maksimalt rettet pseudo -skov , er en rettet graf, hvor hvert toppunkt har en udgrad på præcis én [8] . Hvis D er en rettet pseudo-skov, er den urettede graf dannet ved at fjerne retninger fra kanterne af D en urettet pseudo-skov.

Antal kanter

Enhver pseudo-skov på et sæt af n toppunkter har højst n kanter, og enhver maksimal pseudo-skov på et sæt af n toppunkter har præcis n toppunkter. Omvendt, hvis en graf G har den egenskab, at antallet af kanter i en genereret undergraf af grafen S for en hvilken som helst delmængde S af grafens hjørnepunkter ikke overstiger antallet af hjørner af grafen S , så er G en pseudo-skov. 1-træer kan defineres som forbundne grafer med samme antal hjørner og kanter [2] .

For familier af grafer, hvis en familie af grafer har den egenskab, at enhver undergraf af en graf i familien er i samme familie, og hver graf i familien ikke har flere kanter end hjørner, så indeholder familien kun pseudoskove. For eksempel er enhver undergraf af en sporle (en graf tegnet på en sådan måde, at ethvert par af kanter har ét skæringspunkt) også en sporle, så Conways hypotese om, at enhver spore ikke har flere kanter end hjørner, kan omregnes, at hver spor er en pseudo-skov. Mere præcist, hvis formodningen er sand, så er trekles præcis pseudoskove uden cyklusser med fire hjørner og højst en cyklus med et ulige antal hjørner [9] [10] .

Strainu og Teran [11] generaliserede egenskaberne ved sparsomhed i definitionen af ​​pseudoskove - den definerer en graf som ( k , l )-sparsom, hvis en ikke-tom undergraf med n toppunkter højst har kn  −  l kanter, og ( k , l )-tæt hvis den ( k , l )-sparsom og har nøjagtig kn  −  l kanter. Således er pseudoskove (1,0)-sparsomme grafer, og maksimale pseudoskove er (1,0)-tætte grafer. Nogle andre vigtige familier af grafer kan defineres for andre værdier af k og l , og hvis l  ≤  k , ( k , l )-sparsomme grafer kan beskrives som grafer dannet af foreningen af ​​l kantløse skove og k  −  l pseudoskove [12] .

Næsten enhver tilstrækkelig sjælden tilfældig graf er en pseudo-skov [13] . Det vil sige, at hvis c er en konstant (0 < c < 1/2) og P c ( n ) er sandsynligheden for, at en graf valgt tilfældigt blandt grafer med n toppunkter og cn kanter er en pseudo-skov, så tenderer P c ( n ) til én i grænse, når n vokser . Men for c > 1/2 har næsten enhver tilfældig graf med cn -kanter en stor ikke-enkeltcyklus-komponent.

Optælling

En graf er enkel , hvis den ikke har nogen løkker eller flere kanter. Antallet af simple 1-træer med n mærkede hjørner er [14]

Værdier for n op til 18 kan findes i Encyclopedia of Integer Sequences -sekvensen A057500 .

Antallet af maksimalt rettede n -vertex-pseudoskove, hvor sløjfer er tilladt, er n n , da der for et hvilket som helst toppunkt er n mulige endespidser af udgående buer. André Joyal brugte denne kendsgerning til at bevise [15] Cayleys formel, at antallet af urettede træer på n toppunkter er lig med n n  − 2 ved at finde en bijektion mellem maksimalt orienterede pseudoskove og urettede træer med to forskellige toppunkter [ 16] . Hvis sløjfer er tilladt, er antallet af maksimalt rettede pseudoskove ( n  − 1) n .

Funktionsgrafer

Styrede pseudoskove og selvkort er i en vis forstand matematisk ækvivalente. Enhver afbildning af ƒ på en mængde X på sig selv (det vil sige en endomorfi på X ) kan fortolkes som definitionen af ​​en rettet pseudo-skov, der har en bue fra x til y , når ƒ( x ) = y . Den resulterende rettede pseudo-skov er maksimal og kan inkludere sløjfer , hvis for nogle x ƒ( x ) = x . Eliminering af sløjfer fører til ikke-maksimale pseudoskove. I den modsatte retning definerer enhver maksimalt orienteret pseudo-skov en mapping ƒ, for hvilken ƒ( x ) er lig med endepunktet af buen udgående fra x , og enhver ikke-maksimal orienteret pseudo-skov kan gøres maksimal ved at tilføje sløjfer og konvertere til en funktion i den samme måde. Af denne grund kaldes maksimalt rettet pseudoskove undertiden funktionelle grafer [2] . At repræsentere en funktion som en funktionel graf giver et praktisk sprog til at beskrive egenskaber, som ikke er lette at beskrive ud fra et funktionsteoretisk synspunkt. Denne teknik er især nyttig til problemer , der involverer itererede funktioner , som svarer til stier i grafteori.

Cyklussøgning , problemet med at spore stier i en funktionel graf for at finde en cyklus i den, har applikationer i kryptografi og beregningstalteori som en del af Pollards ro-algoritme for heltalsfaktorisering og som en metode til at finde kollisioner i kryptografisk hash funktioner . Disse applikationer antager, at ƒ er tilfældig. Flajolet og Odlyzhko [17] studerede egenskaberne af funktionelle grafer opnået fra tilfældige kortlægninger. Især en version af fødselsdagsparadokset indebærer, at i en tilfældig funktionel graf med n hjørner, går stien, der starter fra et tilfældigt valgt vertex, normalt efter O(√ n ) trin. Konyagin et al. udførte analyser og beregningsmæssige statistiske undersøgelser [18] .

Martin, Odlyzko og Wolfram [19] har udforsket pseudoskove, der modellerer dynamikken i cellulære automater . Disse er funktionelle grafer, de kaldte dem tilstandsovergangsdiagrammer , de har et toppunkt for hver mulig konfiguration, hvor celler i den cellulære automat kan placeres, og buer forbinder hver konfiguration, der opnås fra den i henhold til reglerne for den cellulære automat. Det er muligt at opnå automategenskaber fra strukturen af ​​disse diagrammer, såsom antallet af komponenter, længden af ​​endelige cyklusser, dybden af ​​træer, der forbinder de ikke-endelige tilstande af disse cyklusser, eller symmetrien af ​​diagrammet. For eksempel svarer ethvert toppunkt uden en indgående bue til Edens Have , mens toppunkter med en løkke svarer til et stilleben .

En anden tidlig anvendelse af funktionelle grafer er i kæder [20] brugt til at studere Steiner triple systemer [21] [22] [23] . En kæde af tripler er en funktionel graf, der indeholder et toppunkt for hver mulig tripel af tegn. Hver tripel pqr er afbildet af funktionen ƒ til stu , hvor pqs , prt og qru  er tripler tilhørende triplesystemet og indeholder henholdsvis parrene pq , pr og qr . Kæder har vist sig at være en kraftig invariant af et tredobbelt system, selvom deres beregning er besværlig.

Bicyklisk matroide

En matroide er en matematisk struktur, hvor visse sæt af elementer er defineret som uafhængige, i den forstand, at uafhængige sæt opfylder egenskaber, der modellerer egenskaberne ved lineær uafhængighed i et vektorrum . Et af standardeksemplerne på matroider er grafmatroiden , hvor de uafhængige sæt er sæt af kanter i grafens skove. Skovenes matroidestruktur er vigtig for algoritmer til beregning af det minimale spændingstræ i en graf. På lignende måde kan man definere matroider for pseudoskove.

For enhver graf G = ( V , E ), kan vi definere en matroide på kanterne af G , hvori sættet af kanter er uafhængigt, hvis og kun hvis dette sæt danner en pseudo-skov. Denne matroide er kendt som den bicykliske matroide i grafen G [24] [25] . De minimale afhængige sæt for denne matroide er de minimale forbundne undergrafer af G , der har mere end én cyklus, og disse undergrafer kaldes nogle gange cykler. Der er tre mulige typer cykler - thetagrafen har to toppunkter forbundet af tre stier, der ikke har interne fælles punkter, "otte" består af to cykler, der har ét fælles toppunkt, og "håndjern" er dannet af to cykler, der gør ikke har fælles hjørner, forbundet med [ 26] . En graf er en pseudo-skov, hvis og kun hvis den ikke indeholder en cykel som undergraf [11] .

Ulovlige mindreårige

At danne en mindre pseudo-skov ved at trække nogle kanter sammen og fjerne nogle andre kanter danner en ny pseudo-skov. Familien af ​​pseudoskove er således lukket i mol, og det følger så af Robertson-Seymour-sætningen , at pseudoskove kan beskrives i form af et endeligt sæt af forbudte mindreårige , svarende til Wagner-sætningen om at beskrive plane grafer som grafer, der hverken har nogen af en komplet graf K 5 eller en komplet todelt graf K 3.3 som mindre. Som diskuteret tidligere, indeholder enhver ikke-pseudo-skov graf enten håndjern, figur otte eller theta som en undergraf. Alle "håndjern" og "ottere" kan trækkes sammen til en "sommerfugl" ("otte" med fem hjørner), og enhver "theta"-graf kan trækkes sammen til en " diamant " ("theta"-graf med fire hjørner) [27 ] , således at enhver graf, der ikke er en pseudo-skov, indeholder enten en "sommerfugl" eller en "diamant" som mindre, og kun disse grafer er minimale grafer, der ikke tilhører pseudo-skov-familien. Hvis kun "diamant" er forbudt, men ikke "sommerfugl", får vi en bredere familie af grafer, bestående af "kaktusser" og en uensartet forening af et sæt "kaktusser" [28] .

Hvis vi betragter multigrafer med sløjfer , er der kun én forbudt mol, et toppunkt med to sløjfer.

Algoritmer

En tidlig algoritmisk anvendelse af pseudoskove brugte netværkssimplex- algoritmen og dens anvendelse på det generaliserede netværksflowproblem til at modellere transformationer af produkter fra en type til en anden [3] [29] . I disse problemer defineres et transportnetværk , hvor toppunkterne modellerer hvert produkt, og kanterne modellerer, om det er tilladt at transformere fra et produkt til et andet. Hver kant er mærket gennemstrømning (mængden af ​​produkt, der kan konverteres pr. tidsenhed), flow (konverteringshastigheden mellem produkter) og pris (hvor meget vi taber i konvertering pr. produktenhed). Udfordringen er at bestemme, hvor meget af hvert produkt, der skal konverteres på hver bue af transportnetværket for at minimere omkostningerne eller maksimere indtjening uden at overtræde begrænsningen og ikke tillade nogen form for produkt at gå ubrugt. Denne type problemer kan formuleres som et lineært programmeringsproblem og løses ved hjælp af simpleksmetoden . Mellemløsninger opnået fra denne algoritme, såvel som den endelige optimale løsning, har specielle strukturer - hver bue af transportnetværket bruges enten ikke eller bruger den maksimale båndbredde, med undtagelse af en delmængde af buer, der danner kernens pseudoskove. transportnetværk, og på denne delmængde af buer kan flowet tage en værdi fra nul til den maksimale gennemstrømning. I denne applikation kaldes en-cyklus grafer nogle gange også forstørrede træer , og maksimale pseudoskove kaldes også forstørrede skove [29] .

Minimumspændende pseudo-skov-problemet bruger at finde en minimumvægt, der spænder over pseudo-skov i en større graf G med vægte. På grund af pseudoskovenes matroide struktur kan maksimale pseudoskove med minimumvægt findes ved hjælp af grådige algoritmer, svarende til minimumspændingstræ- problemet . Gabov og Tarjan fandt imidlertid en mere effektiv lineær tidstilgang til denne sag [2] .

Pseudotræheden af ​​en graf G defineres analogt med træheden som det mindste antal pseudoskove, som kanter kan opdeles i. Tilsvarende er det minimumstallet k , således at grafen G er ( k , 0)-sparsom, eller minimumsantallet k , således at kanterne af grafen G kan rettes således, at den resulterende rettede graf højst vil have en udgrad. k . På grund af matroide strukturen af ​​pseudoskove, kan pseudotreeness beregnes i polynomiel tid [30]

En tilfældig todelt graf med n hjørner på hver af dens dele med cn kanter valgt tilfældigt og uafhængigt for hvert par af n 2 mulige knudepunkter er en pseudo-skov med høj sandsynlighed for en konstant c strengt taget mindre end én. Denne kendsgerning spiller en nøglerolle i analysen af ​​gøgehashing [31] , en datastruktur til at finde nøgleværdi-par ved at se på en af ​​de to hashtabeller på det sted, der er bestemt af nøglen - man kan danne en "parret graf" hvis hjørner svarer til placeringen af ​​placeringen i hash-tabellerne, og kanter forbinder to steder, hvor en af ​​nøglerne kan findes. Parvis hashing finder alle nøgler, hvis og kun hvis den parrede graf er en pseudo-skov [32] .

Pseudoskove spiller også en nøglerolle i parallelle graffarvealgoritmer og relaterede problemer [33] [34] .

Noter

  1. ↑ 1 2 De urettede grafer, der betragtes her, er multigrafer eller pseudografer, ikke simple grafer .
  2. ↑ 1 2 3 4 Gabow, Tarjan, 1988 .
  3. ↑ 12 Dantzig , 1963 .
  4. ↑ Picard, Queyranne, 1982 .
  5. ↑ Denne definition bruges for eksempel af Gabow og Westermann ( Gabow, Westermann (1992 )).
  6. ↑ Denne definition bruges af Gabow og Tarjan ( Gabow, Tarjan (1988 )).
  7. ↑ Se for eksempel beviset for Lemma 4 i Alvarez, Bles og Cern ( Àlvarez et al (2002 )).
  8. ↑ Krusk, Rudolf og Snir ( Kruskal et al (1990 )) bruger i stedet den omvendte definition, hvor hvert toppunkt har en inputgrad på én. De resulterende grafer, som de kalder single -cycle , er de transponerede grafer af de grafer, der er behandlet i dette papir.
  9. ↑ Woodall, 1969 .
  10. ↑ Lovász et al., 1997 .
  11. ↑ 12 Streinu, Theran, 2009 .
  12. ↑ Whiteley, 1988 .
  13. ↑ Bolobash ( Bollobás (1985 )). Se især Corollary 24, s. 120, for en grænse for antallet af toppunkter, der tilhører en-cykluskomponenter i en tilfældig graf, og Corollary 19, s. 113, for en grænse for antallet af forskellige mærkede en- cyklus grafer.
  14. ↑ Riddell (1951 ); se A057500 i Encyclopedia of Integer Sequences .
  15. ↑ Du kan læse om metoden med bijektiv bevis i Vershiks artikel ( Vershik (1986 ))
  16. ↑ Aigner, Ziegler, 1998 .
  17. ↑ Flajolet, Odlyzko, 1990 .
  18. ↑ Konyagin et al., 2016 .
  19. ↑ Martin, Odlyzko, Wolfram, 1984 .
  20. ↑ I den engelske version - tog
  21. ↑ Hvid, 1913 .
  22. ↑ Colbourn, Colbourn, Rosenbaum, 1982 .
  23. ↑ Stinson, 1983 .
  24. ↑ Simoes-Pereira, 1972 .
  25. ↑ Matthews, 1977 .
  26. ↑ Ordliste over underskrevne og forstærkede grafer og allierede områder . Hentet 23. oktober 2016. Arkiveret fra originalen 3. marts 2016.
  27. ↑ For denne terminologi, se liste over små grafer Arkiveret 22. juli 2012 på Wayback Machine fra Information System om Graph Class Inclusions Arkiveret 5. februar 2019 på Wayback Machine . Imidlertid kan sommerfuglen referere til en anden familie af grafer, relateret til hyperkuber .
  28. ↑ El-Mallah, Colbourn, 1988 .
  29. ↑ 1 2 Ahuja, Magnanti, Orlin, 1993 .
  30. ↑ Gabow, Westermann (1992 ). Se også Kowaliks hurtige tilnærmelsesskemaer ( Kowalik (2006 )).
  31. ↑ . Generelt er udtrykket mislykket, men det har slået rod i russisksproget litteratur (som en direkte oversættelse af gøgehashing ). Tilsyneladende er udtrykket opstået på grund af parringen af ​​"gøg". Metoden skal kaldes parret eller to-trins hashing.
  32. ↑ Kutzelnigg, 2006 .
  33. ↑ Goldberg, Plotkin, Shannon, 1988 .
  34. ↑ Kruskal et al., 1990 .

Litteratur

Links