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

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

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

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

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

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

, т.е.

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

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

Цикл графа 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₁). Число циклов при этом уменьшиться на еденицу. Повторяя процедуру склеивания, в итоге получим один цикл, содержащий все рёбра исходного графа – эйлеров цикл, ч.т.д.

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