Множества. Комбинаторика. Отношения (стр. 20 )

Матрица С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 после приведения

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

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

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

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

Графы и сети

3.1. Графы

Графом называется пара множеств (V, X), где V – множество вершин, а X – некоторое множество неупорядоченных пар элементов и из V, множество рёбер. Граф называется ориентированным (орграфом), если пары упорядочены. В этом случае их называют дугами. Граф конечен, если множества V, X конечны. Ребро вида называется петлёй. Рёбра и называются кратными. Договоримся под словом граф подразумевать, если не оговорено противное, конечный граф без кратных рёбер и без петель. Если в графе существует ребро , которое соединяет вершины а и b, то вершины а и b называют смежными, а вершину а и ребро x инцидентными. Граф называется полным, если в нём любые две вершины смежны. Полный граф с р вершинами обозначается Kp. Например,

3.1.1 Степень вершины графа

Совокупность рёбер, инцидентных вершине , называется звездой вершины . Число рёбер графа, инцидентных вершине , называется степенью вершины ; обозначение deg, т. е. deg=.

ТЕОРЕМА. Сумма степеней всех вершин графа равна удвоенному числу его рёбер, т. е. .

Доказательство. В сумме каждое ребро учтено дважды. <

Упражнения

1)  Число вершин нечётной степени в графе чётно. Докажите это.

2)  Докажите, что в любом графе, содержащем не менее двух вершин, найдутся две вершины одинаковой степени. (Указание: предположить противное, что все вершины разной степени).