Оценка мощности ОЕ-покрытия плоского графа

Аннотация

В статье рассматриваются оценки количества цепей в эйлеровом ОЕ-покрытии плоского графа цепями. Под эйлеровым ОЕ-покрытием понимается такое минимальное по мощности упорядоченное множество реберно-непересекающихся цепей, для которых выполнено условие отсутствия пересечения внутренности цикла из ребер пройденной части маршрута с ребрами непройденной части. В соответствии с теоремой Листинга–Люка минимальная мощность покрытия графа реберно-непересекающимися цепями равна k, где 2k – число вершин нечетной степени. Ранее автором показано, что мощность эйлерова OE-покрытия плоского графа без мостов равна k, если хотя бы одна вершина нечетной степени инцидентна внешней грани и k+1, в противном случае. В данной работе показано, что точная верхняя оценка мощности эйлерова ОЕ-покрытия равна 2k.