“Xuong tree”的意思、由来-开放百科全书

In graph theory, a Xuong tree is a spanning tree

of a given graph

with the property that, in the remaining graph

, the number of connected components with an odd number of edges is as small as possible.{{r|bw}}

They are named after Nguyen Huy Xuong, who used them to characterize the cellular embeddings of a given graph having the largest possible genus.{{r|x}}

and the numbers of edges in the components of

are

, then the maximum genus of an embedding of

.{{r|bw|x}}

Any one of these components, having

edges, can be partitioned into

edge-disjoint two-edge paths, with possibly one additional left-over edge.{{r|s}}

An embedding of maximum genus may be obtained from a planar embedding of the Xuong tree by adding each two-edge path to the embedding in such a way that it increases the genus by one.{{r|bw|x}}

A Xuong tree, and a maximum-genus embedding derived from it, may be found in any graph in polynomial time, by a transformation to a more general computational problem on matroids, the matroid parity problem for linear matroids.{{r|bw|fgm}}

References

1. ^{{citation | last1 = Furst | first1 = Merrick L. | last2 = Gross | first2 = Jonathan L. | last3 = McGeoch | first3 = Lyle A. | doi = 10.1145/44483.44485 | issue = 3 | journal = Journal of the ACM | mr = 963159 | pages = 523–534 | title = Finding a maximum-genus graph imbedding | volume = 35 | year = 1988}}
2. ^{{Citation | last = Sumner | first = David P. | authorlink = David Sumner | doi = 10.2307/2039666 | mr = 0323648 | journal = Proceedings of the American Mathematical Society | pages = 8–12 | title = Graphs with 1-factors | volume = 42 | year = 1974 | issue = 1 | publisher = American Mathematical Society | jstor = 2039666}}
3. ^{{citation | last = Xuong | first = Nguyen Huy | doi = 10.1016/0095-8956(79)90058-3 | issue = 2 | journal = Journal of Combinatorial Theory | mr = 532589 | pages = 217–225 | series = Series B | title = How to determine the maximum genus of a graph | volume = 26 | year = 1979}}