Hamiltoniánský rozklad - Hamiltonian decomposition

Waleckiho Hamiltoniánský rozklad celého grafu

{ displaystyle K_ {9}}

v teorie grafů, obor matematiky, a Hamiltoniánský rozklad daného grafu je a rozdělit okrajů grafu do Hamiltonovské cykly. Hamiltonovské rozklady byly studovány jak pro neorientované grafy a pro řízené grafy; v neřízeném případě lze hamiltonovský rozklad také popsat jako a 2-faktorizace grafu tak, že každý faktor je spojen.

Nezbytné podmínky

Aby Hamiltonianův rozklad existoval v neorientovaném grafu, musí být graf připojen a pravidelný dokonce stupeň Směrovaný graf s takovým rozkladem musí být silně propojený a všechny vrcholy musí mít stejný vnitřní i vnější stupeň, ale tento stupeň nemusí být rovnoměrný.^[1]

The mediální graf z Herschelův graf je 4-pravidelný rovinný graf bez Hamiltonovského rozkladu. Stínované oblasti odpovídají vrcholům podkladového Herschelova grafu.

Pro 4-pravidelné rovinné grafy, lze odvodit další nezbytné podmínky Grinbergova věta. Příklad 4-pravidelného rovinného grafu, který nesplňuje tyto podmínky a nemá hamiltonovský rozklad, je dán mediální graf z Herschelův graf.^[2]

Kompletní grafy

Každý kompletní graf s lichým číslem ${ displaystyle n}$ vrcholů má hamiltonovský rozklad. Tento výsledek, který je zvláštním případem Oberwolfachův problém rozkladu kompletních grafů na izomorfní 2-faktory, přisoudil Walecki Édouard Lucas v roce 1892. Waleckiho stavební místa ${ displaystyle n-1}$ vrcholů do pravidelného mnohoúhelníku a pokrývá celý graf v této podmnožině vrcholů s ${ displaystyle (n-1) / 2}$ Hamiltonovské cesty, které cikcakují napříč mnohoúhelníkem, přičemž každá cesta se od sebe navzájem otáčí násobkem ${ displaystyle pi / (n-1)}$ Cesty lze potom všechny dokončit do hamiltonovských cyklů spojením jejich konců přes zbývající vrchol.^[3]

Rozšíření vrcholu a ${ displaystyle 2k}$ -pravidelný graf do a klika z ${ displaystyle 2k}$ vrcholy, jeden pro každý koncový bod hrany na nahrazeném vrcholu, nemohou změnit, zda má graf hamiltonovský rozklad. Zadní strana tohoto procesu expanze, kdy se zhroutí klika na jeden vrchol, transformuje jakýkoli hamiltonovský rozklad ve větším grafu na hamiltonovský rozklad v původním grafu. Naopak, Waleckiho konstrukci lze použít na kliku, aby se rozšířil jakýkoli hamiltonovský rozklad menšího grafu na hamiltonovský rozklad rozšířeného grafu. Tento proces rozšiřování lze použít k výrobě libovolně velkého vertex-tranzitivní grafy a Cayleyovy grafy sudého stupně, které nemají hamiltonovské rozklady.^[4]

Směrovaný případ úplných grafů je turnaje. Odpověď na domněnku Paul Kelly od roku 1968,^[5] Daniela Kühn a Deryk Osthus v roce 2012 dokázal, že každý dostatečně velký regulérní turnaj má hamiltonovský rozklad.^[6]

Počet rozkladů

Každý 4 pravidelný neorientovaný graf má sudý počet hamiltonovských rozkladů. Silněji pro každé dva okraje ${ displaystyle e}$ a ${ displaystyle f}$ 4 pravidelného grafu, počet hamiltonovských rozkladů, ve kterých ${ displaystyle e}$ a ${ displaystyle f}$ patří do stejného cyklu je sudý. Pokud ${ displaystyle 2k}$ -pravidelný graf má hamiltonovský rozklad, má alespoň a trojitý faktoriál počet rozkladů,

{ displaystyle (3k-2) cdot (3k-5) cdots 7 cdot 4 cdot 1.}

Například 4 pravidelné grafy, které mají hamiltonovský rozklad, mají alespoň čtyři z nich; 6 pravidelných grafů, které mají hamiltonovský rozklad, mají alespoň 28 atd. Z toho vyplývá, že jediné grafy, jejichž hamiltonovské rozklady jsou jedinečné, jsou cyklické grafy.^[7]

Výpočetní složitost

Testování, zda má libovolný graf hamiltonovský rozklad, je NP-kompletní, jak v řízených, tak v neřízených případech.^[8]

The spojnicové grafy z kubické grafy jsou 4 pravidelné a mají hamiltonovský rozklad právě tehdy, pokud má základní kubický graf hamiltonovský cyklus.^[9]^[10] V důsledku toho zůstává Hamiltoniánský rozklad NP-úplný pro třídy grafů, které zahrnují spojnicové grafy tvrdých instancí Hamiltoniánský cyklus. Například Hamiltonovský rozklad je u 4 pravidelných rovinných grafů NP-úplný, protože obsahují spojnicové grafy kubických rovinných grafů. Na druhou stranu tato ekvivalence také naznačuje, že Hamiltoniánský rozklad je snadný pro 4-řádkové spojnicové grafy, když jejich podkladové kubické grafy mají snadné problémy s Hamiltonovým cyklem.

Náhodné pravidelné grafy rovnoměrného stupně téměř jistě mají hamiltoniánský rozklad a silněji existuje randomizovaný polynomiální čas algoritmus, který, když je zadán jako vstup, náhodný pravidelný graf rovnoměrného stupně, téměř jistě v něm najde hamiltonovský rozklad.^[11]

