Cykel (grafteori) - Cycle (graph theory)

En graf med kanter färgade för att illustrera bana HAB (grön), stängd bana eller gå med en upprepad topp BDEFDCB (blå) och en cykel utan upprepad kant eller vertex HDGH (röd).

I grafteorin är en cykel i en graf ett icke-tomt spår där de enda upprepade hörn är de första och sista hörnpunkterna. En riktad cykel i en riktad graf är ett icke-tomt riktat spår där de enda upprepade hörnpunkterna är de första och sista hörnpunkterna.

En graf utan cykler kallas en acyklisk graf . En riktad graf utan riktade cykler kallas en riktad acyklisk graf . Ett anslutet diagram utan cykler kallas ett träd .

Definitioner

Krets, cykel

  • En krets är ett icke-tomt spår där det första toppunktet är lika med det senaste toppunktet ( stängt spår ).
Låt G = ( V , E , ϕ ) vara ett diagram. En krets är ett icke-tomt spår ( e 1 , e 2 ,…, e n ) med en vertexsekvens ( v 1 , v 2 ,…, v n , v 1 ) .
  • En cykel eller enkel krets är en krets där det enda upprepade toppunktet är det första / sista toppunktet.
  • Den längd av en krets eller cykel är antalet kanter som är involverade.

Riktad krets, cykel

  • En riktad krets är ett icke-tomt riktat spår där det första toppunktet är lika med det senaste toppunktet.
Låt G = ( V , E , ϕ ) vara en riktad graf. En riktad krets är ett icke-tomt riktat spår ( e 1 , e 2 ,…, e n ) med en vertexsekvens ( v 1 , v 2 ,…, v n , v 1 ) .
  • En riktad cykel eller enkel riktad krets är en riktad krets där det enda upprepade toppunktet är det första / sista toppunktet.

Ackordlösa cykler

I denna graf är den gröna cykeln (ABCDEFA) ackordlös medan den röda cykeln (GHIJKLG) inte är det. Detta beror på att kanten KI är ett ackord.

En ackordlös cykel i en graf, även kallad ett hål eller en inducerad cykel, är en cykel så att inga två hörn i cykeln är förbundna med en kant som inte i sig hör till cykeln. Ett antihål är komplementet till ett grafhål. Ackordlösa cykler kan användas för att karakterisera perfekta grafer : med den starka perfekta grafsatsen är en graf perfekt om och bara om ingen av dess hål eller antihål har ett udda antal hörn som är större än tre. En ackorddiagram , en speciell typ av perfekt graf, har inga hål av någon storlek som är större än tre.

Den omkrets av ett diagram är längden av dess kortaste cykel; denna cykel är nödvändigtvis ackordlös. Burar definieras som de minsta vanliga graferna med givna kombinationer av grad och omkrets.

En perifer cykel är en cykel i ett diagram med den egenskapen att varannan kanter som inte finns på cykeln kan anslutas med en väg vars inre vertikaler undviker cykeln. I en graf som inte bildas genom att lägga till en kant till en cykel måste en perifer cykel vara en inducerad cykel.

Cykelutrymme

Termen cykeln kan också hänvisa till ett element i cykeln utrymmet av en graf. Det finns många cykelutrymmen, ett för varje koefficientfält eller ring. Det vanligaste är det binära cykelutrymmet (vanligtvis bara kallat cykelutrymmet ), som består av kantuppsättningarna som har jämn grad vid varje toppunkt; den bildar en vektorrum över två element fält . Genom Veblens teorem kan varje element i cykelutrymmet bildas som en kant-ojämn förening av enkla cykler. En cykelbas i diagrammet är en uppsättning enkla cykler som utgör grunden för cykelutrymmet.

Med hjälp av idéer från algebraisk topologi generaliseras det binära cykelutrymmet till vektorrymden eller moduler över andra ringar som heltal, rationella eller reella tal etc.

Cykeldetektering

Förekomsten av en cykel i riktade och oriktade grafer kan bestämmas av om djup-första sökning (DFS) hittar en kant som pekar på en förfader till det aktuella toppunktet (den innehåller en bakkant ). Alla bakkanter som DFS hoppar över är en del av cykler. I ett oriktat diagram bör kanten till en nods räkning inte räknas som en bakkant, men att hitta någon annan redan besökt topp kommer att indikera en bakkant. När det gäller oriktade grafer krävs bara O ( n ) -tid för att hitta en cykel i ett n- vertikalt diagram, eftersom högst n  - 1 kanter kan vara trädkanter.

Många topologiska sorteringsalgoritmer kommer att upptäcka cykler också, eftersom det är hinder för topologisk ordning att existera. Dessutom, om en riktad graf har delats in i starkt anslutna komponenter , finns cykler bara inom komponenterna och inte mellan dem, eftersom cykler är starkt anslutna.

För riktade grafer kan distribuerade meddelandebaserade algoritmer användas. Dessa algoritmer förlitar sig på tanken att ett meddelande som skickas av ett toppunkt i en cykel kommer tillbaka till sig själv. Distribuerade cykeldetekteringsalgoritmer är användbara för att bearbeta storskaliga grafer med ett distribuerat grafbehandlingssystem i ett datorkluster (eller superdator).

Tillämpningar av cykeldetektering inkluderar användning av väntar på grafer för att upptäcka blockeringar i samtidiga system.

Täcker diagram efter cykler

I sitt 1736-dokument om Königsbergs sju broar , allmänt ansett som grafteoriens födelse, bevisade Leonhard Euler att det är nödvändigt och tillräckligt att för en ändlig riktad graf att ha en sluten promenad som besöker varje kant exakt en gång. vara anslutna förutom isolerade hörn (det vill säga alla kanter finns i en komponent) och har jämn grad vid varje toppunkt. Motsvarande karakterisering för förekomsten av en sluten promenad som besöker varje kant exakt en gång i en riktad graf är att grafen är starkt ansluten och har lika många inkommande och utgående kanter vid varje toppunkt. I båda fallen är den resulterande vandringen känd som en Euler-cykel eller Euler-turné. Om en ändlig oriktad graf har jämn grad vid vart och ett av dess hörnpunkter, oavsett om den är ansluten, är det möjligt att hitta en uppsättning enkla cykler som tillsammans täcker varje kant exakt en gång: detta är Veblens sats . När en ansluten graf inte uppfyller villkoren i Eulers sats kan en sluten promenad av minsta längd som täcker varje kant åtminstone en gång ändå hittas i polynomtid genom att lösa färdvägskontrollproblemet .

Problemet med att hitta en enda enkel cykel som täcker varje toppunkt exakt en gång, snarare än att täcka kanterna, är mycket svårare. En sådan cykel är känd som en Hamilton-cykel , och det är NP-komplett att bestämma om den existerar . Mycket forskning har publicerats angående klasser av diagram som kan garanteras innehålla Hamilton-cykler; ett exempel är malmens teorem att en Hamiltonian-cykel alltid kan hittas i en graf för vilken varje icke intilliggande par av hörn har grader som summerar till åtminstone det totala antalet hörn i diagrammet.

De cykel dubbla kuvert Conjecture anges att för varje bridge diagram finns det en multimängd av enkla cykler som täcker varje kant av grafen exakt dubbelt. Att bevisa att detta är sant (eller hitta ett motexempel) är fortfarande ett öppet problem.

Grafklasser definierade av cykler

Flera viktiga klasser av grafer kan definieras av eller kännetecknas av deras cykler. Dessa inkluderar:

Se även

Referenser