Дерево Хоайна — это остовное дерево заданного графа со свойством, что в оставшемся графе число связных компонент с нечётным числом рёбер как можно меньше. Деревья названы именем Нгуен Хюи Хоайна, который использовал их для описания клеточных вложений заданного графа, имеющих наибольший возможный род.
Дерево Хоайна и род вложения Согласно результатам Хоайна, если является деревом Хоайна и число рёбер в компонентах равно , то максимальный род вложения равен .
Любая из этих компонент, имеющая рёбер, может быть разбита на рёберно непересекающихся путей длиной два, при этом, возможно, останется одно ребро.
Вложение с максимальным родом может быть получено из планарного вложения Хоайна путём добавления каждого пути длиной два так, что это добавление увеличивает род на единицу.
Сложность вычислений Дерево Хоайна и вложение с максимальным родом, полученное из него, может быть найдено в любом графе за полиномиальное время путём преобразования к более общей вычислительной задаче на матроидах, для .
Примечания
Категория:Остовное дерево Категория:Топологическая теория графов