Perifer sløjfe

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 31. januar 2022; checks kræver 4 redigeringer .

En perifer cyklus i en urettet graf  er en cyklus , der ikke adskiller nogen del af grafen fra nogen anden. Perifere cyklusser (eller, som de først blev kaldt, perifere polygoner , som Tutt kaldte cyklusser " polygoner "), blev først studeret af Tutt, William Thomas [1] . Perifere cyklusser spiller en vigtig rolle i beskrivelsen af ​​plane grafer og i dannelsen af ​​cykliske rum af ikke -plane grafer [2] .

Definitioner

En perifer cyklus i en graf kan formelt defineres på en af ​​følgende måder:

Ækvivalensen af ​​disse definitioner er let at se: en sammenhængende undergraf af en graf (sammen med kanter, der forbinder den med ) eller en cyklusakkord, der overtræder cyklusgenerering, skal under alle omstændigheder være en bro, og der skal også være en ækvivalensklasse af en binær relation på kanter, hvor to kanter er forbundet, hvis de er ender af en sti uden indvendige hjørner i [8]

Egenskaber

Perifere cyklusser optræder i teorien om polyedriske grafer , dvs. vertex-3-forbundne plane grafer . For enhver plan graf og enhver plan indlejring skal overfladerne af indlejringen, der genereres af cyklusser, være perifere cyklusser. I en polyedrisk graf er alle flader perifere cyklusser, og enhver perifer cyklus er en flade [9] . Dette indebærer, at (før kombinatorisk ækvivalens, valg af ydre flade og orientering af planet) enhver polyedrisk graf har en unik plan indlejring [10] .

I plane grafer er det cykliske rum dannet af kanterne, men i ikke-planære grafer spiller perifere cyklusser en lignende rolle - for enhver top-3-forbundet finite graf er det cykliske rum dannet af perifere cyklusser [11] . Resultatet kan udvides til lokalt endelige uendelige grafer [12] . Dette indebærer især, at 3-forbundne grafer er garanteret at indeholde perifere cyklusser. Der er 2-forbundne grafer, der ikke indeholder perifere cyklusser (et eksempel er en komplet todelt graf , hvor enhver cyklus har to broer), men hvis en 2-forbundet graf har en minimumsgrad på tre, så indeholder den mindst én perifer cyklus [13] .

Perifere cyklusser i 3-forbundne grafer kan beregnes i lineær tid og er blevet brugt til at udvikle test for planaritet [14] . De er også blevet udvidet til det mere generelle begreb om ikke-adskillende øreudvidelser . I nogle algoritmer til kontrol af planariteten af ​​grafer er det nyttigt at finde en cyklus, der ikke er perifer, for at opdele problemet i mindre underproblemer. I en toforbundet graf med konturrang på mindre end tre (såsom en cyklus eller en tetagraf ) er enhver cyklus en periferi, men enhver toforbundet graf med konturrang på tre eller mere har en ikke-perifer cyklus, der kan findes i lineær tid [15] .

Generaliserende akkordgrafer definerede Seymour og Weaver [16] en sammentrukket graf som en graf, hvor hver perifer cyklus er en trekant. De beskrev disse grafer som kliksummer af akkordgrafer og maksimale plane grafer [17] .

Relaterede begreber

Perifere cyklusser blev også kaldt ikke-separerende cyklusser [3] , men dette udtryk er tvetydigt, da det bruges om to andre begreber - for simple cyklusser, hvis fjernelse gør den resterende graf afbrudt [18] , og for cyklusser af topologiske indlejring af grafen , således at skæring langs cyklus ikke gør overfladen, hvori grafen er indlejret [19] afbrudt .

I matroider er en ikke-separerende cyklus en matroide-cyklus (dvs. minimalt afhængig sæt), hvor fjernelse af -cyklus efterlader en mindre matroide , der er forbundet (dvs. som ikke kan opdeles i en direkte sum af matroider) [20] . De ligner perifere cyklusser, men er ikke identiske selv i grafmatroider (matroider, hvor cyklusser er simple cyklusser af en graf). For eksempel, i en komplet todelt graf , er enhver cyklus perifer (den har kun én bro, en sti med to kanter), men grafmatroiden dannet af denne bro er ikke forbundet, så ingen grafgrafmatroidecyklus er ikke - adskillende.

Noter

  1. ↑ Tutte, 1963 .
  2. ↑ Tutte, 1963 , s. 743-767.
  3. ↑ 1 2 Di Battista, Eades, Tamassia, Tollis, 1998 , s. 74-75.
  4. ↑ Dette er den definition, som Bruhn ( 2004 ) bruger. Brun skelnede dog det tilfælde, der har isoleret hjørner fra afbrydelsen forårsaget af cyklusfjernelse .
  5. ↑ Må ikke forveksles med bridge , et andet begreb af samme navn.
  6. ↑ Tutte, 1960 , s. 304-320.
  7. ↑ Denne definition af perifere cyklusser blev oprindeligt brugt af Tutte ( Tutte 1963 ). Seymour og Weaver ( 1984 ) brugte den samme definition af en perifer sløjfe, men med en anden brodefinition, der i højere grad minder om child loop-definitionen for perifere sløjfer.
  8. ↑ Se f.eks. sætning 2.4 i Tutte ( Tutte 1960 ), der viser, at et sæt brohjørner er forbundet med stier, se Seymour og Weaver ( 1984 ) for at definere broer ved hjælp af akkorder og forbundne komponenter, og se også Di Battista, Eades, Tamassia, Tollis 1998 for at definere broer ved hjælp af ækvivalensklasser af en binær relation på kanter.
  9. ↑ Tutte, 1963 , s. Sætning 2.7 og 2.8.
  10. ↑ Se bemærkningerne efter sætning 2.8 i Tuttes papir ( Tutte 1963 ). Som Tutt bemærker, var dette allerede kendt af Whitney ( Whitney 1932 )
  11. ↑ Tutte, 1963 , s. Sætning 2.5.
  12. ↑ Bruhn, 2004 , s. 235-256.
  13. ↑ Thomassen, Toft, 1981 , s. 199-224.
  14. ↑ Schmidt, 2014 , s. 967-978.
  15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , s. 75–76 Lemma 3.4.
  16. ↑ Seymour, Weaver, 1984 .
  17. ↑ Seymour, Weaver, 1984 , s. 241-251.
  18. ↑ Se for eksempel ( Borse, Waphare 2008 )
  19. ↑ Se for eksempel ( Cabello, Mohar 2007 )
  20. ↑ Maia, Lemos, Melo, 2007 , s. 162-171.

Litteratur