8.4. Результаты вычислений

Алгоритм построения абсолютного р-центра был опробован на ЭВМ CDC 6600. Каждый бинарный вектор, задающий SI, хранится в одном слове, так что можно использовать булевские функции для более удобного выполнения теоретико-множественных операций. Поскольку длина слова в вычислительной машине CDC 6600 равна 60 битам, то граф, содержащий не более 60 вершин, можно было непосредственно задавать в машинном коде.

В некоторых задачах, в частности, когда число областей в искомом абсолютном р-центре (т. е. число р) велико, шаг 5 алгоритма, описанного в разд. 8.1, требует значительную часть всего времени, затрачиваемого на решение задачи. В табл. 5.1 время, необходимое для выполнения этого шага, приведено отдельно от полного времени решения задачи. В этой таблице представлены времена вычисления (в секундах) и числа итераций, требуемые при построении абсолютных 1-, 2-, 3-, 4- и 5-центров для некоторых графов. Здесь мы под числом итераций понимаем число повторений шагов алгоритма с 3 по 6 (для различных значений к), всех тех повторений, которые необходимо осуществить для получения абсолютного р-центра с заданной точностью. Графы, которые были использованы при составлении табл. 5.1, выбирались случайным образом и являются связными и неориентированными. Требуемая точность во всех случаях принималась равной 1% от средней длины ребер рассматриваемого графа.

Как видно из табл. 5.1, алгоритм, приведенный в разд. 8.1,-можно весьма эффективно использовать при нахождении абсолютных р-центров достаточно больших графов.

тельного перебора; оно порождается SI с номерами 16 и 18 в приведенном выше списке. Область, соответствующая SI с номером 16, состоит из одной точки, расположенной на ребре (2,3) в том месте,

где находится кружок @ . На рис. 5.9 эта точка обозначена

буквой Л. Область, соответствующая SI с номером 18, представляет собой участок ребра (1,5) между метками 6 и 1; на рис. 5.9 она обозначена буквой В.

Таким образом, при X = 3,5 требуется два центра; один расположен в точке А, а другой - в любой точке области В. Поскольку область А является точкой, то два указанных центра образуют также абсолютный 2-центр и Я = 3,5 является минимально возможным критическим расстоянием для существования 2-центра. Поэтому при к < 3,5 область А исчезнет совсем, и тогда уже нужно строить 3-центр.

вычислительные результаты для выборочных графов

Таблица SJ

Число центроб в обсолютном р-центре (значение р)

Гра/р

nf mt

в

в

в

в

0,44 0,46

14,00 3,51 6,02

16,10

0,08 0,06

13,00 1,94 4,50

12,00

0,33 0,35 1,36 0,37 2,58 3,60 4,25 6,38 6,00

18,10 8,40

23,20

0,06 0,05 0,45 0,22 1,06 1,70 1,53 2,86 2,10

14,50 3,73

18,80

31,34

25.88

24,55

16,60

0,15 0,46 1,16 1,49

2,70 2,85 4,21 3,82 2,66 7,20 6,50 11,80 27,00 17,70

0,04 0Р9 0,11 0,43 0,18 0,41 0,37 0,58 0,45 0,12 1,56 1,20 2,53 13,50 0,95

0,30 0,55 1,13 1,73 1,63 3,20 5,41 4,35 3,83 3,16 6,90 7,10 11,20 10,00 8,11

0,04 0,08 0,05 0,06 0,05 0,10 0,19 0,09

0,06 0,17 0,25 0,22 0,51 0,11

0,34 0,51 0,86 1,05 1,75 2,90 2,20 3,32 5,00 2,22 3,55 6,60

12,40 7,40

17,80

t Число вершин X Числа ребер

А Полное время вычисления (секунды на CDC i В Время бышсления для шаеа 5 алгоритма С Число иа

8.5. Применение общего алгоритма для поиска -центров

Алгоритм из разд. 8.1 можно, очевидно, использовать при решении более узкой задачи, приведенной в разд. 6, т. е. при нахождении р-центра. Для этого надо только изменить шаг 6 настоящего алгоритма (см. разд. 8.1) таким образом, чтобы контролировалось не число областей в наименьшем доминирующем множестве, найденном на шаге 5, а число вершин графа G, содержащихся в этих областях. Если полученное число вершин больше р, то нужно возвратиться к шагу 2. В противном случае алгоритм заканчивает работу, и р-центром графа будет множество вершин, содержащихся во всех тех областях, которые образуют доминирующее множество.

Поскольку в этом случае необходимы только вершины, содержащиеся в областях, задаваемых соотношениями (5.22) и (5.23), то алгоритм из разд. 8.1 можно без изменений применять для нахождения р-центров, если области на шаге 3 строить с помощью соотношений (5.22) и (5.23), используя вместо множеств (а;,) множества (х,). Более того, если все п (п - 1) расстояний в матрице расстояний с самого начала расположить в строку в порядке неубывания [Д, f, . . ., fn (n-uli то на шаге 2 алгоритма значения для параметра Я должны выбираться лишь из этой строки, и их не надо увеличивать на произвольно малую величину в каждой итерации. Поиск начинается с Я = /i, а затем продолжается при Я = /2, /з и т. д. в соответствии с указанным выше упорядочением. Следует заметить, что здесь, очевидно, было бы весьма кстати бинарное представление семейства ) {Д, /2, ...

- ч /л<л-1)}

9. Задачи

1. Найти центр графа, приведенного на рис. 5.11. Рядом с дугами указаны их стоимости, а веса вершин задаются вектором 15, 3. 1, 7, 4, 6]

2. Найти абсолютные центр и радиус неориентированного графа, изображенного на рис. 5.12, предполагая, что веса всех вершин равны 1. Использовать метод Хакими, а также итерационный метод из разд. 5.4. Сравнить вычислительную трудоемкость этих двух методов.

3. Показать, что в любом неориентированном графе G с единичными весами вершин существует такой маршрут между неко-

1 В семействе (в отличие от множества) могут встречаться одинаковые элементы.- Прим. ред.