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

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

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

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

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

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

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

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

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