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

  • Татьяна Анатольевна Макаровских ФГАОУ ВО «Южно-Уральский государственный университет» (ЮУрГУ)

Аннотация

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

Биография автора

Татьяна Анатольевна Макаровских, ФГАОУ ВО «Южно-Уральский государственный университет» (ЮУрГУ)
доц. каф. математического и компьютерного моделирования ЮУрГУ. Дипл. мат.-инж. (Южно-Уральский гос. ун-т, 2003). к-т физ.-мат. наук по теор. осн. инф. (ВЦ РАН, 2006). Иссл. в обл. теории графов и алгоритмизации.
Опубликована
2017-20-06
Как цитировать
МАКАРОВСКИХ, Татьяна Анатольевна. Оценка мощности ОЕ-покрытия плоского графа. Вестник УГАТУ, [S.l.], v. 21, n. 2, p. 112-118, июнь 2017. ISSN 1992-6502. Доступно на: <http://journal.ugatu.ac.ru/index.php/Vestnik/article/view/36>. Дата доступа: 21 сен. 2017
Раздел
ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