Файл: Солтан, П. С. Экстремальные задачи на графах и алгоритмы их решения.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.10.2024
Просмотров: 39
Скачиваний: 0
б) удаляющая вое виоячие вершины дерева |
Н , |
если |
орѳди |
|||
них имеютоя по крайней мере две вершины о |
одинаковыми |
"потен |
||||
циалами"; |
|
Н |
|
|
|
|
в) если среди |
висячих вершин дерева |
имеется |
лишь одна |
|||
вершина с максимальным "потенциалом", то |
удаляютоя |
|
все |
осталь |
||
ные виоячие вершины. |
|
|
|
|
|
|
Заметим, что при применении операций |
присвоения |
и |
/1 —усе |
|||
чения к дереву Н |
получается дерево Ht |
, у |
которого количест |
|||
во висячих вершин не больше количества висячих вершин дерева Н.
После конечного числа |
этапов применения операций присвоения |
и |
|||||||||
А -усечения к деревьям |
Н |
, |
ні |
, Нг, ■ ■ •, Нр |
получим либо |
одну |
|||||
вершину - выролденное дерево, либо дерево с двумя вершинами. |
|
||||||||||
На оонове доказанной теоремы и |
введенных |
операций |
можно |
||||||||
предложить следующий алгоритм нахождения центра |
тяжести |
дерева. |
|||||||||
1 . Проверяем выполнение условия |
N > 2 ? |
|
Если да, |
то |
|
пе |
|||||
реходим |
к п . 2 . В противном |
олучае к п. 6. |
|
|
|
|
|
||||
2. |
Находим множество |
висячих вершин д ер ев а //. |
|
|
|
||||||
3 . Выполним операцию присвоения |
в дереве Н. |
|
|
|
|||||||
4 . Применяем операцию |
А -уоечения дерева//. |
|
|
|
|||||||
5 . В результате выполнения |
пунктов 2 - 4 |
получим новое |
де |
||||||||
рево Ht . Заменяем дерево |
Н |
на |
Н, . Переходим |
к пункту |
I . |
|
|
||||
6 . После конечного числа шагов получим либо вырожденное де |
|||||||||||
рево-вершину, либо дерево, |
содержащее ровно две |
вершины.Если |
по |
||||||||
лученное дерево вырожденно, то переходим к п .7 , в противном слу
чае - |
к п. 8. |
|
|
|
|
|
|
|
|
Н |
|
|
|
7 |
. Печатаем номера |
вершины (центра тяжести дерева |
) . |
||||||||
|
8 |
. Для |
дерева |
Нр применим операцию присвоения. Если полут*--- |
||||||||
ченные |
"потенциалы" |
этих двух |
вершин равны, то переходим |
к п. 9, |
||||||||
в противном |
случае |
- к п.ІО . |
|
|
|
|
|
|
||||
|
9 |
. Печатаем номера |
вершин дерева Нр (центры тяжести |
дере |
||||||||
ва |
Н |
) , |
|
|
|
|
|
|
Нр с максимальным |
|
|
|
|
10. |
Выбираем вершину дерева |
"потенциало |
|||||||||
Печатаем номер |
этой |
вершины (центра |
тяжести дерева Н |
) . |
|
|||||||
|
Можно указать |
различные |
приложения изложенного |
алгоритма. |
||||||||
Вот одно из них. Пусть дерево |
Н |
представляет собой |
обслуживаю |
|||||||||
щую систему. Если р ( у ) |
интерпретировать как частоту |
связи |
меж |
|||||||||
ду |
центром Je“ |
и |
а |
"стоимость" |
пропорциональной |
|
квадрату |
|||||
"расстояния", |
то J z |
(ое° ) |
будет |
минимальная "стоимость" |
свя |
|||||||
зи |
центра со |
всеми |
пунктами системы. |
|
|
|
|
|||||
ЦИТИРОВАННАЯ ЛИТЕРАТУРА
1 . |
К.Берж. Теория графов и ее применение. М., ИЛ, 1962. |
|
|
|||||||||
2 . |
Э.Берлекэмп. Алгебраическая теория |
кодирования. |
М,, "Мир", |
|||||||||
|
|
1971. |
|
|
|
|
|
|
|
|
|
|
3 . В.Г,Болтянский. Гомотопическая теория непрерывных |
отображе |
|||||||||||
|
|
ний и векторных полей. М.,РИ0 АН МССР, 1956. |
|
|
|
|
||||||
4 . |
А.Данцер, Б.Грюнбаум, |
В.Кли. Теорема Хелли. М., "Мир", |
1968. |
|||||||||
5 . М.А.Духовный. Об одной |
оптимальной |
задаче |
теории |
графов. Ма |
||||||||
|
|
тематические записки, |
10, вып.З. М., |
"Наука", |
1971. |
|
||||||
6.. Д.К.Замбицкий, П.С.Солтан. Об одной |
экстремальной |
|
задаче |
на |
||||||||
|
|
дереве. Математические методы решения экономических за |
||||||||||
|
|
дач, I . |
М., |
"Наука", 1969. |
|
|
|
|
|
|
||
7 . Д.К.Замбицкий. Относительно |
одной |
экстремальной |
задачи |
на |
||||||||
|
|
графе. Прикладная математика и программирование. |
Киши- |
|||||||||
|
|
flев,РИО АН МССР,І968. |
|
|
|
|
|
|
|
|||
8 . |
Д.К.Замбицкий. Об одной задаче на графе. Математические |
|
ис |
|||||||||
|
|
следования, |
3 , вып.З. Кишинев,РИО ÄH МСС^ІЭбѲ, |
|
|
|
||||||
9. С.И.Зуховицкий, |
Л.И.Авдеева. Линейное и выпуклое |
программи |
||||||||||
|
|
рование. М., "Наука", |
1967, |
|
|
|
|
|
|
|||
1 0 . |
А.А.Зыков. Теория конечных графов. Новосибирск,"Наука",1968. |
|||||||||||
Ц.А.К.Кельмано. О |
выборе оптимальной вершины в графе. Исследо |
|||||||||||
|
|
вания по дискретной математике. М., "Наука", 1973, |
|
|
||||||||
1 2 . |
G.С.Лавров, |
Л.И.Гончарова. Автоматизация |
обработки |
данных. |
||||||||
|
|
Хранение |
информации в |
памяти ЭВМ. М., |
"Наука", |
1971. |
|
|||||
1 3 . |
Л.Лефгрен. Решение проблемы реализуемости неиэбыточными ' бу |
|||||||||||
|
|
левыми схемами. Кибернетичѳокий сборник, вып.2. М., ИЛ, |
||||||||||
|
|
1967. |
|
|
|
|
|
|
|
|
|
|
1 4 .0 . |
Б.Лупанов. О |
синтезе некоторых клаосов |
управляющих оиотем. |
|||||||||
|
|
Проблемы кибернетики, вып.ІО. М., Физматгиз, |
1963. |
|
|
|||||||
1 5 .0 . |
0 .е . Теория графов. М., |
"Наука", |
1968. |
|
|
|
|
|
||||
Іб.К.Ф.Присакару. Относительно |
задачи Штейнера на графах. Прик- |
|||||||||||
87
ладная математика и ^программирование, |
вып.8. |
Кишинев, |
||||
"Штиинца", 1972.. |
|
|
|
|
|
|
17 . П.С.Солтан. Теорема |
Хеши |
для |
«/-выпуклых множеств, |
ДАН |
||
СССР, 205, » 3 . 1972,. |
|
|
|
|
|
|
18. П.С.Солтан, К.Ф.Присаяарз'» |
0 |
задаче Штейнера на графах I . |
||||
Прикладная математика и программирование, вып.6. Киши |
||||||
нев, "Штиинца”, |
1971. |
|
|
|
|
|
19. П.С.Солтан, К.Ф.Присаквру. Задача Штейнера |
на графах. |
ДАН |
||||
СССР, 198, №I , |
1971. |
|
|
|
|
|
2 0 . Д.Дл.Уайлд. Метода |
поиска |
экотремума. М., |
"Наука", |
1967. |
||
ОГЛАВЛЕНИЕ |
|
|
|
|
|
|
|
|
|
|||
В |
в |
е |
д е |
н |
и е . . . . . |
. ......................................- 3 |
|
|||||
Г л а в а |
I . |
|
Задача Штейнера |
|
|
|
|
|||||
§ |
I . |
Формулировка задачи |
.............................................. |
|
|
|
5 |
|||||
§ |
2 . Некоторые предварительные сведения и теоре |
|
||||||||||
|
|
ма Хелли |
|
для |
d -выпуклых множеств . . . . |
8 |
||||||
§ |
3 . |
Задача |
Штейнера в пространстве |
Ri . . . . |
17 |
|||||||
§ |
4. Описание |
|
класса графов, для которых задача |
|
||||||||
|
|
Штейнера решается ^эффективно............... |
|
25 |
|
|||||||
§ |
5. Топологические свойства графов класса |
К . |
2G |
|||||||||
§ |
6 . |
Теорема |
о расстоянии . . . . . . . . . . . |
30 |
||||||||
Г л а в а |
В. Решение задачи Штейнера на графах |
|
||||||||||
§ |
7. Описа ние мпожесіда решений задачи'Штейнера |
34 |
||||||||||
§ |
8 . Решение |
|
задачи X X X |
................................ |
|
|
|
42 |
||||
§ |
9 . |
|
Решение |
|
задачи X X Y |
.............................................. |
|
|
|
42 |
||
§ |
10. |
Решение |
задачи ХМY . . |
....................................... |
45 |
|||||||
§ |
I I . |
Решение |
задачи Штейнера для деревьев . . |
51 |
||||||||
§ 12. Задача Штейнера для |
графов |
с |
ребрами |
со |
|
|||||||
|
|
|
членения ..................................................................... |
|
|
|
|
|
57 |
|||
§ |
13. Задача Штейнера для графов |
с |
точками |
со |
|
|||||||
|
|
|
членения ................................................................... |
|
|
|
|
|
60 |
|||
§ |
14. |
Алгоритм нахожденияблоковграфа . . . . |
65 |
|||||||||
Г л а в а |
Ш. Задачи типа задач |
Штейнера ' |
|
|
||||||||
§ 15 .0 двух |
задачах,сводящихся к задаче Штейнера |
69 |
||||||||||
§ |
16. |
Совместное |
решениенесколькихзадач |
Штей |
|
|||||||
|
|
|
нера |
на г р а ф е |
|
|
|
71 |
|
|||
Зак.665 |
|
|
|
|
|
|
|
|
|
|||
89
§ 17. |
Совместное рассмотрение на графе нескольких |
|
§ 18. |
пар задач типа Штейнера . . . . . ....... |
77 |
Центр тяжести дерева и алгоритм его |
натиж- |
|
|
дения . . . . . . . . . . . . . . . . |
. . . 62 |
Ц и т и р о в а н н а я л и т е р а т у р а . |
. . , . »87 |
|
Петр Семенович Солтан Дмитрий Кириллович Замбицкий Кирилл Федорович Присакару
ЭКСТРМАЛЬНЫЕ ЗАДАЧИ НА ГРАФАХ И АЛГОРИТМЫ ИХ РЕШЕНИЯ
Утверждено к изданию Редакционно издательским советом АН МССР
Редактор В.Н.Безручко Художественный редактор В.А.Чупин Художник Б.П.Никифоров Технический редактор Л .А.Мокрицкая
Корректоры А.Л.Меламед” Л.М.Малая і Оператор-наборщик Е.С.Волощук
Подписано |
в печать 19,. X 1973 г . ABI I 510.Бумага офсетная № I.Фор |
|
мат 60x90 |
І/І6 .П еч .л .5 ,7 5 . У ч .-и зд .л .5,57 . Тираж.50(Г . |
|
|
Цена 56 коп.Заказ 665, |
|
Издательство "Штиинца", 277028, Кишинев, |
ул. Академичеокая, 3. |
|
|
Типография издательства |
"Штиинца” , |
|
777004, Кишинев, ул.Берзарина, 10 |
|
j ГОТОВЯТСЯ К ИЗДАНИЮ в 1974 ГОДУ 'В ИЗДАТЕЛЬСТВЕ * "ШТИИНЦА"
И. И, В а л у ц э . Отображения. Алгебраическая
теория. 8 л. На русском языке. Цена 80 коп.
Исследования по дискретной геометрии. 8 л. На руооком языке. Цена 80 коп.
Р. И. Т р у X а е в, В. С. Л е р н ѳ р. Дина-
мичеокне модели процессов принятия |
решений. |
13 л. На русском языке. Цена I р. 30 к.
Заказы просим направлять по адресу: 277028, Киши
нев, ул.Академическая, 3, Издательство "Штиинца"