Strom Xuong - Xuong tree - Wikipedia

Strom Xuong. Pouze jedna složka hran bez stromu (červená složka) má lichý počet hran, což je pro tento graf minimum.

v teorie grafů, a Strom Xuong je kostra ${ displaystyle T}$ daného grafu ${ displaystyle G}$ s vlastností, která ve zbývajícím grafu ${ displaystyle G-T}$, 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 ${ displaystyle T}$ je strom Xuong a počet hran v komponentách ${ displaystyle G-T}$ jsou ${ displaystyle m_ {1}, m_ {2}, tečky, m_ {k}}$, pak maximální rod vložení ${ displaystyle G}$ je ${ displaystyle textstyle sum _ {i = 1} ^ {k} lfloor m_ {i} / 2 rfloor}$.^[1][2]Kterákoli z těchto součástí má ${ displaystyle m_ {i}}$ hrany, lze rozdělit na ${ displaystyle lfloor m_ {i} / 2 rfloor}$ 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