Strom Xuong - Xuong tree - Wikipedia

v teorie grafů, a Strom Xuong je kostra daného grafu s vlastností, která ve zbývajícím grafu , počet připojené komponenty s lichým počtem hran je co nejmenší.[1]Jsou pojmenovány po Nguyen Huy Xuongovi, který je použil k charakterizaci buněčné vložení daného grafu, který má největší možný rod.[2]
Podle výsledků Xuong, pokud je strom Xuong a počet hran v komponentách jsou , pak maximální rod vložení je .[1][2]Kterákoli z těchto součástí má hrany, lze rozdělit na okrajové disjunktní dvě okrajové cesty, s možnou jednou další levou hranou.[3]Vložení maximálního rodu lze získat z rovinného vnoření stromu Xuong přidáním každé dvoubřité cesty k vnoření takovým způsobem, že se zvýší rod o jednu.[1][2]
Strom Xuong a z něj odvozené vložení maximálního rodu lze nalézt v jakémkoli grafu v polynomiální čas, transformací na obecnější výpočetní problém dne matroidy, problém parity matroidu pro lineární matroidy.[1][4]
Reference
- ^ A b C d Beineke, Lowell W.; Wilson, Robin J. (2009), Témata v teorii topologických grafůEncyklopedie matematiky a její aplikace, 128, Cambridge University Press, Cambridge, str. 36, doi:10.1017 / CBO9781139087223, ISBN 978-0-521-80230-7, PAN 2581536
- ^ A b C Xuong, Nguyen Huy (1979), „Jak určit maximální rod grafu“, Journal of Combinatorial Theory, Řada B, 26 (2): 217–225, doi:10.1016/0095-8956(79)90058-3, PAN 0532589
- ^ Sumner, David P. (1974), „Grafy s 1 faktory“, Proceedings of the American Mathematical SocietyAmerická matematická společnost, 42 (1): 8–12, doi:10.2307/2039666, JSTOR 2039666, PAN 0323648
- ^ Furst, Merrick L .; Gross, Jonathan L .; McGeoch, Lyle A. (1988), „Nalezení maximálního rodového grafu“, Deník ACM, 35 (3): 523–534, doi:10.1145/44483.44485, PAN 0963159, S2CID 17991210