Суперэйлеровость графов и стягиваемость | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Математика

Опубликовано в Молодой учёный №12 (116) июнь-2 2016 г.

Дата публикации: 18.06.2016

Статья просмотрена: 116 раз

Библиографическое описание:

Маркова Н. А. Суперэйлеровость графов и стягиваемость // Молодой ученый. — 2016. — №12. — С. 32-38. — URL https://moluch.ru/archive/116/31846/ (дата обращения: 15.10.2018).



Цель данной статьи — проиллюстрировать на примерах основные определения и результаты из [1]. Основная задача, рассматриваемая в [1] — является ли граф суперэйлеровым, т. е., по определению, содержит ли граф остовный эйлеров подграф.

За далее обозначается множество вершин графа . За – множество рёбер графа . За – степень вершины в графе .

Понятие суперэйлеровости будет рассмотрено через понятие стягиваемых подграфов: если – стягиваемый подграф , тогда суперэйлеровость равносильна суперэйлеровости . Это сужает проблему суперэйлеровых графов.

Итак, введём понятие стягиваемого подграфа. Подграф графа называется стягиваемым (collapsible), если для любого чётного подмножества его вершин содержит связный подграф, множество вершин с нечетными степенями которого есть .

Пример (стягиваемого подграфа).

Рассмотрим граф . Пусть (рис. 1). Любое чётное подмножество его вершин – это либо пустое множество, либо две соседние вершины (рис. 2). Содержит ли связный подграф, множество вершин с нечётными степенями которого есть ? Да, содержит – соответствующий подграф выделен на рис 3. Следовательно, рассмотренный пример представляет собой пример стягиваемого подграфа.

Рис. 1.

Рис. 2.

Рис. 3.

Пример нестягиваемого подграфа.

Приведём пример нестягиваемого подграфа, что проиллюстрирует существенность введённого определения. Пусть снова (рис. 4). Возьмем чётное подмножество вершин (рис. 5), для которого не найдется в связного подграфа, множество вершин с нечетными степенями которого есть . Чтобы попасть в вершину необходимо пройти по угловой вершине, но степень этой вершины будет четной (рис. 6). Значит, она не попала бы в Х.

Рис. 4.

Рис. 5.

Рис. 6.

Введем определение S-подграфа. Для чётного подмножества вершин S-подграфом графа называется подграф такой, что связен, и состоит из таких вершин , степень которых в нечётна.

Запишем кратко все условия, за выполнением которых необходимо следить при работе с этим определением:

,

связан,

.

Пример S-подграфа приведён на рис. 3. Здесь .

Если для любого чётного подмножества граф имеет S-подграф, то называют стягиваемым. И это определение согласуется с определением стягиваемого подграфа, которое было дано выше.

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

Заметим, что из стягиваемости следует эйлеровость. Достаточно в определении S-подграфа взять , т. к. из этого будет следовать, что граф связен, а степени всех его вершин чётны, из чего следует эйлеровость графа.

Утверждение. Граф является суперэйлеровым тогда и только тогда, когда содержит R-подграф. Где – это множество таких вершин , степень которых в нечетна, т. е. .

Пример (иллюстрирующий утверждение).

Рассмотрим граф – рис 7. Следуя утверждению, выделяем все вершины в , степень которых нечетна (рис. 8). Получаем множество . Далее находим R-подграф графа . Он изображён на рис 9. Видим, что (рис. 10) и есть остовный эйлеров подграф графа , что и влечёт суперэйлеровость .

Рис. 7.

Рис. 8.

Рис. 9. Г – R-подграф

Рис. 10.

Теорема 1. Пусть – граф и . Если содержит остовное дерево такое, что все компоненты имеют равное количество вершин в , то имеет S-подграф.

Пример (иллюстрирующий теорему 1).

Рассмотри граф из предыдущего примера (рис.7). Уже известно, что этот граф имеет R-подграф, значит есть возможность найти остовное дерево из условия теоремы. Такое дерево изображено на рис. 11. При этом связен, а значит имеет единственную компоненту. Следовательно, условие теоремы выполнено, значит имеет R-подграф, который мы уже предъявили на рис. 9.

Рис. 11. Остовное дерево

Теорема 2.

  1. содержит два рёберно непересекающихся остовных дерева.
  2. стягиваемый.
  3. суперэйлеров.

Теорема утверждает, что .

Пример (иллюстрирующий теорему 2).

Теорема 2 представляет собой признак, по которому можно сделать вывод о суперэйлеровости графа – требуется в графе найти два рёберно непересекающихся остовных дерева. Рассмотрим граф из предыдущего примера. Первое остовное дерево представлено на рис. 11. На рис. 12 представлено ещё одно остовное дерево . Заметим, что приведённые деревья не пересекаются по рёбрам, из чего, согласно теореме 2, вновь можно сделать вывод о суперэйлеровости рассматриваемого графа.

Рис. 12. Остовное дерево

Пусть – граф, – его подграф, а – чётное подмножество . Пусть – остовный подграф такой, что . Тогда сужением называется граф, вершины которого – это компоненты . При этом отдельные вершины инцидентны такому же числу рёбер, как соответствующие компоненты в .

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

Рассмотрим введённые определения и обозначения на примере.

Пример.

Рассмотрим граф (рис. 13) и его подграф (рис. 14).

Рис. 13.

Рис. 14.

Далее нужен остовный подграф такой, что . Дополним подграф двумя вершинами и получим (рис. 15).

