Petersens sætning

Petersens sætning  er en af ​​de tidligste sætninger i grafteori , opkaldt efter Julius Petersen . Definitionen af ​​teoremet kan formuleres som følger:

Petersens sætning. Enhver kubisk dobbeltforbundet graf indeholder en perfekt matchning [1] .

Med andre ord, hvis nøjagtigt tre kanter kommer frem fra hvert hjørne af grafen (grafen er 3-regulær), og hver kant hører til cyklussen , så har grafen et sæt kanter, der berører hvert hjørne af grafen nøjagtigt én gang.


Bevis

Det er nødvendigt at vise, at for hver kubisk dobbeltforbundet graf G = ( V , E ) er det rigtigt, at antallet af ulige forbundne komponenter i undergrafen V  −  U for hvert sæt U ⊆ V ikke overstiger kardinaliteten af ​​U . Så, ifølge Tutts sætning , indeholder G en perfekt match.

Lad G i  være en komponent med et ulige antal hjørner i undergrafen V  −  U . Lad V i betegne hjørnerne af G i , og m i angive antallet af kanter på G med et toppunkt i V i og et toppunkt i U . Ved at fordoble denne værdi får du følgende:

hvor E i  er sættet af kanter i Gi med begge hjørner i V i . Fordi

er et ulige tal og 2| e i |  er lige, så må m i være ulige. Desuden er m i  ≥ 3 , da G  er en dobbeltforbundet graf.

Lad m  være antallet af kanter på grafen G , der forbinder toppunkterne på U med toppunkterne på grafen V  −  U . Hver komponent med et ulige antal hjørner tilføjer mindst 3 unikke kanter til m , så antallet af sådanne komponenter ikke overstiger m /3 . I værste fald vil hver kant fra et af hjørnerne i U blive talt med i m -tællingen , og så m  ≤ 3| U | . Det viser sig

Dermed er betingelsen for Tutts sætning opfyldt.

Historie

Sætningen er opkaldt efter den danske matematiker Julius Petersen . Betragtes som en af ​​de første teoremer i grafteori . Sætningen dukkede første gang op i papiret "Die Theorie der regulären graphs" fra 1891 [1] . Beviset for sætningen præsenteret af Petersen anses for komplekst efter nutidens standarder. En række forenklinger af beviset præsenteres i beviserne fra Frink ( Frink (1926 )) og König ( König (1936 )).

I moderne lærebøger behandles Petersens sætning som en anvendelse af Tutts sætning .

Ansøgning

Udvidelser af sætningen

Antal perfekte matchninger i kubiske dobbeltforbundne grafer

Lovas og Plummer foreslog, at antallet af perfekte matchninger indeholdt i en kubisk dobbeltforbundet graf afhænger eksponentielt af antallet af grafens hjørnepunkter n [5] . Formodningen blev først bevist for todelte kubiske dobbeltforbundne grafer af Voorhoeve (1979 ), og senere for plane kubiske dobbeltforbundne grafer af Chudnovsky & Seymour (2012 ). Den generelle sag blev løst i Esperet et al. (2011 ), hvor det blev vist, at hver kubisk dobbeltforbundet graf indeholder mindst perfekte matchninger.

Algoritmiske versioner

Biedl et al. (2001 ) diskuterede effektive versioner af Petersens sætning. Baseret på Frinks bevis [6] opnåede de en O ( n log 4 n ) kompleksitetsalgoritme til at beregne en perfekt matchning i en kubisk dobbeltforbundet graf med n toppunkter. Hvis grafen også er plan , giver det samme papir en algoritme med O ( n ) kompleksitet . Deres O ( n log 4 n ) tidsbegrænsning kan forbedres baseret på efterfølgende tidsforbedringer for at opretholde mange broer i en dynamisk graf [7] . Yderligere forbedringer, der reducerer tiden til O ( n log 2 n ) eller (med yderligere tilfældige datastrukturer ) O ( n log n (log log n ) 3 ) er blevet foreslået af Diks & Stanczyk (2010 ).

Stigende grad

Hvis G  er en regulær graf af grad d , hvis kantforbindelse er mindst d − 1, og G har et lige antal hjørner, så har den en perfekt match. Mere strengt taget hører hver kant af grafen G til mindst én perfekt matchning. Betingelsen om antallet af knudepunkter kan udelades fra denne erklæring, når graden er ulige, fordi i dette tilfælde (ved håndtrykslemmaet ) er antallet af knudepunkter altid lige [8] .

Kilder

  1. ↑ 12 Petersen (1891 ) .
  2. ↑ Se for eksempel Bouchet & Fouquet (1983 ).
  3. ↑ Häggkvist & Johansson (2004 ).
  4. ↑ Meenakshisundaram & Eppstein (2004) .
  5. ↑ Lovász & Plummer (1986) .
  6. ↑ Frink (1926 ).
  7. ↑ Thorup (2000) .
  8. ↑ Naddef & Pulleyblank (1981 ), Sætning 4, s. 285.

Links