Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 5.6. Ориентированные гамильтоновы графыКонтур ориентированного графа G называется ориентированным гамильтоновым контуром G, если он содержит все его вершины. Ориентированный путь графа G называется гамильтоновым, если в нем содержатся все вершины того же графа. Ориентированным гамильтоновым графом называется граф, имеющий гамильтонов контур. Гамильтоновым контуром, например, является последовательность дуг
Рис. 5.13. а — ориентированный гамильтонов граф, б — ориентированный граф с гамильтоновым ориентированным путем, но без гамильтоновых контуров Последовательность дуг Характеризация ориентированных гамильтоновых графов в такой же степени трудна, как и в случае неориентированных гамильтоновых графов. Однако существует несколько достаточных условий, гарантирующих присутствие гамильтоновых контуров или ориентированных путей. Рассмотрим некоторые из этих условий. Ориентированный граф называется полным, если полным является неориентированный граф, лежащий в его основе. Следующая теорема принадлежит Муну [5.4]. Теорема 5.10. Пусть Доказательство. Пусть Докажем теорему индукцией по k. Допустим, что вершина и входит в контуры всех длин от 3 до Пусть С: Предположим, что некоторой сершине v, не входящей в контур С, инцидентны дуги В противном случае обозначим через S множество всех вершин, не входящих в контур С и являющихся конечными в дугах, исходящих из вершин контура С, а через Т — множество всех вершин, не входящих в контур С и являющихся начальными в дугах, заходящих в вершины того же контура. Снова, поскольку граф G сильно связный, S и Т — непусты. Кроме того, существует дуга, идущая из вершины
Рис. 5.14.
Рис. 5.15. Следствие 5.10.1. Сильно связный полный ориентированный граф гамильтонов. Приведем сейчас без доказательства очень сильную теорему, принадлежащую Гуйа-Ури. Доказательство ее исключительно сложно, его можно найти в работе [5,9]. Теорема 5.11. Пусть G — сильно связный граф на Следующее утверждение обобщает результат Дирака (следствие 3.4.1) для неориентированных графов, и его можно доказать с помощью теоремы 5.11 и упражнения 5.6. Следствие 5.11.1. Пусть 0 — ориентированный граф на Непосредственное доказательство этого результата можно найти в работе [5.6]. Завершаем этот раздел утверждением о существовании ориентированного гамильтонова пути. Теорема 5.12. Если ориентированный граф Доказательство. Рассмотрим ориентированный путь в графе G максимальной длины Повторяя эти рассуждения, получим, что
|
1 |
Оглавление
|