Дискретная математика 3 (стр. 8 из 10)

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

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

Доказательство.Необходимость. Пусть связный граф G является эйлеровым. Это значит, что существует эйлерова цепь x₁u₁x₂u₂…x_nu_nx₁, где x_iÎV(G) (множество вершин) u_iÎE(G) (множество ребер), в которой все ребра содержатся по одному разу. Такая цепь включает в себя все вершины графа G. каждая тройка цепи u_i-1x_iu_i приносит вершине x_i степень 2, а так как все ребра в цепи различные, то степени внутренних вершин четные.

Рассмотрим вершину x₁: в начале цепи ребро u₁ ей приносит степень 1, если эта вершина встречается внутри цепи, то степень ее увеличивается на 2 при каждом повторе; и в конце цепи ребро u_n приносит ей степень 1. Всего, если посчитать, степень вершины х₁ будет четной.

Достаточность. Пусть каждая вершина графа G имеет четную степень. Построим эйлерову цепь. Пусть х₁ÎV(G) – произвольная вершина. Из нее будем строить цепь, выбирая в качестве продолжения пути ребро, которое еще не пройдено. Эта цепь может закончится только в вершине х₁, так как при входе в любую другую вершину, всегда существует ребро, по которому можно из нее выйти (степени вершин четные).

Возможны два случая: 1) построенный цикл содержит все ребра графа G и тогда теорема доказана; 2) построенный цикл содержит не все ребра графа G. Тогда рассмотрим граф G₁, полученный из G удалением всех ребер, входящих в построенный цикл. Граф G₁ вновь содержит вершины только с четными степенями (так как у каждой вершины удалили по четному числу ребер). Так как G – связный граф, то в построенном цикле существует вершина инцидентная ребру графа G₁. Пусть это вершина x_kÎV(G). Построим из нее второй цикл так же, как строили предыдущий. Далее построим общий цикл, который получится из первого цикла, если включить в него второй цикл как составную часть.

#

dg 1=dg 2=dg 3=2,

dg 4=dg 5=4,

dg 6=6.

Пусть х₁=1.

Построим первый цикл следующим образом: 1е₁2е₃6е₁₁5е₁₂6е₄2е₂1.

Выбираем вершину графа G инцидентную какому-либо не пройденному ребру такую, чтобы эта вершина была в первом цикле. Это возможно, так как граф G связный.

Пусть х₂=6. Второй цикл: 6е₅3е₆4е₇1е₈5е₉4е₁₀6.

Теперь объединяем первый и второй циклы вместе, вставляя второй цикл внутрь первого, там, где стоит вершина 6.

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

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

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

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

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

1) стираем ребра по мере их прохождения. И стираем также изолированные вершины, которые при этом образуются;

2)

на каждом этапе идем по мосту только тогда, когда нет других возможностей.

# С помощью алгоритма Флёри найти эйлерову цепь в следующем графе

§7. Гамильтоновы графы.

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

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

#

Не гамильтоновый Гамильтоновый Полугамильтоновый

граф граф граф

В теореме Эйлера приведено необходимое и достаточное условие для того, чтобы связный граф был эйлеровым. Однако, для гамильтоновых графов аналогичная задача до сих пор является нерешенной.

Теорема 4 (Дирарк, 1952). Если в простом графе G с n (³3) вершинами степень любой вершины vρ(v)³

, то граф G является гамильтоновым.

§8. Деревья.

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

#21. На данном рисунке изображено ориентированное дерево. v₀ – корень ориентированного дерева.

Неориентированный лес ®

¬ Ориентированный лес

Определение 22.Основным деревом связного графа G называется дерево, являющееся основным подграфом графа G, то есть это дерево, содержащее все вершины графа G.

#22.

¬ Связный граф G

Остовные деревья

графа G®

Определение 23. Вершину v ориентированного дерева называют потомком (подлинным потомком) вершины u, если существует путь из u в v (путь ненулевой длины). В этом случае u называют предком (подлинным предком) вершины v, а если длина пути из u в v равна 1, то вершину v называют сыном вершины u, которая при этом именуется отцом вершины v. Вершину, не имеющую потомков, называют листом.

#23.

v₄, v₅ – сыновья вершины v₂, которая в свою очередь является сыном v₀ - корня дерева.

Вершины v₄ и v₅ являются подлинными потомками вершин v₀ и v₂, которые будут их подлинными предками.

v₁, v₄, v₅, v₆, v₈, v₉ – листья.

Определение 24. Ориентированное дерево, у которого каждая вершина отличная от корня, есть лист, называют кустом.

#24.

Куст

§9. Двудольные графы.

Определение 25. Граф G=(V, E) называется двудольным, если множество его вершин можно разбить на два независимых подмножества V₁ и V₂ так, что V=V₁ÈV₂ и V₁ÇV₂=Æ. Если каждая вершина из V₁ соединена с каждой вершиной из V₂, то G называется полным двудольным графом и обозначается K_{m, n}, где m – число вершин в V₁, а n – число вершин в V₂. полный двудольный граф вида K_{1, n}, называется звездным графом.

#25.

¬ Двудольный граф

Полный двудольный граф ®

¬ Звездный граф

Теорема 5. Граф G=(V, E) является двудольным тогда и только тогда, когда любой его простой цикл четной длины.

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

Достаточность. Пусть у графа G каждый цикл имеет четную длину. разобьем граф G на компоненты связности G₁, G₂, …, G_m. Пусть G_k=(V_k, E_k) и пусть аÎV_k – произвольная вершина G_k. Далее разобьем множество вершин V_k на непересекающиеся множества V_k1 и V_k2, где V_k1 – вершины, расстояние до которых от а нечетно, V_k2 – вершины, расстояние до которых от а четно. Получаем, что аÎV_k2. Множества V_k1 и V_k2 являются незавиДимыми. действительно, если предположить, что вершины b и c смежные и принадлежат одновременно одному из множеств V_k1 или V_k2, то существовал бы цикл нечетной длины:

1) Предположим, что b, cÎV_k1.

от a к b – нечетная длина,

от b к с – длина 1,

от с к а – нечетная длина.