Сюйонг дерево - Xuong tree

Дерево Сюонг. Только один компонент из ребер не-дерева (красный компонент) имеет нечетное количество ребер, минимально возможное для этого графа.

В теория графов, а Сюйонг дерево это остовное дерево ${ displaystyle T}$ данного графа ${ displaystyle G}$ со свойством, что в оставшемся графе ${ Displaystyle G-T}$ , количество связанные компоненты с нечетным количеством ребер - как можно меньше.^[1]Они названы в честь Нгуен Хай Сюонга, который использовал их для характеристики клеточные вложения данного графа, имеющего наибольшую возможную род.^[2]

Согласно результатам Xuong, если ${ displaystyle T}$ является деревом Сюонг, а количество ребер в компонентах ${ Displaystyle G-T}$ находятся ${ displaystyle m_ {1}, m_ {2}, dots, m_ {k}}$ , то максимальный род вложения ${ displaystyle G}$ является ${ displaystyle textstyle sum _ {я = 1} ^ {k} lfloor m_ {i} / 2 rfloor}$ .^[1]^[2]Любой из этих компонентов, имеющий ${ displaystyle m_ {i}}$ края, можно разделить на ${ displaystyle lfloor m_ {i} / 2 rfloor}$ двухреберные пути с непересекающимися ребрами, возможно, с одним дополнительным левым ребром.^[3]Вложение максимального рода может быть получено из плоского вложения дерева Сюонг, добавляя каждый двухреберный путь к вложению таким образом, чтобы род увеличивался на единицу.^[1]^[2]

Дерево Сюонг и производное от него вложение максимального рода можно найти в любом графе в полиномиальное время, преобразованием к более общей вычислительной задаче на матроиды, то проблема четности матроидов за линейные матроиды.^[1]^[4]

Рекомендации

^ ^а ^б ^c ^d Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (2009), Темы топологической теории графов, Энциклопедия математики и ее приложений, 128, Cambridge University Press, Кембридж, стр. 36, Дои:10.1017 / CBO9781139087223, ISBN 978-0-521-80230-7, МИСТЕР 2581536
^ ^а ^б ^c Сюонг, Нгуен Хай (1979), "Как определить максимальный род графа", Журнал комбинаторной теории, Серия B, 26 (2): 217–225, Дои:10.1016/0095-8956(79)90058-3, МИСТЕР 0532589
^ Самнер, Дэвид П. (1974), «Графики с 1-факторами», Труды Американского математического общества, Американское математическое общество, 42 (1): 8–12, Дои:10.2307/2039666, JSTOR 2039666, МИСТЕР 0323648
^ Furst, Merrick L .; Гросс, Джонатан Л .; МакГеоч, Лайл А. (1988), "Поиск вложения графа максимального рода", Журнал ACM, 35 (3): 523–534, Дои:10.1145/44483.44485, МИСТЕР 0963159, S2CID 17991210

[bw-1] а ^б ^c ^d Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (2009), Темы топологической теории графов, Энциклопедия математики и ее приложений, 128, Cambridge University Press, Кембридж, стр. 36, Дои:10.1017 / CBO9781139087223, ISBN 978-0-521-80230-7, МИСТЕР 2581536

[x-2] а ^б ^c Сюонг, Нгуен Хай (1979), "Как определить максимальный род графа", Журнал комбинаторной теории, Серия B, 26 (2): 217–225, Дои:10.1016/0095-8956(79)90058-3, МИСТЕР 0532589

[s-3] Самнер, Дэвид П. (1974), «Графики с 1-факторами», Труды Американского математического общества, Американское математическое общество, 42 (1): 8–12, Дои:10.2307/2039666, JSTOR 2039666, МИСТЕР 0323648

[fgm-4] Furst, Merrick L .; Гросс, Джонатан Л .; МакГеоч, Лайл А. (1988), "Поиск вложения графа максимального рода", Журнал ACM, 35 (3): 523–534, Дои:10.1145/44483.44485, МИСТЕР 0963159, S2CID 17991210

[1]

[2]

[3]

[4]