Рис. 15.

Рассмотрим компоненты (выделены пунктиром на рис. 16). И то, как они связаны в графе (рис. 17).

Рис. 16. Компоненты

Рис. 17. Связь компонент

Получим сужение (рис. 18).

Рис. 18. Сужение

Теперь разберём понятие . Возьмём чётное подмножество вершин в . Рассмотрим число вершин в компонентах . Выделим из них те компоненты, у которых число вершин в нечётно. Получаем искомое (рис. 19).

Рис. 19. Сужение

Теорема 3.

  1. имеет S-подграф.
  2. имеет -подграф.

Пусть – связный подграф , и пусть . Тогда .

Если ещё стягиваемый, то .

Следствие.

Если стягиваемый подграф , то суперэйлеров тогда и только тогда, когда суперэйлеров.

Литература:

  1. P. A. Catlin. Supereulerian graphs, collapsible graphs, and four-cycles // Congressus Numerantium 58 (1987), pp. 233–246.
Основные термины (генерируются автоматически): граф, стягиваемый подграф, вершина, подграф, множество вершин, компонент, связный подграф, дерево, четное подмножество, четное подмножество вершин.


Похожие статьи

Один способ генерации графа | Статья в журнале...

Пусть подграф графа .

Например, полный граф из трех вершин, вес каждого ребра равен один.

Основные термины (генерируются автоматически): вершина, ребро, граф, компонент связности, дуга, вес, массив, получившийся граф, последовательность, алгоритм.

Алгоритмические аспекты доминирования в графах

Алгоритм полного перебора анализирует все 2N различных подмножеств множества из N вершин графа на предмет того, является ли очередное подмножество доминирующим множеством графа...

Двухфазный алгоритм решения задачи о клике для разреженных...

Граф G′ = (V′, E′) называется подграфом графа G = (V, E) при условии, что V′ ⊆V, E′ ⊆E. Если множество вершин подграфа G′ есть V′, а множество ребер E′ совпадает с множеством всех ребер графаG, оба конца которых принадлежат V′, то G′ = (V′, E′) называется подграфом...

Элементы теории графов в курсе дискретной математики

теория графов, граф, задача, вершина графа, реберное покрытие графа, независимое подмножество вершин графа, доминирующее подмножество вершин графа, вершинное покрытие графа, дискретная...

Занятие «Раскраски графов» факультативного курса «Элементы...

Вершины пустого графа раскрашиваются независимо — ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно.

Разработка программного обеспечения для конструирования...

Одной из важных задач теории графов является задача раскраски вершин графа. Пусть — некоторый произвольный граф, множество будем называть красками.

Данный класс содержит условия, при которых граф является простым циклом или деревом.

Комбинаторика. Ее изучение в школе | Статья в журнале...

Всякое k-членное подмножество n-членного множества называется сочетанием из n элементов по k.

Решение: обозначим количество сторон многоугольника через n, вершин у него тоже будет n. Соединим вершины попарно отрезками, которых будет .

Методические аспекты обучения доказательству студентов...

Сумма степеней всех вершин графа есть число четное.

Основные термины (генерируются автоматически): граф, доказательство, теорема, вершина, простой цикл, связный граф, формулировка теоремы, число ребер, любой, вершина графа.

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Один способ генерации графа | Статья в журнале...

Пусть подграф графа .

Например, полный граф из трех вершин, вес каждого ребра равен один.

Основные термины (генерируются автоматически): вершина, ребро, граф, компонент связности, дуга, вес, массив, получившийся граф, последовательность, алгоритм.

Алгоритмические аспекты доминирования в графах

Алгоритм полного перебора анализирует все 2N различных подмножеств множества из N вершин графа на предмет того, является ли очередное подмножество доминирующим множеством графа...

Двухфазный алгоритм решения задачи о клике для разреженных...

Граф G′ = (V′, E′) называется подграфом графа G = (V, E) при условии, что V′ ⊆V, E′ ⊆E. Если множество вершин подграфа G′ есть V′, а множество ребер E′ совпадает с множеством всех ребер графаG, оба конца которых принадлежат V′, то G′ = (V′, E′) называется подграфом...

Элементы теории графов в курсе дискретной математики

теория графов, граф, задача, вершина графа, реберное покрытие графа, независимое подмножество вершин графа, доминирующее подмножество вершин графа, вершинное покрытие графа, дискретная...

Занятие «Раскраски графов» факультативного курса «Элементы...

Вершины пустого графа раскрашиваются независимо — ведь они не связаны между собой ребрами. Они могут быть окрашены в различные цвета или в один и тот же цвет, неважно.

Разработка программного обеспечения для конструирования...

Одной из важных задач теории графов является задача раскраски вершин графа. Пусть — некоторый произвольный граф, множество будем называть красками.

Данный класс содержит условия, при которых граф является простым циклом или деревом.

Комбинаторика. Ее изучение в школе | Статья в журнале...

Всякое k-членное подмножество n-членного множества называется сочетанием из n элементов по k.

Решение: обозначим количество сторон многоугольника через n, вершин у него тоже будет n. Соединим вершины попарно отрезками, которых будет .

Методические аспекты обучения доказательству студентов...

Сумма степеней всех вершин графа есть число четное.

Основные термины (генерируются автоматически): граф, доказательство, теорема, вершина, простой цикл, связный граф, формулировка теоремы, число ребер, любой, вершина графа.

Задать вопрос