Нахождение гамильтонова цикла

		х1	х2	х3	х4	х5	х6	х7
	х1
	х2
	х3
R(G)=	х4
	х5
	х6
	х7

х1

х2

х7

х3

х4

х5

х6

 

Рисунок 8.2. Граф G(X, U) и его матрица соединений

Включаем в S начальную вершину S={x₁}.

Первая " возможная" вершина х₂ Гх₁, S={x₁, х₂} и т.д. до вершины х₇:

S={x₁, х₂, х₃, х₄, х₅, х₆, х₇}. Ребра (х₇, х₁) нет. Найдена гамильтонова цепь. Прибегнем к возвращению. Удалим из S вершину х₇.

S={x₁, х₂, х₃, х₄, х₅, х₆}.

У х₆ больше нет " возможных" вершин. Удалим и ее. S={x₁, х₂, х₃, х₄, х₅}.

У х₅ больше нет " возможных" вершин. Удалим ее. S={x₁, х₂, х₃, х₄}. Следующая " возможная" вершина х₆. S={x₁, х₂, х₃, х₄, х₆}.

Следующая " возможная" вершина х₅. S={x₁, х₂, х_3, х_4, х₆, х₅}.

У х₅ больше нет " возможных" вершин. Удалим ее. S={x₁, х₂, х₃, х₄, х₆}. Следующая " возможная" вершина х₇. S={x₁, х₂, х₃, х₄, х₆, х₇}.

У х₇ больше нет " возможных" вершин. Удалим из S вершину х₇.

S={x₁, х₂, х₃, х₄, х₆}. У х₆ больше нет " возможных" вершин. Удалим ее. S={x₁, х₂, х₃, х₄}. Следующая " возможная" вершина х₇. S={x₁, х₂, х₃, х₄, х₇}. Следующая " возможная" вершина х₆. S={x₁, х₂, х₃, х₄, х₇, х₆}.

Следующая " возможная" вершина х₅. S={x₁, х₂, х₃, х₄, х₇, х₆, х₅}.

Ребра (х₅, х₁) нет. Найдена гамильтонова цепь. Удаляем вершины х₄, х₇, х₆, х₅.

S={x₁, х₂, х₃}.

И т.д., пока последней не окажется вершина х₄, которая образует цикл с вершиной х₁. Гамильтонов цикл будет

S={x₁, х₂, х₃, х₅, х₆, х₇, х₄}.

На рис. 8.3 показан полученный гамильтонов цикл.

х1

х2

х7

х3

х4

х5

х6

Рисунок 8.3. Гамильтонов цикл графа G(X, U)

8.2.2. Построение графа пересечений G^'

Перенумеруем вершины графа таким образом, чтобы ребра гамильтонова цикла были внешними.

до перенумерации	х1	х2	х3	х5	х6	х7	х4
после перенумерации	х1	х2	х3	х4	х5	х6	х7

Тогда граф G (X, U) будет выглядеть так (рис. 8.4.)

		х1	х2	х3	х4	х5	х6	х7	pi
	х1		×					×
	х2			×
	х3				×
R(G)=	х4					×
	х5						×
	х6							×
	х7

 

х1

х2

х7

х3

х4

х5

х6

 

Рисунок 8.4. Граф G(X, U)

с перенумерованными вершинами и его матрица соединений

Определим p₂₆, для чего в матрице R выделим подматрицу R_26.

Ребро (х₂х₆) пересекается с ребром (х₁х₃). Строим граф пересечений G^'

u26

u13

 

Определим p₂₄, для чего в матрице R выделим подматрицу R_24.

Ребро (х₂х₄) пересекается с ребром (х₁х₃). p₂=2.

Продолжаем строить граф пересечений G^'.

u26

u13

u24

 

 

После обработки остальных ребер получим граф пересечений G^' (рис. 8.5).

u26

u13

u36

u37

u57

u35

u24

u47

1

2

3

4

5

6

7

8

G'

Число пересечений ребер графа Р(G) = p₂ + p₃ + p₄ + p₅ = 11.

 

