Faktorizace grafu - Graph factorization
v teorie grafů, a faktor grafu G je překlenující podgraf, tj. podgraf, který má stejný vrchol nastavený jako G. A k-faktor grafu je rozpětí k-pravidelný podgraf, a k-faktorizace rozděluje okraje grafu na disjunktní k-faktory. Graf G se říká, že je k-faktorovatelný pokud připouští a k-faktorizace. Zejména a 1-faktor je perfektní shoda a 1-faktorizace a k-běžný graf je zbarvení hran s k barvy. A 2-faktor je sbírka cykly který překlenuje všechny vrcholy grafu.
1-faktorizace
Pokud je graf 1-faktorovatelný (tj. Má 1-faktorizaci), pak musí být a běžný graf. Ne všechny běžné grafy jsou však 1-faktorovatelné. A k-regular graph is 1-factorable if it has chromatický index k; příklady takových grafů zahrnují:
- Jakékoli pravidelné bipartitní graf.[1] Hallova věta o manželství lze použít k prokázání, že a k-pravidelný bipartitní graf obsahuje perfektní shodu. Jeden pak může odstranit perfektní shodu, aby získal (k - 1) -pravidelný bipartitní graf a opakovaně používejte stejnou úvahu.
- Žádný kompletní graf se sudým počtem uzlů (viz níže ).[2]
Existují však také k-pravidelné grafy, které mají chromatický index k + 1 a tyto grafy nejsou 1-faktorovatelné; příklady takových grafů zahrnují:
- Libovolný pravidelný graf s lichým počtem uzlů.
- The Petersenův graf.
Kompletní grafy
1-faktorizace a kompletní graf odpovídá párování v a každý s každým. 1-faktorizace úplných grafů je zvláštním případem Baranyaiova věta týkající se 1-faktorizace úplného hypergrafy.
Jedna metoda pro konstrukci 1-faktorizace úplného grafu na sudém počtu vrcholů zahrnuje umístění všech vrcholů kromě jednoho na kruh a vytvoření pravidelný mnohoúhelník, přičemž zbývající vrchol je ve středu kruhu. S tímto uspořádáním vrcholů je jedním ze způsobů konstrukce 1-faktoru grafu výběr hrany E od středu k jednomu vrcholu mnohoúhelníku spolu se všemi možnými hranami, které leží na úsečkách kolmých na E. Takto vytvořené 1-faktory tvoří 1-faktorizaci grafu.
Počet odlišných 1-faktorizací K.2, K.4, K.6, K.8, ... je 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... OEIS: A000438.
1-faktorizační domněnka
Nechat G být k-pravidelný graf s 2n uzly. Li k je dostatečně velká, je známo, že G musí být 1-faktorovatelný:
- Li k = 2n - 1 tedy G je kompletní graf K.2n, a tedy 1-faktorovatelný (viz výše ).
- Li k = 2n - 2 tedy G lze zkonstruovat odstraněním dokonalé shody z K.2n. Znovu, G je 1-faktorovatelný.
- Chetwynd & Hilton (1985) ukázat, že pokud k ≥ 12n / 7 G je 1-faktorovatelný.
The 1-faktorizační domněnka[3] je dlouhodobý dohad to říká k ≈ n je dostačující. Přesně řečeno, domněnka je:
- Li n je liché a k ≥ n, pak G je 1-faktorovatelný. Li n je sudé a k ≥ n - 1 tedy G je 1-faktorovatelný.
The přehnaná domněnka znamená domněnku 1-faktorizace.
Perfektní 1-faktorizace
A perfektní pár z 1-faktorizace je dvojice 1-faktorů, jejichž sjednocení indukuje A Hamiltonovský cyklus.
A perfektní 1-faktorizace (P1F) grafu je 1-faktorizace mající vlastnost, že každá dvojice 1-faktorů je dokonalá dvojice. Dokonalá 1-faktorizace by neměla být zaměňována s perfektní shodou (nazývanou také 1-faktor).
V roce 1964 Anton Kotzig domníval se, že každý kompletní graf K.2n kde n ≥ 2 má perfektní 1-faktorizaci. Zatím je známo, že následující grafy mají perfektní 1-faktorizaci:[4]
- nekonečná rodina úplných grafů K.2str kde str je lichý prime (Anderson a také Nakamura, samostatně),
- nekonečná rodina úplných grafů K.str + 1 kde str je zvláštní prime,
- a sporadické další výsledky, včetně K.2n kde 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Shromažďují se některé novější výsledky tady.
Pokud je kompletní graf K.n + 1 má perfektní 1-faktorizaci, pak kompletní bipartitní graf K.n,n má také perfektní 1-faktorizaci.[5]
2-faktorizace
Pokud je graf dvoufaktorový, musí být 2k-pravidelné pro celé číslo k. Julius Petersen v roce 1891 ukázal, že tato nezbytná podmínka je také dostatečná: jakákoli 2k-pravidelný graf je dvoufaktorový.[6]
Pokud je připojený graf 2k-pravidelný a má sudý počet okrajů, které také mohou být k-faktorováno, výběrem každého ze dvou faktorů jako alternativní podmnožiny okrajů Prohlídka Euler.[7] To platí pouze pro připojené grafy; odpojené protiklady zahrnují nesouvislé svazky lichých cyklů nebo kopií K.2k+1.
The Oberwolfachův problém se týká existence 2-faktorizace kompletní grafy do izomorfních podgrafů. Ptá se, které podgrafy je to možné. To je známo, když je připojený podgraf (v takovém případě se jedná o a Hamiltonovský cyklus a tento speciální případ je problémem Hamiltoniánský rozklad ), ale obecný případ zůstává nevyřešen.
Poznámky
- ^ Harary (1969), Věta 9.2, s. 85. Diestel (2005), Dodatek 2.1.3, s. 37.
- ^ Harary (1969), Věta 9.1, str. 85.
- ^ Chetwynd & Hilton (1985). Niessen (1994). Perkovic & Reed (1997). Západ.
- ^ Wallis, W. D. (1997), „16. Perfect Factorizations“, Jednofaktorizace, Matematika a její aplikace, 390 (1. vyd.), Springer USA, str. 125, doi:10.1007/978-1-4757-2564-3_16, ISBN 978-0-7923-4323-3
- ^ Bryant, Darryn; Maenhaut, Barbara M .; Wanless, Ian M. (květen 2002), „Rodina dokonalých faktorizací úplných bipartitních grafů“, Journal of Combinatorial Theory, A, 98 (2): 328–342, doi:10.1006 / jcta.2001.3240, ISSN 0097-3165
- ^ Petersen (1891), §9, s. 200. Harary (1969), Věta 9.9, s. 90. Viz Diestel (2005), Dodatek 2.1.5, s. 39 pro důkaz.
- ^ Petersen (1891), §6, s. 198.
Reference
- Bondy, John Adrian; Murty, USA (1976), Teorie grafů s aplikacemi, Severní Holandsko, ISBN 0-444-19451-7, archivovány z originál dne 13. 4. 2010, vyvoláno 2019-12-18, Oddíl 5.1: „Přiřazení“.
- Chetwynd, A. G.; Hilton, A. J. W. (1985), „Pravidelné grafy vysokého stupně jsou 1-faktorizovatelné“, Proceedings of the London Mathematical Society, 50 (2): 193–206, doi:10,1112 / plms / s3-50.2.193.
- Diestel, Reinhard (2005), Teorie grafů (3. vyd.), Springer, ISBN 3-540-26182-6, Kapitola 2: „Sladění, zakrytí a zabalení“. Elektronické vydání.
- Harary, Franku (1969), Teorie grafů, Addison-Wesley, ISBN 0-201-02787-9, Kapitola 9: „Faktorizace“.
- „One-factorization“, Encyclopedia of Mathematics, Stiskněte EMS, 2001 [1994]
- Niessen, Thomas (1994), „Jak najít přeplněné podgrafy v grafech s velkým maximálním stupněm“, Diskrétní aplikovaná matematika, 51 (1–2): 117–125, doi:10.1016 / 0166-218X (94) 90101-5.
- Perkovic, L .; Reed, B. (1997), „Okrajové barevné grafy vysokého stupně“, Diskrétní matematika, 165–166: 567–578, doi:10.1016 / S0012-365X (96) 00202-6.
- Petersen, Julius (1891), „Die Theorie der regulären graphs“, Acta Mathematica, 15: 193–220, doi:10.1007 / BF02392606.
- West, Douglas B. „1-faktorizační domněnka (1985?)“. Otevřené problémy - teorie grafů a kombinatorika. Citováno 2010-01-09.
- Weisstein, Eric W. „Graph Factor“. MathWorld.
- Weisstein, Eric W. „k-faktor“. MathWorld.
- Weisstein, Eric W. "K-faktorovatelný graf". MathWorld.
Další čtení
- Plummer, Michael D. (2007), „Grafické faktory a faktorizace: 1985–2003: Průzkum“, Diskrétní matematika, 307 (7–8): 791–821, doi:10.1016 / j.disc.2005.11.059.