Признаки существования гамильтоновых циклов, путей и контуров

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

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

Теорема (условие Дирака). Если число вершин графа не менее трех и степень любой вершины не менее , то граф является гамильтоновым.

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

Теорема Бонди-Хватала. Пусть для упорядоченной по возрастанию последовательности степеней вершин , , графа выполнены импликации , , тогда – гамильтонов граф.

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

Следствие. Если граф либо эйлеров, либо гамильтонов, то реберный граф гамильтонов.

Теорема (признак Кенига). В полном орграфе (любая пара вершин которого соединяется хотя бы в одном направлении) всегда существует гамильтонов путь.

54 Цикломатика графів. Цикломатичне число та його властивості. Цикломатична матриця. Базис циклів. Алгоритм побудови базису циклів.

Маршруты, цепи, циклы,(пути, контуры - орграфы).

Граф называется ациклическим, если он не содержит циклов

Каркас (остов) – это максимальный подграф без циклов.

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

Хордой остова в связном графе называется всякое ребро графа, не принадлежащее . Любой подграф, который состоит из хорды и остова, имеет точно один цикл.

Кодерево графа – такой подграф графа, который содержит все его вершины и те ребра, которые не вошли в остов.

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

В случае связного графа , следовательно, .

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

Система циклов графа называется полной, если любой цикл данного графа представляется в виде линейной комбинации циклов из этой системы.

Базисом циклов графа называется любая полная линейно независимая система циклов данного графа.