R(G')=

 

Рисунок 8.5. Граф пересечений G’ и его матрица соединений

8.2.3. Построение семейства Ψ _{G '}

 

В первой строке матрицы R(G') находим номера нулевых элементов. Составляем список J(j) = {4, 5, 6, 7, 8}.

Для первого нулевого элемента составляем дизъюнкцию

M₁₄= r₁ Ú r₄={11110000}.

В строке M₁₄ находим номера нулевых элементов. Составляем список J’(j’) = {5, 6, 7, 8}.

Записываем дизъюнкцию

M₁₄₅= M₁₄ Ú r₅= {11111011}.

В строке M₁₄₅ находим m₆=0. Записываем дизъюнкцию

M₁₄₅₆= M₁₄₅ Ú r₆= {11111111}.

В строке M₁₄₅₆ все «1».

Построено ψ ₁={u₁₃, u₃₇, u₃₆, u₃₅}.

Из списка J’(j’) выбираем следующий элемент. Записываем дизъюнкцию

M₁₄₆= M₁₄ Ú r₆= {11110110}.

В строке M₁₄₆ находим m₈=0. Записываем дизъюнкцию

M₁₄₆₈= M₁₄₆ Ú r₈= {11111111}.

В строке M₁₄₆₈ все «1».

Построено ψ ₂={u₁₃, u₃₇, u₃₅, u₅₇}.

Из списка J’(j’) выбираем следующий элемент. Записываем дизъюнкцию

M₁₄₇= M₁₄ Ú r₇= {11111110}.

И, наконец, M₁₄₇₈= M₁₄₇ Ú r₈= {11111111}.

В строке M₁₄₇₈ все «1».

Построено ψ ₃={u₁₃, u₃₇, u₄₇, u₅₇}.

Из списка J’(j’) выбираем следующий элемент. Записываем дизъюнкцию

M₁₄₈= M₁₄ Ú r₈= {11110001}.

В строке остались не закрытые «0».

Из списка J(j) выбираем следующий нулевой элемент r₅. Составляем дизъюнкцию

M₁₅= r₁ Ú r₅={11101011}.

В строке M₁₅ находим нулевой элемент – m₆=0. Записываем дизъюнкцию

M₁₅₆= M₁₅ Ú r₆= {11101111}.

В строке остался не закрытый «0». Понятно, что «0» в четвертой позиции элементами с номерами j > 4 закрыть не удастся.

Во второй строке ищем первый нулевой элемент – r₂₃. Составляем дизъюнкцию

M₂₃= r₂ Ú r₃= {11111111}.

В строке M₂₃ все «1».

Построено ψ ₄={u₂₆, u₂₄}.

Во второй строке ищем следующий нулевой элемент – r₂₅. Составляем дизъюнкцию

M₂₅= r₂ Ú r₅= {11111011}.

И, наконец, M₂₅₆= M₂₅ Ú r₆= {11111111}.

Построено ψ ₅={u₂₆, u₃₆, u₃₅}.

Во второй строке ищем следующий нулевой элемент – r₂₆. Составляем дизъюнкцию

M₂₆= r₂ Ú r₆= {11110111}.

В строке остался не закрытый «0».

В третьей строке ищем первый нулевой элемент – r₇. Составляем дизъюнкцию

M₃₇= r₃ Ú r₇= {11111110}.

И, наконец, M₃₇₈= M₃₇ v r₈= {11111111}.

Построено ψ ₆={u₂₄, u₄₇, u₅₇}.

В третьей строке ищем следующий нулевой элемент – r₃₈. Составляем дизъюнкцию

M₃₈= r₃ Ú r₈= {1111101}.

В строке остался не закрытый «0».

Из матрицы R(G') видно, что строки с номерами j > 3 «0» в первой позиции закрыть не смогут.

Семейство максимальных внутренне устойчивых множеств Ψ _G' построено. Это

ψ ₁ ={u₁₃, u₃₇, u₃₆, u₃₅};

ψ ₂ ={u₁₃, u₃₇, u₃₅, u₅₇};

ψ ₃ ={u₁₃, u₃₇, u₄₇, u₅₇};

ψ ₄ ={u₂₆, u₂₄};

ψ ₅ ={u₂₆, u₃₆, u₃₅};

ψ ₆ ={u₂₄, u₄₇, u₅₇}.

Для каждой пары множеств вычислим значение критерия

α _{γ δ} =׀ ψ _γ ׀ + ׀ ψ _δ ׀ - ׀ ψ _γ ∩ ψ _δ ׀ .

Результаты вычислений запишем в матрицу Α = ׀ ׀ α _{γ δ} ׀ ׀.

α ₁₂=׀ ψ ₁׀ + ׀ ψ ₂׀ - ׀ ψ ₁∩ ψ ₂׀ =4+4-3=5.

α ₁₃=׀ ψ ₁׀ + ׀ ψ ₃׀ - ׀ ψ ₁∩ ψ ₃׀ =4+4-2=6 и т.д.

А=

 

 

maxα _{γ δ} = α ₁₆= α ₃₅=7, дают две пары множеств ψ ₁, ψ ₆ и ψ ₃, ψ ₅.

Возьмем множества

ψ ₁ ={u₁₃, u₃₇, u₃₆, u₃₅} и ψ ₆ ={u₂₄, u₄₇, u₅₇}.

В суграфе H, содержащем максимальное число непересекающихся ребер, ребра, вошедшие в ψ ₁, проводим внутри гамильтонова цикла, а в ψ ₆ – вне его (рис. 8.6 (а)).

х1

х2

х7

х3

х4

х5

х6

Н

х1

х2

х7

х3

х4

х5

х6

 

 

а5

б

 

Рисунок 8.6. Планарные суграфы

Удалим из Ψ _G' ребра, вошедшие в ψ ₁ и ψ ₆

ψ ₄ ={u₂₆}; ψ ₅ ={u₂₆}.

Объединим одинаковые множества, не реализованным осталось единственное ребро ψ ₄ ={u₂₆}.

Проведем его (рис. 8.6 (б)). Все ребра графа G реализованы. Толщина графа m = 2.

Если взять множества ψ ₃ ={u₁₃, u₃₇, u₄₇, u₅₇} и ψ ₅ ={u₂₆, u₃₆, u₃₅}, то не реализованным окажется ребро {u₂₄}.

Верификация. Основные понятия

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Популярное:

1. АЛГОРИТМЫ ПОСТРОЕНИЯ ЭЙЛЕРОВА И ГАМИЛЬТОНОВА ЦИКЛА
2. Высота отчуждения травостоя, продолжительность пастбищного периода по зонам, продолжительность интервалов между циклами стравливания,
3. Два цикла эгоического присвоения
4. Деление жизненного цикла на этапы
5. Задачи на использование цикла при обработке массивов.
6. Инновационный процесс осуществляется во временных и организационных рамках жизненного цикла инновационного продукта.
7. Книги из цикла «Рождение новой науки»
8. Концепция жизненного цикла товаров
9. Лекция 15. Построение тренировки в больших циклах. Этапы цикла.
10. Лекция 20 Концепция жизненного цикла товаров.
11. Лечение нарушений менструального цикла.
12. Местонахождение и координатные системы