В теории графов , дерево Xuong является остов данного графа со свойством, что в оставшемся графе , количество связных компонентов с нечетным числом ребер минимально. [1] Они названы в честь Нгуен Хуй Сюонга, который использовал их для характеристики клеточных вложений данного графа, имеющего наибольший возможный род . [2]
Согласно результатам Xuong, если является деревом Сюонг, а количество ребер в компонентах находятся , то максимальный род вложения является . [1] [2] Любой из этих компонентов, имеющий края, можно разделить на двухреберные пути с непересекающимися краями, возможно, с одним дополнительным левым ребром. [3] Вложение максимального рода может быть получено из плоского вложения дерева Сюонг путем добавления каждого двухреберного пути к вложению таким образом, чтобы род увеличивался на единицу. [1] [2]
Дерево Сюонг и производное от него вложение максимального рода можно найти в любом графе за полиномиальное время путем преобразования к более общей вычислительной задаче на матроидах - проблеме четности матроидов для линейных матроидов . [1] [4]
Рекомендации
- ^ а б в г Бейнеке, Лоуэлл В .; Уилсон, Робин Дж. (2009), Темы топологической теории графов , Энциклопедия математики и ее приложений, 128 , Cambridge University Press, Кембридж, стр. 36, DOI : 10,1017 / CBO9781139087223 , ISBN 978-0-521-80230-7, Руководство по ремонту 2581536
- ^ а б в Xuong, Нгуен Зуй (1979), "Как определить максимальный род графа", Журнал комбинаторной теории , серии B, 26 (2): 217-225, DOI : 10,1016 / 0095-8956 (79) 90058-3 , Руководство по ремонту 0532589
- ^ Самнер, Дэвид П. (1974), "Графы с 1-факторов", Труды Американского математического общества , Американского математического общества, 42 (1): 8-12, DOI : 10,2307 / 2039666 , JSTOR 2039666 , MR 0323648
- ^ Furst, Merrick L .; Гросс, Джонатан Л .; McGeoch, Лайл А. (1988), "Нахождение максимальной род графа вложение", Журнал ACM , 35 (3): 523-534, DOI : 10,1145 / 44483,44485 , МР 0963159 , S2CID 17991210