Гамильтоновы цепи, циклы и пути.

Эйлеровы цепи, циклы, контуры.

Хроматические графы.

Пусть G(x) неориентированный граф с однократными ребрами без петель. Такой граф к-хроматический, если существует такое разложение множества его вершин, на к-пересекающихся классов х1 , х2 , х3 … хn ,для которых х1 , х2 , х3 … хn хк = х, хi хj = , что подтверждает то, что вершины в каждом классе независимы.

Представление ① называется к - раскраской графа G(x). Раскраска осуществляется в к – цветов, таким образом, чтобы смежные вершины были окрашены в разные цвета. Но было доказано, на примере раскраски карты, что любой плоский граф, которым является карта, можно раскрасить в пять цветов, при этом гипотеза о четырёх красках не будет опровергнута.

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

Теорема 1: Конечный граф G(x) является эйлеровым, когда он связен и все его локальные степени чётны.

Необходимость первого условия очевидна; для второго условия – если в процессе движения попали в одну и ту же вершину, то каждому входящему ребру будет соответствовать своя вершина.

Достаточность: Предположим, граф связен и все его локальные степени чётны, будем строить цепь до тех пор, пока это возможно. Остановимся в начальной вершине, так как локальная степень нечётна. Предположим, что цепи содержат не все рёбра, поскольку граф связен, то существует хj , которое инцидентна рёбрам графа. Граф G(x) имеет все чётные локальные степени.

Теорема 2: Пусть G(x) конечный, связный неориентированный граф, имеющий к – вершин с нечётной степенью. Тогда минимальное число непересекающихся по рёбрам простых цепей, покрывающих этот граф = к\2.

Каждая вершина нечётной цепи должна быть концом цепи. Общее число цепей, не больше, чем к\2. Этого количества цепей достаточно для покрытия графа.

Теорема 3: Пусть G(x) конечный связный ориентированный граф. Для того, чтобы существовал простой контур, содержащий все рёбра G(x), необходимо и достаточно, чтобы полустепени захода и исхода совпадали для каждой вершины, то есть

х ’(х) = ”(х)

 

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

Гамильтоновой цепью называется элементарная цепь неориентированного графа.

В ориентированных графах аналогично определение путей и контуров.

Нужно построить граф Н = (х, ∆) в ориентированном графе G(x, Г), в котором полустепени захода и исхода в каждой вершине равны единице. Такой граф называется фактором.

Гамильтонов цикл, в силу элементарности и отсутствия пересечений, является фактором.

Фактор может состоять из нескольких контуров.

Теорема 1: Полная элементарная цепь длины l имеет тип цикла,

если 1х + х l +1.

Теорема 2: Длиннейшая элементарная цепь А в G может иметь тип цикла, если граф имеет гамильтонов цикл.

Теорема 3: В связном графе либо есть гамильтонов цикл, либо длина его максимальных цепей удовлетворяет неравенству:

l x0 + eх.