Диаметр, радиус, центр графа.

Пусть G – конечный неориентированный граф. Тогда можно определить его диаметр d(G)=max d(v¢,v²). Кратчайшие простые цепи, связывающие вершины v¢,v²ÎG с максимальным расстоянием между ними, называются диаметральными простыми цепями.

Пусть v – произвольная вершина рассматриваемого графа G. Максимальным удалением в графе G от вершины v называется величина r(v)=max d(v,v¢). Вершина v называется центром графа G, если максимальное удаление от нее принимает минимальное значение r(G)=min r(v¢). Максимальное удаление r(G) от центра называется радиусом графа, а любая кратчайшая цепь от центра v до максимально удаленной от него вершины v¢ - радиальной цепью.

Центр не обязательно должен быть единственным. Например, в полном неориентированном графе K(V), в котором любые две различные вершины v¢,v²ÎV соединены ребром, радиус равен единице и любая вершина vÎV является центром.

Произведение графов.

Прямое произведение графов.

Прямые произведения графов. Пусть даны графы G₁и G₂ с множествами вершин V₁и V₂. У прямого произведения этих графов F = G₁×G₂ множеством вершин является прямое произведение V = V₁×V₂. Ребра произведения могут быть определены различными способами.

При одном из определений в произведении Fграфов G₁и G₂ребро имеется тогда, когда в графе G₁есть ребро или в графе G₂ — . В другом опре­делении для этого требуется существование обоих этих ребер. В первом случае элементы матрицы смежности опре­деляются формулой во втором . Таким образом, в обоих случаях матрица смежности произведения является тензорным произведением матриц смежности сомножителей, но в первом случае произведение элементов матрицы понимается как логическая сумма (или), а во втором -— как логическое (и обычное) произведение (и).

Чаще всего используется третье определение, согласно которому ребро существует в тех и только тех случаях, когда в графах G₁ и G₂ есть соответственно ребра и или , а в графе G₂ есть ребро или, наконец, в графе G₁есть ребро , а . Пусть , где E — единичная матрица, а — матрица смежности рассматриваемого графа:

 

Тогда матрица смежности прямого произведения гра­фов G₁и G₂ при таком определении равна

, т.е.

Аналогично определяется прямое произведение лю­бого множества графов.

 

Эйлеровы циклы.

Цикл графа G, содержащий все его рёбра, наз. эйлеровым. Граф, имеющий эйлеров цикл наз. эйлеровым.

Терорема.

Для каждого связного графа G следующие условия эквивалентны:

1. G – эйлеров граф.

2. Каждая вершина графа G имеет чётную степень.

3. Мн-во рёбер графа можно разбить на простые циклы, т.е. U=È^k_i=1 u_i (u_i Çu_j=Æ, (i¹j), u_i=Æ).

Доказательство.

Пусть G – эйлеров граф. Покажем, что каждая вершина имеет чётную степень. Каждая вершина простого цикла имеет степень 2. Поэтому, если в графе G существует эйлеров цикл, то каждая вершина должна иметь чётную степень.

Пусть каждая вершина имеет чётную степень. Выбираем произвольную вершину графа i₁ и движемся от неё по ребру к смежной вершине i₂, и т.д. каждый раз выбирая новое ребро. Т.к. граф связен, число рёбер в графе конечно и войдя в вершину по некоторому ребру мы можем выйти по другому, то через некоторое число шагов какая-то вершина i_k повторится. Тогда i₁,i₂,…,i_k,i₁ образует простой цикл в исодном графе (u₁). Удалим рёбра этого цикла из исходного графа. Новом графе каждая не изолированя вершина имеет чётную степень, поэтому процедуру выделения простых циклов можно применять к каждой компоненте связности, отличной от изолированой вершины. Через некоторое число шагов мы получим исх. разбиение.