Viz také

Lineární arboricita, jiný druh omezeného rozdělení do podgrafů maximálního stupně dva

Reference

^ Bermond, J.-C. (1978), „Hamiltonovské rozklady grafů, směrované grafy a hypergrafy“, Annals of Discrete Mathematics, 3: 21–28, doi:10.1016 / S0167-5060 (08) 70494-1, ISBN 9780720408430, PAN 0505807
^ Bondy, J. A.; Häggkvist, R. (1981), „Edge-disjoint Hamiltonovy cykly ve 4-pravidelných rovinných grafech“, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007 / BF02190157, PAN 0623315
^ Alspachu, Briane (2008), „Nádherná Walecki stavba“, Bulletin Ústavu kombinatoriky a jeho aplikací, 52: 7–20, PAN 2394738
^ Bryant, Darryn; Dean, Matthew (2015), „Vertex-transitive graphs that have no Hamilton decomposition“, Journal of Combinatorial Theory, Series B, 114: 237–246, doi:10.1016 / j.jctb.2015.05.007, PAN 3354297
^ Moon, John W. (1968), Témata o turnajích, New York, Montreal, Londýn: Holt, Rinehart a Winston, cvičení 9, strana 9, PAN 0256919
^ Kühn, Daniela; Osthus, Deryk (2013), „Hamiltonovy rozklady pravidelných expandérů: důkaz Kellyho domněnky o velkých turnajích“, Pokroky v matematice, 237: 62–146, arXiv:1202.6219, doi:10.1016 / j. Cíl.2013.01.005, PAN 3028574
^ Thomason, A. G. (1978), „Hamiltonovské cykly a jedinečně zbarvitelné grafy hran“, Pokroky v teorii grafů (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, str. 259–268, PAN 0499124
^ Péroche, B. (1984), „NP-úplnost některých problémů rozdělení a zakrytí v grafech“, Diskrétní aplikovaná matematika, 8 (2): 195–208, doi:10.1016 / 0166-218X (84) 90101-X, PAN 0743024
^ Kotzig, Anton (1957), „Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades“, Československá Akademie Věd, 82: 76–92, PAN 0090815
^ Martin, Pierre (1976), „Cycles hamiltoniens dans les graphes 4-réguliers 4-contraxes“, Aequationes Mathematicae, 14 (1/2): 37–40, doi:10.1007 / BF01836203, PAN 0414442
^ Kim, Jeong Han; Wormald, Nicholas C. (2001), „Náhodné shody, které indukují Hamiltonovy cykly a hamiltonovské rozklady náhodných pravidelných grafů“, Journal of Combinatorial Theory, Series B, 81 (1): 20–44, doi:10.1006 / jctb.2000.1991, PAN 1809424

[b-1] Bermond, J.-C. (1978), „Hamiltonovské rozklady grafů, směrované grafy a hypergrafy“, Annals of Discrete Mathematics, 3: 21–28, doi:10.1016 / S0167-5060 (08) 70494-1, ISBN 9780720408430, PAN 0505807

[bh-2] Bondy, J. A.; Häggkvist, R. (1981), „Edge-disjoint Hamiltonovy cykly ve 4-pravidelných rovinných grafech“, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007 / BF02190157, PAN 0623315

[a-3] Alspachu, Briane (2008), „Nádherná Walecki stavba“, Bulletin Ústavu kombinatoriky a jeho aplikací, 52: 7–20, PAN 2394738

[bd-4] Bryant, Darryn; Dean, Matthew (2015), „Vertex-transitive graphs that have no Hamilton decomposition“, Journal of Combinatorial Theory, Series B, 114: 237–246, doi:10.1016 / j.jctb.2015.05.007, PAN 3354297

[moon-5] Moon, John W. (1968), Témata o turnajích, New York, Montreal, Londýn: Holt, Rinehart a Winston, cvičení 9, strana 9, PAN 0256919

[ko-6] Kühn, Daniela; Osthus, Deryk (2013), „Hamiltonovy rozklady pravidelných expandérů: důkaz Kellyho domněnky o velkých turnajích“, Pokroky v matematice, 237: 62–146, arXiv:1202.6219, doi:10.1016 / j. Cíl.2013.01.005, PAN 3028574

[t-7] Thomason, A. G. (1978), „Hamiltonovské cykly a jedinečně zbarvitelné grafy hran“, Pokroky v teorii grafů (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, 3, str. 259–268, PAN 0499124

[p-8] Péroche, B. (1984), „NP-úplnost některých problémů rozdělení a zakrytí v grafech“, Diskrétní aplikovaná matematika, 8 (2): 195–208, doi:10.1016 / 0166-218X (84) 90101-X, PAN 0743024

[k-9] Kotzig, Anton (1957), „Aus der Theorie der endlichen regulären Graphen dritten und vierten Grades“, Československá Akademie Věd, 82: 76–92, PAN 0090815

[m-10] Martin, Pierre (1976), „Cycles hamiltoniens dans les graphes 4-réguliers 4-contraxes“, Aequationes Mathematicae, 14 (1/2): 37–40, doi:10.1007 / BF01836203, PAN 0414442

[kw-11] Kim, Jeong Han; Wormald, Nicholas C. (2001), „Náhodné shody, které indukují Hamiltonovy cykly a hamiltonovské rozklady náhodných pravidelných grafů“, Journal of Combinatorial Theory, Series B, 81 (1): 20–44, doi:10.1006 / jctb.2000.1991, PAN 1809424

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]