1.2.4 Матрица весов соответствующего неориентированного графа:

Соответствующий неориентированный граф можно представить матрицей весов:

∞	2	7	∞	∞	∞	∞	∞	∞	∞	∞
∞	∞	3	8	4	∞	∞	7	∞	∞	∞
∞	∞	∞	∞	12	5	∞	∞	2	∞	∞
∞	∞	∞	∞	∞	∞	∞	6	∞	∞	∞
∞	∞	∞	∞	∞	∞	2	∞	13	∞	∞
∞	∞	∞	∞	4	∞	∞	18	∞	∞	∞
∞	∞	∞	∞	∞	∞	∞	∞	12	∞	∞
∞	∞	∞	∞	∞	6	∞	∞	∞	7	∞
∞	∞	∞	∞	6	∞	4	∞	4	1	∞
∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	15
∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	4

Примечание. Показана верхняя половина матрицы, т.к. матрица весов неориентированного графа симметрична относительно главной диагонали.

1.2.5 Описание графа Gор матрицей смежности:

∞	1	1	∞	∞	∞	∞	∞	∞	∞	∞
∞	∞	1	1	1	∞	∞	1	∞	∞	∞
∞	∞	∞	∞	1	1	∞	∞	1	∞	∞
∞	∞	∞	∞	∞	∞	∞	1	∞	∞	∞
∞	∞	∞	∞	∞	∞	1	∞	1	∞	∞
∞	∞	∞	∞	1	∞	∞	1	∞	∞	∞
∞	∞	∞	∞	∞	∞	∞	∞	1	∞	∞
∞	∞	∞	∞	∞	1	∞	∞	∞	1	∞
∞	∞	∞	∞	1	∞	1	∞	1	1	∞
∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	1
∞	∞	∞	∞	∞	∞	∞	∞	∞	∞	1

1.2.6 Степени вершин неориентированного графа:

Степени вершин рассматриваемого неориентированного графа приведены в табл.1.1

Таблица 1.1 Степенная последовательность вершин графа G

Вершина	0	1	2	3	4	5	6	7	8	9	10	11
Степень	2	4	3	1	2	2	1	2	4	1	1	2

Выбираем из таблицы наибольшую и наименьшую степени:

D_max = 1; D_min = 4.

1.3.2 Нумерация вершин графа G «поисков в глубину»:

Рассмотрим стек нумерации «поиском в глубину». Правило построения LIFO – Last In First Out. Использованы номера вершин исходного графа. Просмотренные вершины выделены жирным шрифтом, уже внесенные в стек вершины заключены в скобки.

Текущая вершина	Стек дополнения	Состояние стека
0	1,2	01,2,3
2	4,5,8	1,24,5,8
8	5,7,9,10	12458(5)7910
10	11	124587(9)(10)11
11	Пусто	124587(9)(10)11
9	(11)	124587(9)(10)11
7	6,10	1245879(10) 6
6	9	1245(8)(7)(9)(6)
5	4(7)	1245(8)(7)(9)(6)(10)(11)
4	(6),(9)	1245(8)(7)(9)(6)(10)(11)
1	2,3,4,7	1245(8)(7)(9)(6)(10)(11)3
3	(7)	1245(8)(7)(9)(6)(10)(11)3

Перенумерация:

Старые	0	2	8	10	11	9	7	6	5	4	1	3
Новые	1	2	3	4	5	6	7	8	9	10	11	12