m = 3 m = 4
| v1 | v2 | v3 | v4 | v5 | v6 | v1 | v2 | v3 | v4 | v5 | v6 | ||
| v1 | 0 | ¥ | 5 | 5 | 2 | 12 | v1 | 0 | 7 | 5 | 5 | 2 | 9 |
| v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 | v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 |
| v3 | ¥ | 2 | 0 | ¥ | ¥ | 4 | v3 | ¥ | 2 | 0 | ¥ | ¥ | 4 |
| v4 | ¥ | 2 | ¥ | 0 | ¥ | 4 | v4 | ¥ | 2 | ¥ | 0 | ¥ | 4 |
| v5 | ¥ | ¥ | 1 | 2 | 0 | ¥ | v5 | ¥ | 3 | 1 | 2 | 0 | 5 |
| v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 | v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 |
m = 5 m = 6
| v1 | v2 | v3 | v4 | v5 | v6 | v1 | v2 | v3 | v4 | v5 | v6 | ||
| v1 | 0 | 7 | 5 | 5 | 2 | 9 | v1 | 0 | 5 | 3 | 4 | 2 | 7 |
| v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 | v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 |
| v3 | ¥ | 2 | 0 | ¥ | ¥ | 4 | v3 | ¥ | 2 | 0 | ¥ | ¥ | 4 |
| v4 | ¥ | 2 | ¥ | 0 | ¥ | 4 | v4 | ¥ | 2 | ¥ | 0 | ¥ | 4 |
| v5 | ¥ | 3 | 1 | 2 | 0 | 5 | v5 | ¥ | 3 | 1 | 2 | 0 | 5 |
| v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 | v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 |
Матрица D:
| v1 | v2 | v3 | v4 | v5 | v6 | |
| v1 | 0 | 5 | 3 | 4 | 2 | 7 |
| v2 | ¥ | 0 | ¥ | ¥ | ¥ | 2 |
| v3 | ¥ | 2 | 0 | ¥ | ¥ | 4 |
| v4 | ¥ | 2 | ¥ | 0 | ¥ | 4 |
| v5 | ¥ | 3 | 1 | 2 | 0 | 5 |
| v6 | ¥ | ¥ | ¥ | ¥ | ¥ | 0 |
1.2. Эйлеровы цепи и циклы
Пусть G – псевдограф. Цепь (цикл) в G называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро псевдографа G.
Для того, чтобы связный псевдограф G обладал эйлеровым циклом, необходимо и достаточно, чтобы степени его вершин были четными.
Для того, чтобы связный псевдограф G обладал эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно две вершины нечетной степени. Если указанное условие выполняется, то любая эйлерова цепь псевдографа G соединяет вершины нечетной степени.
Пусть G – связный мультиграф, степени вершин которого – четные числа.
А л г о р и т м построения эйлерова цикла
Данные: матрица инцидентности В(G) мультиграфа G.
Результат: последовательность ребер, образующих эйлеров цикл.
1. Выбрать произвольную вершину v.
2. Выбрать произвольное ребро x, инцидентное v, и присвоить ему номер 1. (Назовем это ребро “пройденным”).
3. Каждое пройденное ребро вычеркивать и присваивать ему номер, на единицу больший номера предыдущего вычеркнутого ребра.
4. Находясь в вершине w, не выбирать ребра, соединяющего w с v, если только есть возможность другого выбора.
5. Находясь в вершине w, не выбирать ребра, которое является “перешейком” (при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру).
6. После того, как в графе будут занумерованы все ребра, цикл m = [xi1, xi2,…, xim], образованный ребрами с номерами от 1 до m, где m – число ребер в графе, есть эйлеров цикл.
Замечание. Прежде чем строить эйлеров цикл, проверить условие существования этого цикла.
Изменить алгоритм построения эйлерова цикла так, чтобы можно было использовать его для построения эйлеровой цепи в графе.
1.3. Гамильтоновы цепи и циклы
Пусть G – псевдограф. Цепь (цикл) в G называется гамильтоновой (гамильтоновым), если она (он) проходит через каждую вершину псевдографа G ровно один раз. Простейшим достаточным условием существования гамильтоновых цепей и циклов в графе является его полнота. Граф G называется полным, если каждая его вершина смежна со всеми остальными вершинами. Необходимым условием существования гамильтоновых цепей и циклов в графе G является связность данного графа.