Пусть закдано разбиение U=È^k_i=1 u_i. Покажем, что $ эйлеров цикл. Т.к. G – связный граф, то найдутся два простых цикла имеющих общую вершину эти два цикла можно объеденить (склеить) в один цикл. Пусть u’ и u’’ имеют общую вершину k. u’=(j₁,j₂,…,j_l-1,k,j₁₊₁,…,j_m,j₁), u’’=(t₁,t₂,…,t_d-1,k,t_d+1,…,t_f,t₁), u*=(j₁,j₂,…,j_l-1,k,t_d-1,…,t₁,t_f,t_f-1,…,t_d+1,k,j₁₊₁,…,j_m,j₁). Число циклов при этом уменьшиться на еденицу. Повторяя процедуру склеивания, в итоге получим один цикл, содержащий все рёбра исходного графа – эйлеров цикл, ч.т.д.

Док-во данной теоремы можно использовать в качестве алгоритма при построении эйлерового цикла, если он существует.

Теорема Эйлера.

Теорема:

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

Необходимость:

В несвязанном графе каждый цикл принадлежит какой-либо его мвязанной части, т.е. не проходит через все его ребра (кроме случая, когда все компоненты связности графа, кроме одной, - изолированные вершины). Кроме того, каждый раз, когда эйлеров цикл приходит в какую-нибудь вершину, он должен выйти из нее по другому ребру, т.е. инцидентные вершинам ребра можно разбить на пары соседних в эйлеровом цикле. Исключением являются ребра, инцидентные началу эйлерова цикла, совпадающему с его концом. Сначала цикл выходит из этой вершины по какому-либо ребру. Затем он, возможно, несколько раз возвращается в эту вершину, каждый раз входя по новому ребру и выходя так же по новому, но другому ребру. В конце концов он возвращается в исходную вершину по не затронутому ранее ребру. Таким образом, и в этом случае инцидентные этой вершине ребра также распадаются на пары соседних в эйлеровом цикле, но одна из этих пар состоит из ребра, проходимого в начале процесса, и другого, замыкающего этот процесс.

Достаточность:

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

Описанный ранее процесс построения цикла может закончиться лишь в той вершине, откуда он начинался, но при этом не обязательно, чтобы он проходил через все ребра графа. Принадлежащие ему ребра порождают связную часть P графа G, в которой степени всех вершин четны. Значит, они четны и для разности G\P. Так как граф G связен, в дополнении G\P существует хотя бы одна вершина v¢, принадлежащая также части Р. Начиная с этой вершины, можно провести, как и ранее, построение цикла Р¢ в G\P, кончающегося в вершине v¢.

Эта вершина, кроме того, разбивает цикл Р на два участка Р₁ с началом v и концом v¢ и Р₂ с началом v¢ и концом v. Тогда Р₁ÈР¢ÈР₂ – также цикл, начинающийся в вершине v, но имеющий большее число ребер. Если и этот цикл не проходит через все ребра, этот процесс расширения цикла можно повторить. Каждый раз число ребер в цикле увеличивается не менее чем на два, значит, в конце концов эйлеров цикл будет построен.

 

Эйлеровы цепи.

Так называется цепь, включающая все ребра данного конечного неориентированного графа G, но имеющая различные начало v¢ и конец v². Чтобы в графе существовала эйлерова цепь, необходимы его связность и четность всех вершин, кроме начальной v¢ и конечной v². Последние две вершины должны иметь нечетные степени: из v¢ мы лишний раз выходим, а в v² лишний раз входим. Эти условия достаточны для существования эйлеровой цепи. Можно искать наименьшее число не пересекающихся по ребрам цепей, покрывающих конечный связный граф G. Пусть G не является эйлеровы графом, k – число его вершин нечетной степени. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих цепей. Следовательно, число последних не меньше, чем k/2. Но ограничиться k/2 цепями не так трудно. Соединим вершины нечетной степени попарно k/2 ребрами произвольным образом. Тогда степень каждой их этих вершин увеличится на единицу и станет четной. Получится эйлеров граф, в котором существует эйлеров цикл. Выбросим теперь обратно присоединенные ребра. При выбрасывании первого ребра эйлеров цикл превратиться в эйлорову цепь, а при выбрасывании каждой следующей цепи одна из возникших к этому моменту цепей разобъется на 2 части. Таким образом, общее число этих цепей станет k/2. При построении никогда не выбрасываются соседние по эйлерову циклу ребра.

 

Гамильтоновы циклы.

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

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

Иногда можно построить проходящую через все вер­шины графа простую цепь с началом и концом в различных заданных вершинах V ', V" С. Такая цепь тоже называется гамильтоновой.