Petersensova věta - Petersens theorem - Wikipedia

A perfektní shoda (červené okraje), v Petersenův graf. Protože Petersenův graf je krychlový a bez můstku, splňuje podmínky Petersenovy věty.

Kubický (ale ne přemostěný) graf bez dokonalého párování, který ukazuje, že nelze přemostit stav přemostění v Petersenově teorému

V matematický disciplína teorie grafů, Petersenova věta, pojmenoval podle Julius Petersen, je jedním z prvních výsledků v teorii grafů a lze jej uvést následovně:

Petersenova věta. Každý krychlový, bez můstku graf obsahuje a perfektní shoda.^[1]

Jinými slovy, pokud má graf přesně tři hrany na každém vrcholu a každá hrana patří do cyklu, pak má sadu hran, která se dotkne každého vrcholu přesně jednou.

Důkaz

Ukážeme to pro každý kubický graf bez přemostění G = (PROTI, E) máme to pro každou sadu U ⊆ PROTI počet připojených komponent v grafu indukovaný podle PROTI − U s lichým počtem vrcholů je nanejvýš mohutnost U. Pak Tutteova věta G obsahuje perfektní shodu.

Nechat G_i být složkou s lichým počtem vrcholů v grafu vyvolaných množinou vrcholů PROTI − U. Nechat PROTI_i označte vrcholy G_i a nechte m_i označit počet okrajů G s jedním vrcholem v PROTI_i a jeden vrchol dovnitř U. Jednoduchým argumentem dvojího počítání to máme

${ displaystyle sum nolimits _ {v ve V_ {i}} deg _ {G} (v) = 2 | E_ {i} | + m_ {i},}$

kde E_i je sada okrajů G_i s oběma vrcholy dovnitř PROTI_i. Od té doby

${ displaystyle sum nolimits _ {v v V_ {i}} deg _ {G} (v) = 3 | V_ {i} |}$

je liché číslo a 2|E_i| je sudé číslo, z toho vyplývá m_i musí být liché číslo. Navíc od té doby G je bez mostu, to máme m_i ≥ 3.

Nechat m být počet hran v G s jedním vrcholem v U a jeden vrchol v grafu indukovaný PROTI − U. Každá komponenta s lichým počtem vrcholů přispívá alespoň 3 hranami m, a ty jsou jedinečné, proto je počet takových komponent maximálně m/3. V nejhorším případě každá hrana s jedním vrcholem U přispívá k m, a proto m ≤ 3|U|. Dostaneme

${ displaystyle | U | geq { frac {1} {3}} m geq | {{ text {komponenty s lichým počtem vrcholů}} } |,}$

což ukazuje, že stav Tutteova věta drží.

Dějiny

Věta je kvůli Julius Petersen, dánský matematik. Lze jej považovat za jeden z prvních výsledků v teorie grafů. Věta se objevuje jako první v článku z roku 1891 “Die Theorie der regulären grafy".^[1] Podle dnešních standardů je Petersenův důkaz věty komplikovaný. V důkazech vyvrcholila řada zjednodušení důkazu Frink (1926) a König (1936).

V moderních učebnicích je Petersenova věta pokryta jako aplikace Tutteova věta.

Aplikace

• V kubickém grafu s dokonalým párováním tvoří hrany, které nejsou v dokonalém párování, a 2-faktor. Podle orientace 2-faktor, okraje perfektní shody lze rozšířit na cesty délky tři, řekněme tím, že vezmeme ven orientované hrany. To ukazuje, že každý kubický graf bez můstků se rozkládá na hranové disjunktní cesty délky tři.^[2]
• Petersenovu větu lze také použít k prokázání, že každý maximální rovinný graf lze rozložit na sadu hranových disjunktních cest délky tři. V tomto případě duální graf je kubický a bez můstků, takže podle Petersenovy věty má shodu, která v původním grafu odpovídá spárování sousedních ploch trojúhelníku. Každá dvojice trojúhelníků dává cestu délky tři, která zahrnuje hranu spojující trojúhelníky spolu se dvěma ze čtyř zbývajících hran trojúhelníku.^[3]
• Aplikováním Petersenovy věty na duální graf a trojúhelníková síť a spojením párů trojúhelníků, které se neshodují, lze síť rozložit na cyklickou proužky trojúhelníků. S některými dalšími transformacemi jej lze proměnit v jeden pás, a proto poskytuje metodu transformace trojúhelníkové sítě tak, aby se jeho dvojitý graf stal hamiltonián.^[4]

Rozšíření

Počet perfektních shody v kubických přemostěných grafech

Bylo to domněnkou Lovász a Plummer že počet perfektní shody obsažené v a krychlový, bez můstku graf je exponenciální v počtu vrcholů grafu n.^[5]Domněnka byla poprvé prokázána pro bipartitní, kubické, nepřemostěné grafy podle Voorhoeve (1979), později pro rovinný, kubické, nepřemostěné grafy podle Chudnovsky & Seymour (2012). Obecný případ byl vyřešen Esperet a kol. (2011), kde se ukázalo, že každý kubický graf bez přemostění obsahuje alespoň ${ displaystyle 2 ^ {n / 3656}}$ perfektní shody.

Algoritmické verze

Biedl a kol. (2001) diskutovat o účinných verzích Petersenovy věty. Na základě Frinkova důkazu^[6] získají Ó(n log⁴ n) algoritmus pro výpočet dokonalého párování v kubickém grafu bez můstku s n vrcholy. Pokud je graf dále rovinný stejný papír dává Ó(n) algoritmus. Jejich Ó(n log⁴ n) časová hranice může být vylepšena na základě následných vylepšení času pro udržení sady mostů v dynamickém grafu.^[7] Další vylepšení, zkrácení doby vázané na Ó(n log² n) nebo (s dalšími náhodně datové struktury ) Ó(n log n (log log n)³), byly dány Diks & Stanczyk (2010).

Vyšší stupeň

Li G je pravidelný graf stupňů d jehož okrajová konektivita je alespoň d - 1 a G má sudý počet vrcholů, pak má perfektní shodu. Silněji, každý okraj G patří alespoň k jedné dokonalé shodě. Podmínku počtu vrcholů lze z tohoto výsledku vynechat, když je stupeň lichý, protože v takovém případě (pomocí handmaking lemma ) počet vrcholů je vždy sudý.^[8]

Poznámky

Reference