Perifer cykel - Peripheral cycle

I denna graf är den röda triangeln som bildas av hörn 1, 2 och 5 en perifer cykel: de fyra återstående kanterna bildar en enda bro. Pentagon 1–2–3–4–5 är dock inte perifer, eftersom de två återstående kanterna bildar två separata broar.

I grafteori är en perifer cykel (eller perifer krets ) i en oriktad graf intuitivt en cykel som inte skiljer någon del av grafen från någon annan del. Perifera cykler (eller, som de ursprungligen kallades, perifera polygoner , eftersom Tutte kallade cykler "polygoner") studerades först av Tutte (1963) och spelar viktiga roller för karakterisering av plana grafer och för att generera cykelutrymmen för icke -plana grafer .

Definitioner

En perifer cykel i en graf kan definieras formellt på ett av flera likvärdiga sätt: ${\ displaystyle C}$${\ displaystyle G}$

• ${\ displaystyle C}$är perifer om det är en enkel cykel i en ansluten graf med egenskapen att det för varje två kanter och in finns en väg in som börjar med , slutar med och inte har några inre hörn som tillhör .${\ displaystyle e_ {1}}$${\ displaystyle e_ {2}}$${\ displaystyle G \ setminus C}$${\ displaystyle G}$${\ displaystyle e_ {1}}$${\ displaystyle e_ {2}}$${\ displaystyle C}$
• ${\ displaystyle C}$är perifer om det är en inducerad cykel med egenskapen som subgrafen som bildas genom att radera kanter och hörn är ansluten.${\ displaystyle G \ setminus C}$${\ displaystyle C}$
• Om är någon subgraf av , en bro av är en minimal subgraf av som kant disjunkta från och som har egenskapen att alla dess platser av bilagor (hörn intill kanter i både och ) tillhörde . En enkel cykel är perifer om den har exakt en bro.${\ displaystyle C}$${\ displaystyle G}$${\ displaystyle C}$${\ displaystyle B}$${\ displaystyle G}$${\ displaystyle C}$${\ displaystyle B}$${\ displaystyle G \ setminus B}$${\ displaystyle C}$${\ displaystyle C}$

Motsvarigheten av dessa definitioner är inte svår att se: en ansluten subgraf av (tillsammans med kanterna som länkar den till ), eller ett ackord av en cykel som får den att inte induceras, måste i båda fallen vara en bro och måste också vara en ekvivalensklass för det binära förhållandet på kanter där två kanter är relaterade om de är ändarna på en bana utan inre hörn i . ${\ displaystyle G \ setminus C}$${\ displaystyle C}$${\ displaystyle C}$

Egenskaper

Perifera cykler förekommer i teorin om polyhedrala grafer , det vill säga 3-vertex-anslutna plana grafer . För varje plan graf och varje plan inbäddning måste ytorna på inbäddningen som induceras cykler vara perifera cykler. I en polyhedral graf är alla ansikten perifera cykler och varje perifer cykel är ett ansikte. Det följer av detta faktum att (upp till kombinatorisk ekvivalens, valet av ytterytan och planets orientering) har varje polyhedral graf en unik plan inbäddning. ${\ displaystyle G}$${\ displaystyle G}$

I plana grafer, den cykel utrymme genereras av ytorna, men i icke-plana grafer perifera cykler spelar en liknande roll: för varje tre-vertex-ansluten ändlig graf, är cykeln utrymme som genereras av de perifera cykler. Resultatet kan också utökas till lokalt ändliga men oändliga diagram. I synnerhet följer att tre-anslutna grafer garanterat innehåller perifera cykler. Det finns 2-anslutna grafer som inte innehåller perifera cykler (ett exempel är den kompletta bipartitgrafen , för vilken varje cykel har två broar) men om en 2-ansluten graf har minst tre grader innehåller den minst en perifer cykel. ${\ displaystyle K_ {2,4}}$

Perifera cykler i 3-anslutna grafer kan beräknas i linjär tid och har använts för att utforma planaritetstester. De utvidgades också till den mer allmänna uppfattningen om icke-separerande öronnedbrytningar. I vissa algoritmer för att testa planaritet 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 dubbelkopplad graf med kretsrankning är mindre än tre (t.ex. en cykeldiagram eller theta-graf ) varje cykel perifer, men varje tvåkopplad graf med kretsrang tre eller fler har en icke-perifer cykel, som kan hittas i linjär tid.

Generalisera ackord grafer , Seymour & Weaver (1984) definierar en strangulated graf för att vara en graf i vilken varje perifer cykel är en triangel. De karakteriserar dessa grafer som klick-summor av ackordgrafer och maximala plana grafer .

Relaterade begrepp

Perifera cykler har också kallats icke-separerande cykler, men denna term är tvetydig, eftersom den också har använts för två besläktade men distinkta begrepp: enkla cykler vars avlägsnande skulle koppla bort den återstående grafen och cykler för en topologiskt inbäddad graf som att skärning längs cykeln inte skulle koppla bort ytan på vilken grafen är inbäddad.

I matroider är en icke-separerande krets en matroid-krets (det vill säga en minimal beroende uppsättning) så att radering av kretsen lämnar en mindre matroid som är ansluten (det vill säga som inte kan skrivas som en direkt summa av matroider) . Dessa är analoga med perifera cykler, men inte samma även i grafiska matroider (matroiderna vars kretsar är de enkla cyklerna i en graf). Till exempel, i den fullständiga bipartitgrafen är varje cykel perifer (den har bara en bro, en tvåkantig väg) men den grafiska matroid som bildas av denna bro är inte ansluten, så ingen krets i den grafiska matroiden är icke-separerande . ${\ displaystyle K_ {2,3}}$${\ displaystyle K_ {2,3}}$

Referenser