Маршруты, цепи и циклы. Расстояния, диаметры, центры. Обходы. Разделяющие множества и разрезы

Маршрут, в котором совпадают начальная и конечная вершины, т.е. , называется циклическим (замкнутым).

Маршрут, в котором все ребра разные называется цепью (т.е. каждое ребро в нем встречается не более одного раза).

Цепь, в которой все вершины, кроме может быть первой и последней, разные называется простой цепью (т.е. каждая вершина и ребро в нем встречается не более одного раза).

Циклический (замкнутый) маршрут называется циклом, если он является цепью (т.е. все ребра в нем разные), и простым циклом, если эта цепь простая (т.е. и все вершины кроме первой и последней, разные).

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

Лемма:Если степень всех вершин в графе больше 1 (больше или равна 2), то граф обязательно содержит цикл.

Вершины  и  называются связными, если существует маршрут с началом в  и концом в .

Утверждение: Связанные маршрутом вершины связаны также и простой цепью.

Утверждение: Отношение связности вершин графа является отношением эквивалентности и определяет разбиение множества вершин графа на непересекающиеся подмножества .

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

Граф G называется связным, если все его вершины связаны между собой. Очевидно, что все подграфы G(V_i) этого графа связны и называются связными компонентами графа.

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

Диаметром связного графа D(G) называется расстояние между двумя наиболее удаленными друг от друга вершинами.

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

Теорема Эйлера: Конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны.

Эйлерова цепь (полуэйлеровый граф) – цепь, включающая все ребра данного конечного н-графа G, но имеющая различные начало v´ и конец v´´, т.е. это граф, в котором если существует маршрут без повторения ребер (эйлеров путь), обходящий все ребра графа ровно один раз.

Эйлеров (и полуэйлеров) граф можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги)

Теорема Эйлера (2): Конечноый н-граф G будет полуэйлеровым (в нем существует эйлерова цепь), тогда и только тогда, когда он связный и четность степеней всех вершин, кроме начальной v´ и конечной v´´ (v´ и v´´должны иметь нечетные степени).

Чтобы в конечном орграфе существовал эйлеров цикл, необходимы и достаточны его связность, а также равенство степеней вершин этого графа по входящим и выходящим ребрам, т.е. ρ₁ (v) = ρ₂ (v), ∀ v ∈ G.

Алгоритм Флери нахождения эйлерова цикла:

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

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

Гамильтонова цепь – простая цепь, проходящая через все вершины графа, с началом и концом в разных вершинах v₁, v₂ ∈ G.

Кратко рассмотрим проблему, связанную с возможным обходом всех вершин в графе: существует ли в данном (связном) графе цикл (или маршрут), обходящий каждую вершину (кроме первой) только один раз. Если такой цикл (маршрут) существует (в этом случае такой цикл будет контуром, а маршрут – путем), то граф называется гамильтоновым (полугамильтоновым),и соответствующий цикл (путь) также называют гамильтоновым циклом (путем). Несмотря на сходство постановки задач для гамильтоновых графов с эйлеровыми, “хорошего” решения для гамильтоновых графов нет. Вообще, о гамильтоновых графах известно очень мало. В основном – это теоремы типа “если в графе достаточное число ребер, то он гамильтонов”. Ясно, что теоремы такого типа не могут дать критерия гамильтонова графа, поскольку в графах такого типа вершин может быть очень много, а ребер сравнительно мало.

Приведем без доказательства самую известную теорему.

Теорема(Дирак, 1952). Если в связном графе с п вершинами (при n³3) степени всех вершин больше или равны п/2, то граф гамильтонов.

УПРАЖНЕНИЯ

1. Определить, что представляют собой последовательности вершин для графа, представленного на рисунке.

1) 1 – 2 – 3 – 4 – 2 – 5 ;

2) 1 – 2 – 3 – 4 – 7 – 5 ;                

3) 1 – 2 – 5      ;                          

4) 1 – 2 – 3 – 4 – 2 – 5 – 6 – 1;              

5) 1 – 2 – 5 – 6 – 1 .

1. Для графа, приведенного на рисунке построить маршрут, проходящий через вершину а: 1) три раза; 2) два раза; 3) один раз. Какими свойствами обладает этот маршрут.

Рис.1                           Рис.2                               Рис.3

2. Для графа, приведенного на рисунке найти построить: 1) маршрут общего вида, 2) цепь, 3) простую цепь, 4) циклический маршрут общего вида, 5) цикл, 6) простой цикл.

Рис.1                                                       Рис.2

3. Для графа, приведенного на рисунке найти: 1) расстояния между вершинами; 2) диаметр; 3) все диаметральные цепи; 4) расстояние от вершины до наиболее удаленной вершины; 5) центры; 6) все радиальные цепи.

Рис.1                                                 Рис.2

4. Для графа, приведенного на рисунке указать разделяющее множество ребер при удалении которого из графа, он распадется на компоненты связности, с множествами вершин  и  для рис. 1), 2), 3); с множествами вершин  и  для рис. 4), 5), 6).

Является ли это множество разрезом? Если является, то указать множество, которое являться разрезом не будет. Если не является, то указать разрез.

Рис. 1                                              Рис.2

Рис. 3                                              Рис.4

Рис. 5                                             Рис.6

5. Для графа, приведенного на рисунке определить, будет ли он Эйлеровым, Гамильтоновым. Если да, то построить эйлеров, гамильтонов цикл.

Рис.1                                 Рис.2                             Рис.3

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

7. Убедится в том, что граф, приведенный на рисунке, эйлеров и найти эйлеров цикл, пользуясь алгоритмом Флери.

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

9. Для графа, приведенного на рисунке найти кратчайший путь между вершинами a и b.

Рис.1                             Рис.2                               Рис.3

10. Какими свойствами обладает отношение связанности вершин н-графа на рисунке? Чему равно число связных компонент графа G?

Для четырех графов на рисунке определить расстояния между вершинами. Какие вершины являются центрами графов? Чему равны радиусы и диаметры графов?

Деревья, их свойства.