WikiDer > Дерево Сюонг - Википедия

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

В теория графов, а Сюйонг дерево это остовное дерево ${ 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]

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