| ВНИМАНИЕ |
Для заказа программы на графы любой сложности пишите на мой электронный адрес proglabs@mail.ru |
Как известно, гамильтонов цикл существует только в гамильтоновом графе. Поэтому встает вопрос: а как, собственно, узнать, что заданный неориентированный граф гамильтонов?
В этой статье-шпаргалке я покажу алгоритм, проверяющий заданный граф на «гамильтоновость». Этот алгоритм принято называть теоремой Оре или условием Оре.
Сама теорема Оре звучит так:
Если в заданном неориентированном графе не меньше $3$ вершин, при этом сумма степеней для любых двух несмежных вершин не меньше общего количества вершин графа, то такой граф гамильтонов.
💡 Условие Оре является достаточным условием существования гамильтонова цикла в графе.
💡 Неориентированный граф, который подчиняется теореме Оре, иногда называют графом Оре.
С точки зрения графовой символики условие Оре можно записать так:
$deg( a )\ +\ deg( b )\ \geq\ n$, где
$a,\ b$ — несмежные вершины графа;
$n$ — общее количество вершин графа;
$deg$ — обозначение степени вершины.
Покажу неориентированный невзвешенный граф, состоящий из $9$ вершин:
Рисунок — помеченный неориентированный невзвешенный граф, состоящий из $9$ вершин
➡ Интересно, а этот граф является гамильтоновым или все-таки нет?
Чтобы ответить на этот вопрос я буду действовать в соответствии с условием Оре, то есть для начала определю степень каждой вершины графа.
Рисунок — вершины графа с их степенями
Общее количество вершин в заданном графе: $n = 9$.
Хочу провести первый этап анализа, рассмотрев вершину с меткой $8$ ( на рисунке эта вершина будет зеленого цвета ). После этого обозначу на картинке все вершины несмежные с ней ( эти вершины будут серыми ). Затем посчитаю суммы степеней всех пар несмежных вершин, одной из которых является вершина $8$.
Рисунок — все несмежные вершины для вершины $8$ обозначены серым цветом
Анализ сумм степеней вершины $8$ с каждой из несмежных для нее вершин:
| Метка несмежной вершины | Сумма степеней пары вершин | Условие Оре |
| $1$ | $4 + 5 \geq 9$ |  |
| $3$ | $3 + 5 \geq 9$ |  |
| $9$ | $1 + 5 \geq 9$ | |
➡ Даже анализ первого этапа выявил, что заданный неориентированный граф негамильтонов, так как, например, сумма степеней двух несмежных вершин ( сумма степеней вершин с метками $8$ и $3$ равна $8$ ) меньше, чем общее количество вершин ( их $9$ штук ). Остальные вершины графа нет смысла проверять, так как условие Оре «сломалось» при проверке вершины с меткой $8$.
💡 Чисто логически для себя делаю такой вывод: чтобы неориентированный граф был гамильтоновым, он должен обладать крайне высокой связностью, в идеале стремиться к полному графу.
Сейчас хочу поработать со следующим помеченным неориентированным графом и на него «наложить» условие Оре:
Рисунок — помеченный неориентированный граф, состоящий из $6$ вершин
Рассчитаю степень каждой вершины рассматриваемого графа. В итоге получаю такую картину:
Рисунок — граф с обозначением степеней всех вершин ( зеленое число, стоящее рядом с вершиной )
В текущем графе всего $3$ пары несмежных вершин. Рассчитаю суммы их степеней и сравню полученные значения с общим количеством вершин графа, то есть с числом $6$:
➡ $deg( 1 ) + deg( 4 ) = 4 + 4 = 8 \geq 6$ — true.
➡ $deg( 3 ) + deg( 5 ) = 3 + 4 = 7 \geq 6$ — true.
➡ $deg( 3 ) + deg( 6 ) = 3 + 4 = 7 \geq 6$ — true.
Во все случаях выполняется требование Оре, следовательно, данный граф является гамильтоновым, то есть содержит как минимум один гамильтонов цикл.
Сейчас я визуально найду пару гамильтоновых циклов в текущем графе.
Рисунок — пример одного ( первого ) из множества гамильтоновых циклов ( $1\ -\ 2\ -\ 3\ -\ 4\ -\ 6\ -\ 5\ -\ 1$ )
Рисунок — пример еще одного ( второго ) из множества гамильтоновых циклов ( $1\ -\ 3\ -\ 4\ -\ 5\ -\ 6\ -\ 2\ -\ 1$ )
➡ Сейчас я хочу написать программу на языке Си, которая на вход принимает неориентированный граф, а в качестве ответа сообщает, выполняется ли для этого графа условие Оре, то есть является ли заданный граф гамильтоновым.
Мне потребуется матрица смежности графа, чтобы отслеживать взаимосвязи между вершинами на уровне их смежности ( соседства ). Для последнего графа матрица смежности имеет такой вид:
Рисунок — матрица смежности неориентированного графа из $6$ вершин
Также мне потребуется полная информация о степенях всех вершин заданного неориентированного графа:
| Метка вершины | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| Степень вершины | $4$ | $5$ | $3$ | $4$ | $4$ | $4$ |
➡ В этой статье я показывал, как программно определить степени вершин в неориентированном графе, который задан матрицей смежности.
В результате у меня получилась следующая программа, которая, используя условие Оре, проверяет заданный неориентированный граф на «гамильтоновость»:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
#include <stdio.h> // для ввода-вывода #include <stdlib.h> // служебные функции #include <locale.h> // русификация диалогов // количество вершин графа #define VERTEX_COUNT 6 //--------------------------------------------------------------------- // условие Оре ( проверка графа на "гамильтоновость" ) // 0 - граф негамильтонов ( условие Оре не выполняется ) // 1 - граф гамильтонов ( условие Оре выполняется ) //--------------------------------------------------------------------- int Is_Ore( const int matrix[][ VERTEX_COUNT ], const int degrees[] ) { int ivertex; // условие Оре проверяется только на графах, состоящих не менее, чем из трех вершин if ( VERTEX_COUNT < 3 ) { return 0; } // т к граф неориентированный, то достаточно для каждой пары // несмежных вершин лишь один раз найти сумму их степеней for ( ivertex = 0; ivertex < VERTEX_COUNT; ivertex++ ) { int jvertex; for ( jvertex = ivertex + 1; jvertex < VERTEX_COUNT; jvertex++ ) { // нашлась пара несмежных вершин графа, т к в матрице смежности // им соответствует 0 - нет связи if ( matrix[ ivertex ][ jvertex ] == 0 ) { // если не выполняется требование Оре, значит, прерываем всю // обработку и возвращаем из функции негативный результат if ( degrees[ ivertex ] + degrees[ jvertex ] < VERTEX_COUNT ) { return 0; } } } } // если суммы всех пар несмежных вершин оказались больше общего // количечества вершин графа, значит, условие Оре выполнилось return 1; } //--------------------------------------------------------------------- // главная функция программы ( точка входа ) //--------------------------------------------------------------------- int main( void ) { // хранит результат выполнения условия Оре int is_Ore; // фиксированная матрица смежности неориентированного графа, // рассмотренного в статье на сайте const int matrix[ VERTEX_COUNT ][ VERTEX_COUNT ] = { 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0 }; // массив хранит степени соответсвенных вершин const int degrees[ VERTEX_COUNT ] = { 4, 5, 3, 4, 4, 4 }; // русификация диалогов программы setlocale( LC_ALL, "Russian" ); // проверка заданного неориентированного графа на "гамильтоновость", накладывая на него условие Оре is_Ore = Is_Ore( matrix, degrees ); if ( is_Ore == 0 ) { printf( "Заданный граф не является гамильтоновым, так как не выполнилось условие Оре." ); } else { printf( "Заданный граф является гамильтоновым, так как выполнилось условие Оре." ); } // задержка работы программы, чтобы у пользователя была возможность просмотреть результат printf( "\n\n" ); return EXIT_SUCCESS; } |
А вот и результаты работы программы:
Рисунок — результаты работы программы
Очень важный момент: условие Оре является достаточным, но не необходимым. Это означает, если заданный граф не подчиняется условию Оре, то это еще не означает, что он не является гамильтоновым.
Вот вам пример неориентированного графа, для которого не выполняется условие Оре, но при этом он гамильтонов граф:
Рисунок — неориентированный граф, который не подчиняется условию Оре
Доказать, что этот граф не соответствует требованиям Оре элементарно. Рассмотрим две несмежные вершины, например, с метками $1$ и $4$. Степени этих вершин равны $2$. Общее количество вершин графа равно $6$. Проверяем формульно условие Оре:
$deg( 1 ) + deg( 4 ) = 2 + 2 \geq 6$ — false
➡ Условие Оре не выполняется, но при этом рассматриваемый граф гамильтонов.
Рисунок — гамильтонов граф с показом гамильтонова цикла, который не подчиняется условию Оре
Надо четко запомнить следующее: если граф подчиняется условию Оре, то он $100\%$ гамильтонов, но если граф гамильтонов, то не факт, что он подчиняется условию Оре.
➡ Пишите в комментариях, что осталось непонятным в рамках рассмотренного алгоритма — наложения условия Оре на неориентированный граф, заданный матрицей смежности. Также расскажите, при каких обстоятельствах вам приходилось прибегать к теореме Оре.
Материал подготовил Александр Георгиевич, эксперт ЕГЭ по информатике, а также специалист по динамическим структурам данных и графовым алгоритмам: стеки, деки, очереди, списки, деревья, хеш-таблицы, графы и т.п. Для записи на частную подготовку или заказа работы по программированию звонить по номеру телефона: 8(926) 610 — 61 — 95 (электронный адрес: proglabs@mail.ru).
Добавить комментарий