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

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

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

Пусть G(x) неориентированный граф с однократными ребрами без петель. Такой граф к-хроматический, если существует такое разложение множества его вершин, на к-пересекающихся классов х₁, х₂, х₃ … х_n,для которых х₁, х₂, х₃ … х_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 имеет тип цикла,

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

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

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

l ^x0 + ^eх.

Дата добавления: 2014-01-05