2-faktorizace 2k-regulárního grafu

Úloha číslo: 3268

Dokažte Petersenovu větu o tom, že každý \(2k\)-regulární graf lze rozložit na \(k\) hranově disjunktních 2-faktorů. Dodejme, že \(k\)-faktor je graf, ve kterém mají všechny vrcholy stupeň \(k\).

  • Nápověda

    S pomocí Eulerovského tahu převeďte hledání 2-faktoru ve \(2k\)-regulárním grafu na hledání perfektního párování v \(k\)-regulárním bipartitním grafu.

  • Řešení

    Bez újmy na obecnosti předpokládejme, že je daný graf \(G\) souvislý, neboť jinak rozložíme každou komponentu zvlášť.

    Protože je daný graf \(2k\)-regulární, má všechny stupně sudé, a tudíž jej lze nakreslit jedním uzavřeným tahem. Hrany grafu zorientujeme podle tahu. U každého vrcholu bude vstupní i výstupní stupeň přesně \(k\).

    Každý vrchol rozdělíme na dva, kdy u jednoho ponecháme pouze vstupní hrany a u druhého pouze výstupní hrany. Výsledkem bude \(k\)-regulární bipartitní graf \(B\). Důstedkem Hallovy věty je, že hrany každého bipartitního \(k\)-regulárního grafu lze rozložit na \(k\) perfektních párování.

    Hrany každého párování v \(B\) tvoří v grafu \(G\) hledaný 2-faktor, protože každý vrchol z \(G\) odpovídá dvěma vrcholům v \(B\). Tyto vrcholy navíc nejsou v \(B\) spojené hranou (ta by odpovídala smyčce v \(G\)) a oba jsou incidentní s jednou párovací hranu – pro každý vrchol z dvojice různou.

Obtížnost: Středně těžká úloha
Úloha na dokazování, ověřování
Úloha vyžadující neobvyklý trik nebo nápad
Komplexní úloha
En translation
	Zaslat komentář k úloze