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

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

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

Согласно результатам Xuong, если является деревом Сюонг, а количество ребер в компонентах находятся , то максимальный род вложения является .[1][2]Любой из этих компонентов, имеющий края, можно разделить на двухреберные пути с непересекающимися ребрами, возможно, с одним дополнительным левым ребром.[3]Вложение максимального рода может быть получено из плоского вложения дерева Сюонг, добавляя каждый двухреберный путь к вложению таким образом, чтобы род увеличивался на единицу.[1][2]

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

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

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