Perifer slinga

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 januari 2022; kontroller kräver 4 redigeringar .

En perifer cykel i en oriktad graf  är en cykel som inte separerar någon del av grafen från någon annan. Perifera cykler (eller, som de först kallades, perifera polygoner , som Tutt kallade cykler " polygoner "), studerades först av Tutt, William Thomas [1] . Perifera cykler spelar en viktig roll i beskrivningen av plana grafer och i bildandet av cykliska utrymmen för icke- plana grafer [2] .

Definitioner

En perifer cykel i en graf kan formellt definieras på något av följande sätt:

Ekvivalensen av dessa definitioner är lätt att se: en sammankopplad subgraf av en graf (tillsammans med kanter som förbinder den med ) eller ett cykelackord som bryter mot cykelgenerering måste i alla fall vara en bro, och det måste också finnas en ekvivalensklass för en binär relation på kanter där två kanter är sammankopplade , om de är ändar på en bana utan inre hörn i [8]

Egenskaper

Perifera cykler förekommer i teorin om polyedriska grafer , dvs vertex-3-anslutna plana grafer . För alla plana grafer och alla plana inbäddningar måste ytorna på inbäddningen som genereras av cykler vara perifera cykler. I en polyedrisk graf är alla ytor perifera cykler, och alla perifera cykler är ett ansikte [9] . Detta innebär att (före kombinatorisk ekvivalens, val av yttre yta och orientering av planet) varje polyedrisk graf har en unik plan inbäddning [10] .

I plana grafer bildas det cykliska utrymmet av kanterna, men i icke-planära grafer spelar perifera cykler en liknande roll - för alla vertex-3-kopplade finita grafer bildas det cykliska rummet av perifera cykler [11] . Resultatet kan utökas till lokalt ändliga oändliga grafer [12] . I synnerhet innebär detta att 3-kopplade grafer garanterat innehåller perifera cykler. Det finns 2-kopplade grafer som inte innehåller perifera cykler (ett exempel är en komplett tvådelad graf , där varje cykel har två bryggor), men om en 2-kopplad graf har en minsta grad av tre, så innehåller den minst en perifer cykel [13] .

Perifera cykler i 3-kopplade grafer kan beräknas i linjär tid och har använts för att utveckla tester för planaritet [14] . De har också utvidgats till det mer allmänna begreppet icke-separerande öronexpansion . I vissa algoritmer för att kontrollera planariteten hos grafer är det användbart att hitta en cykel som inte är perifer för att dela upp problemet i mindre delproblem. I en tvåkopplad graf med konturrang mindre än tre (som en cykel eller en tetagraf ) är vilken cykel som helst en periferi, men varje tvåkopplad graf med konturrang tre eller mer har en icke-perifer cykel som kan hittas i linjär tid [15] .

Generaliserande ackordsgrafer definierade Seymour och Weaver [16] en sammandragen graf som en graf där varje perifer cykel är en triangel. De beskrev dessa grafer som klicksummor av ackordsgrafer och maximala plana grafer [17] .

Relaterade begrepp

Perifera cykler kallades också icke-separerande cykler [3] , men denna term är tvetydig, eftersom den används för två andra begrepp - för enkla cykler, vars borttagning gör att den återstående grafen kopplas bort [18] , och för cykler av topologiska cykler. inbäddning av grafen , så att skärning längs cykeln inte gör att ytan som grafen är inbäddad i [19] kopplas bort .

I matroider är en icke-separerande cykel en matroidcykel (d.v.s. minimalt beroende uppsättning) där borttagning av -cykeln lämnar en mindre matroid som är ansluten (dvs. som inte kan delas upp i en direkt summa av matroider) [20] . De liknar perifera cykler, men är inte identiska ens i grafmatroider (matroider där cykler är enkla cykler av en graf). Till exempel, i en komplett tvådelad graf är vilken cykel som helst perifer (den har bara en bro, en bana med två kanter), men grafmatroiden som bildas av denna bro är inte ansluten, så ingen grafgrafmatroidcykel är icke -separerande.

Anteckningar

  1. ↑ Tutte, 1963 .
  2. ↑ Tutte, 1963 , sid. 743–767.
  3. ↑ 1 2 Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 74–75.
  4. ↑ Detta är den definition som används av Bruhn ( 2004 ). Brun särskiljde dock fallet som har isolerat hörn från frånkopplingen orsakad av cykelborttagning .
  5. ↑ Inte att förväxla med bridge , ett annat begrepp med samma namn.
  6. ↑ Tutte, 1960 , sid. 304–320.
  7. ↑ Denna definition av perifera cykler användes ursprungligen av Tutte ( Tutte 1963 ). Seymour och Weaver ( 1984 ) använde samma definition av en perifer loop, men med en annan bryggdefinition som mer liknar child loop-definitionen för perifera loopar.
  8. ↑ Se till exempel sats 2.4 i Tutte ( Tutte 1960 ) som visar att en uppsättning brohörn är sammankopplade med banor, se Seymour och Weaver ( 1984 ) för att definiera broar med hjälp av ackord och sammankopplade komponenter, och se även Di Battista, Eades, Tamassia, Tollis 1998 för att definiera broar med användning av ekvivalensklasser för en binär relation på kanter.
  9. ↑ Tutte, 1963 , sid. Satserna 2.7 och 2.8.
  10. ↑ Se anmärkningarna efter sats 2.8 i Tuttes artikel ( Tutte 1963 ). Som Tutt noterar var detta redan känt för Whitney ( Whitney 1932 )
  11. ↑ Tutte, 1963 , sid. Sats 2.5.
  12. ↑ Bruhn, 2004 , sid. 235–256.
  13. ↑ Thomassen, Toft, 1981 , sid. 199–224.
  14. ↑ Schmidt, 2014 , sid. 967-978.
  15. ↑ Di Battista, Eades, Tamassia, Tollis, 1998 , sid. 75–76 Lemma 3.4.
  16. ↑ Seymour, Weaver, 1984 .
  17. ↑ Seymour, Weaver, 1984 , sid. 241–251.
  18. ↑ Se till exempel ( Borse, Waphare 2008 )
  19. ↑ Se till exempel ( Cabello, Mohar 2007 )
  20. ↑ Maia, Lemos, Melo, 2007 , sid. 162–171.

Litteratur