Дерево Хоайна

Дерево Хоайна. Только одна компонента из не принадлежащих дереву рёбер (красная компонента) имеет нечётное число рёбер, минимальное для этого графа.

Дерево Хоайна — это остовное дерево $T$ заданного графа $G$ со свойством, что в оставшемся графе $G-T$ число связных компонент с нечётным числом рёбер как можно меньшеШаблон:R. Деревья названы именем Нгуен Хюи Хоайна, который использовал их для описания клеточных вложений заданного графа, имеющих наибольший возможный родШаблон:R.

Дерево Хоайна и род вложения

Согласно результатам Хоайна, если $T$ является деревом Хоайна и число рёбер в компонентах $G-T$ равно $m_1,m_2,\dots ,m_k$, то максимальный род вложения $G$ равен ${\sum }_{i=1}^k\lfloor m_i/2\rfloor$Шаблон:R.

Любая из этих компонент, имеющая $m_i$ рёбер, может быть разбита на $\lfloor m_i/2\rfloor$ рёберно непересекающихся путей длиной два, при этом, возможно, останется одно реброШаблон:R.

Вложение с максимальным родом может быть получено из планарного вложения Хоайна путём добавления каждого пути длиной два так, что это добавление увеличивает род на единицуШаблон:R.

Сложность вычислений

Дерево Хоайна и вложение с максимальным родом, полученное из него, может быть найдено в любом графе за полиномиальное время путём преобразования к более общей вычислительной задаче на матроидах, Шаблон:Не переведено 5 для Шаблон:Не переведено 5Шаблон:R.