Теория графов

1

4

4

6

2

2

0

1

3

3

3

0

4

0

4

0

5

1

7

5

0

1

3

0

1

2

3

4

5

1

0

0

2

2

2

0

1

3

3

3

0

4

0

4

0

5

1

7

5

0

1

3

0

Матрица С_1,2

Матрица С_1,2 после приведения

Сумма констант последнего приведения равна 4, так что

.

Теперь выберем между множествами и то, на котором минимальна функция . В нашем случае из множеств, которому соответствует меньшее из чисел (Г_{(1,4)})=15 и . Поэтому дальнейшей разработке подвергнется множество Г_{(1,4)}.

Итак, выделена определенная дуга (1,4) графа и построены новые матрицы, к которым, очевидно, можно применить описанную выше процедуру. При каждом таком повторном применении будет фиксироваться очередная дуга графа, которая в конечном итоге войдёт в искомый гамильтонов цикл (цикл коммивояжёра), если данная ветвь будет продолжена до конца и иметь минимальный вес.

В матрице С_1,1 подсчитаем веса нулей (веса нулей указаны в скобках):

	1	2	3	5
2	2		0(3)	3
3	3	0(1)		0(3)
4		4	0(4)	6
5	0(1)	1	3

Самым тяжёлым является нуль с номером (4,3), так что теперь следует рассматривать множества и .

Обратимся к первому из них. Поскольку, вычеркнув строку 4 и столбец 3 в матрице С_1,1, нужно также заменить на числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n), то в клетке с номером (3,1) надо поставить символ . Получим матрицу С_1,1,1:

1 2 5 2 2 3 3 0 0 5 0 1	1 2 5 2 0 1 3 0 0 5 0 1
Матрица С1,1,1	Матрица С1,1,1 после приведения

Для оценочной функции .

Матрица С_1,1,2 для множества :

1 2 3 5 2 2 0 3 3 3 0 0 4 4 6 5 0 1 3	1 2 3 5 2 2 0 3 3 3 0 0 4 0 2 5 0 1 3
Матрица С1,1,2	Матрица С1,1,2 после приведения

Оценочная функция . Следовательно, дальнейшей разработке подлежит . «Взвешиваем» нули в матрице С_1,1,1:

	1	2	5
2	0(1)		1
3		0(1)	0(1)
5	0(1)	1

Поскольку все нули имеют одинаковый вес, выберем любой из них; для определённости - нуль, стоящий в клетке (2,1).

Теперь речь пойдёт о множествах и .

Как и раньше, вычёркивая строку 2 и столбец 1 в матрице С_1,1,1, нужно также заменить на числа в определённых клетках так, чтобы не получалось коротких циклов (длиной меньше n). Так в клетке с номером (3,2) окажется символ .

2 5 3 0 5 1	2 5 3 0 5 0
Матрица С1,1,1,1	Матрица С1,1,1,1 после приведения

Получаем для оценочной функции .

Для множества матрица такова:

1 2 5 2 1 3 0 0 5 0 1	1 2 5 2 0 3 0 0 5 0 1
Матрица С1,1,1,2	Матрица С1,1,1,2 после приведения

Для оценочной функции

.

Получилось, что для дальнейшей разработки можно брать любое из множеств и . Но в первом случае уже получена матрица размером 22. Её нулевые клетки дают те дуги, которые с найденными ранее составляют обход коммивояжёра, причём вес этого обхода равен значению оценочной функции - 18. Вот этот обход:

(1,4)(4,3) (3,5) (5,2) (2,1) или 143521

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

Методические указания по выполнению контрольной работы

В курсе «Теория графов» изучается применение методов теории графов в прикладных задачах.

При выполнении контрольной работы необходимо придерживаться следующих правил:

1. Студент обязан делать контрольную работу только своего варианта в сроки, предусмотренные графиком.

2. Номер варианта определяется по следующей схеме

Номер варианта соответствует начальной букве фамилии студента.

Вариант №1 Вариант №2 Вариант №3 Вариант №4

А, Б, В Г, Д, Е Ж, З, И К, Л

Вариант №5 Вариант №6 Вариант №7 Вариант №8

М, Н О, П, Р С, Т, У Ф, Х, Ц

Вариант №9 Вариант №10

Ч, Ш, Щ Э, Ю, Я

3. Контрольную работу следует выполнять в ученической тетради чернилами любого цвета, кроме красного, оставляя поля (3 - 4 см) для замечаний рецензента. Рекомендуется в конце тетради указать список используемой литературы и оставить несколько чистых листов для исправлений и дополнений в соответствии с указаниями рецензента.

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

