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

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

4. ЗАДАЧА ШТЕЙНЕРА 169

задачу Штейнера нерешенной. Для задач большого размера можно обратиться к ряду эвристических методов [7, 50].

В более позднем варианте задачи Штейнера на плоскости используется обычно линейное (вместо евклидова) расстояние между точками. Такая постановка задач впервые была предложена Хэнном [28, 30] в связи с разработкой теории монтажа печатных схем электронных устройств. Расстояние между точками с координатами (xj, у^, {х^, у2) в этом случае определяется следующим образом:

di.2 = \Xi - X2\ + \yi - y2\.

При этих условиях можно легко показать [44], что если через каждую точку из множества Р провести вертикальные и горизонтальные линии, то решение задачи Штейнера можно получить, рассматривая в качестве возможных точек Штейнера точки пересечения полученной сетки линий.

Пусть граф G построен так, что множество его вершин X является множеством точек пересечения некоторой сетки линий и ребра графа G соответствуют линиям сетки, соединяющим две точки пересечения. Тогда задача Штейнера на плоскости с линейной метрикой переходит в задачу Штейнера для конечного графа, определенную в начале этого раздела [54]. На рис. 7.156 показан пример наикратчайшего дерева Штейнера для линейной задачи с шестью точками, а для сравнения на рис. 7.15а показан SST этой задачи.

Задача Штейнера для обычных неориентированных графов рассматривалась Хакими [27] и Дрейфусом и Вагнером [18]. Они нашли точные алгоритмы решения таких задач. Однако эти алгоритмы с вычислительной точки зрения являются не эффективными процедурами, хотя они и значительно лучше, чем последовательный просмотр SST всех подграфов G графа G. В любом случае (как и в случае задач с евклидовым расстоянием) максимальный размер задач Штейнера, для решения которых требуется разумное вычислительное время, не превышает 10 вершин (в множестве Р). С этой точки зрения задачу Штейнера на графе можно рассматривать как нерешенную проблему, и она в этой книге больше не будет обсуждаться.

5. Задачи

1. Доказать, что все три определения остовного дерева, данные во введении, эквивалентны.

2. Показать, что в дереве, имеющем больше одной вершины, существуют по крайней мере две вершины степени 1.



3. Показать, что детерминант любой квадратной подматрицы матрицы инциденций графа равен +1, - 1 или 0.

4. Для матрицы размера п X т любая квадратная матрица размера min (п, т) X min (п, т) называется главной подматрицей. Показать, что если - главная подматрица матрицы инциденций связного графа, то 15 отличен от нуля (равен + 1


Рис. 7.16.

или-1) тогда и только тогда, когда остовный подграф, состоящий из всех ребер, соответствующих столбцам подматрицы является деревом.

5. Найти все остовные деревья графа, показанного на рис. 7.16, и, используя результат теоремы 1, убедиться, что их число равно числу, приведенному в теореме 1.

6. Показать, что произведение матриц Вд-В*, использованное

в теореме 1, не обязательно вычислять перемножением Вд и В^, но можно получить непосредственно из графа в виде (п X п) матрицы М = [niij], определенной следующим образом: диагональный элемент тпц есть степень вершины х^, а элемент тпи - число параллельных ребер между вершинами xt и xj со знаком минус. Чтобы получить Во -BI, достаточно построить только {п - 1) строк и столбцов матрицы М.

7. Используя теорему 1, показать, что число остовов полного связного неориентированного графа с п вершинами равно

8. Пусть матрица М = [mjjl для ориентированного графа определена следующим образом: тпц = dt (х^), степень полузахода вершины Xj, niij = - к, где к есть число параллельных дуг из Xj в Xj. Показать, что ориентированный граф есть ориентированное дерево с корнем Хг тогда и только тогда, когда тпгг = О, тпц = 1 при i ф г VI определитель подматрицы, получающейся вычеркиванием г-й строки и г-го столбца из М, равен 1 (см. [19).



у

17 V

14/ \

Рис. 7.17.

Рис. 7.18.

9. Пусть М - матрица, определенная в задаче 8. Используя полученный выше результат, показать, что число ориентированных остовов с корнем Хг в ориентированном графе (без петель) равно определителю подматрицы, полученной вычеркиванием г-й строки и г-го столбца из М (см. [1], стр. 163, и [2]).



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