Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [ 51 ] 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

ВОЙ вершины с меньшим индексом к вершине с большим индексом):

3 4

0 0

1 1

0 -

-1 0

0 -1

0 0

Удаляя, например, строку х^ получим матрицу Ь Произведение матриц -Во выглядит так:

1 2

2 -1

в,-в1 =

-1 3 0 -1

0 -1

0 0

Определитель \Вд-В1 равен 21. Следовательно, по теореме 1 число остовных деревьев данного графа равно 21.

2.4. Граф остовов

Каждому остову графа G сопоставим определенную вершину (нового графа). Две вершины в новом графе соединяются ребром только тогда, когда соответствующие им остовы графа G являются соседними (т. е. расстояние между этими остовами, определяемое в соответствии с разд. 2.1, равно единице). Граф, построенный таким образом, называется графом остовов (графа G). Для графа G, изображенного на рис. 7.10 (а), полный список остовов приведен на рис. 7.10 (б), а граф остовов - на рис. 7.10 (в).

Каммингс [15] и Шэнк [51] доказали, что граф остовов любого связного графа является гамильтоновым. Позже Киси и Кадзита-ни [37, 38] и Камаз [33] разработали методы нахождения гамиль-тоновых циклов в графе остовов (и, следовательно, методы построения всех остовов графа G). Эти методы представляют в основном теоретический интерес и не эффективны с вычислительной точки зрения.




Рис. 7.10. Граф G и его граф остовов, (а) Граф G. (б) Остовы графа G. (в) Граф остовов графа G.

3. Кратчайший остов (SST) графа

Рассмотрим взвешенный связный неориентированный граф G = {X, А); вес ребра (xi, Xj) обозначим с,. Из большого числа остовов графа нужно найти один, у которого сумма весов ребер наименьшая. Такая задача возникает, например, в том случае, когда вершины являются клеммами электрической сети, которые должны быть соединены друг с другом с помощью проводов наименьшей общей длины (для уменьшения уровня наводок). Другой пример: вершины представляют города, которые нужно связать




2 (а)


Рис. 7.11.

(а) Граф G.

(б) Дерево кратчайших путей из х^.

(в) Кратчайший остов графа.

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

Следует отметить, что SST графа не имеет никакого отношения к дереву, дающему все кратчайшие пути, выходящие из некоторой выбранной вершины. Так для графа, показанного на рис. 7.11(a), где числа, стоящие около ребер, являются их весами, дерево, дающее все кратчайшие пути, выходящие из вершины х^, изображено на рис. 7.11 (б), а SST - на рис. 7.11 (в).

Задача построения кратчайшего остова (SST) графа является одной из немногих задач теории графов, которые можно считать



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [ 51 ] 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95