5. Перед решением задачи нужно полностью выписать ее условие. Если несколько задач имеют общую формулировку, переписывать следует только условие задачи нужного варианта. Решение каждой задачи следует сопровождать подробными ссылками на соответствующие формулы, теоремы и правила. Вычисления должны быть доведены до конечного числового результата. Ответы и выводы, полученные при решении задач, следует подчеркнуть.

6. После получения отрецензированной работы студенту необходимо исправить все отмеченные ошибки и недочеты.

Если работа возвращена на доработку, то следует переделать те задачи, на которые указывает рецензент, а при отсутствии такого указания контрольная работа должна быть выполнена заново.

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

7. Работы, выполненные без соблюдения этих правил, к зачету не принимаются и возвращаются без рецензирования для переработки.

8. На экзамен допускаются студенты, контрольная работа которых является зачтенной.

Контрольная работа содержит 6 задач. Варианты контрольной работы должны соответствовать следующей таблице:

Вариант	1	2	3	4	5	6	7	8	9	10
Номер задания	1(а), 2(а), 3(а), 4(а), 5(а), 6(а)	1(б), 2(б), 3(б), 4(б), 5(б), 6(б)	1(в), 2(в), 3(в), 4(в), 5(в), 6(в)	1(а), 2(б), 3(а), 4(б), 5(а), 6(б)	1(б), 2(а), 3(б), 4(а), 5(а), 6(в)	1(в), 2(в), 3(в), 4(в), 5(б), 6(в)	1(а), 2(а), 3(б), 4(в), 5(в), 6(б)	1(б), 2(в), 3(а), 4(а), 5(б), 6(а)	1(в), 2(а), 3(б), 4(в), 5(а), 6(б)	1(а), 2(б), 3(в), 4(б), 5(в), 6(а)

ЗАДАНИЯ ДЛЯ ДОМАШНЕЙ КОНТРОЛЬНОЙ РАБОТЫ

1. С помощью матрицы смежности найти компоненты сильной связности ориентированного графа D.

а)	б)	в)

2. С помощью алгоритма фронта волны найти расстояния в ориентированном графе D: диаметр, радиус и центры.

а)	б)	в)

Примечание: самый длинный путь в графе найти при помощи алгоритма фронта волны.

3. Найти минимальный путь в нагруженном графе по методу Форда-Беллмана.

а) из вершины в вершину	б) из вершины в вершину	в) из вершины в вершину

4. Найти Эйлерову цепь в неориентированном графе.

а)	б)	в)

5. Найти минимальное остовное дерево в неориентированном нагруженном графе.



а)	б)	в)

6. Методом ветвей и границ найти оптимальный путь коммивояжёра при следующей матрице стоимости.

1 3 4 5 1 13 7 5 2 2 8 4 7 5 3 8 4 3 6 4 5 8 1 0 5 21 6 1 4	1 2 3 4 5 1 6 4 8 7 2 6 7 11 7 3 4 7 4 3 4 8 11 4 5 5 7 7 3 5	1 2 3 4 5 1 2 2 3 3 2 2 1 1 1 3 2 1 3 3 4 3 1 3 3 5 3 1 3 3
а)	б)	в)

РЕКОМЕНДУЕМЫ СПИСОК ЛИТЕРАТУРЫ

1. Бахвалов, Н.С. Численные методы / Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков М.: Наука, 1987. -598 с.

2. Бахвалов, Н.С. Численные методы. Часть 1 / Н.С.Бахвалов М.: Наука, 1973. 631 с.

3. Самарский, А.А. Введение в численные методы / А.А.Самарский М.: Наука, 1987. 286 с.

4. Калиткин, Н.Н. Численные методы / Н.Н.Калиткин М.: Наука, 1978. 512 с.

5. Крылов, В.И. Вычислительные методы. Т. I, II / В.И.Крылов, В.В.Бобков, П.И.Монастырный М.: Наука, 1987. 600 с.

6. Житников, В.П. Линейные некорректные задачи. Верификация численных результатов. Учеб. пособие / В.П.Житников, Н.М.Шерыхалина, А.Р.Ураков Уфа: УГАТУ, 2002. 91 с.

7. Smith D.A., Ford W.F. Acceleration of linear and logarithmic convergence. - SIAM J. Numer. Anal., 1979, v. 16. P. 223-240.

8. Smith D. A., Ford W. F. Numerical comparisons of non-linear convergence accelerations. - Mathematics of Computation, 1982, v. 38, 158. P. 481-499.

9. Прудников, А.П. Интегралы и ряды / Прудников А.П., Бычков Ю.А., Маричев О.И. - М.: Наука, 1981. 800 с.

Размещено на Allbest.ru