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

[ 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

гамильтоновы циклы

Часто бывает полезно и наглядно изображать некоторую ситуацию в виде рисунка, состоящего из точек (вершин), представляющих основные элементы ситуации, и линий (ребер), соединяющих определенные пары этих вершин и представляющих связи между ними. Такие рисунки известны под общим названием графов, и эта книга посвящена их изучению. Графы встречаются во многих областях под разными названиями: структуры в гражданском строительстве, сети в электротехнике, социограммы в СОЦИОЛОГИИ и экономике, молекулярные структуры в химии, дорожные карты , электрические или газовые распределительные сети и так далее.

Благодаря своему широкому применению теория графов в последние годы интенсивно развивается. В большой мере этому способствует также прогресс в области развития больших быстродействующих вычислительных машин. Непосредственное и детальное представление практических систем, таких, как распределительные сети и системы связи, приводит к графам большого размера, успешный анализ которых зависит в равной степени как ОТ существования хороших алгоритмов, так и от возможности использования быстродействующих вычислительных машин. Поэтому в настоящей книге основное внимание сосредоточено на разработке и описании алгоритмов анализа графов, хотя при этом часто упоминаются области их приложения, что позволяет максимально приблизить текст книги к решениям практических задач. Надеюсь, что благодаря этому читателю будет легче связать изложенные в книге основные понятия со своей областью деятельности и применить их к разработке новых методов решения своих специфических задач.

Хотя вообще считается, что эффективность алгоритмов имеет самое важное значение, автор не сводит свою книгу к справочнику эффективных алгоритмов. Часто метод рассматривается и по той причине, ЧТО он тесно связан с только что введенными понятиями (или получен из них) и ему отдается предпочтение, хотя имеются и другие алгоритмы, столь же (или даже порой несколько более) эффективные.



Определяющим для нашего изложения явилось желание создать у читателя цельное и логически стройное представление об алгоритмах анализа графов.

Название Теория графов на самом деле не может подходить ни к какому однотомному изданию, ибо в таком ограниченном объеме нельзя дать сколько-нибудь полного представления об этом предмете. Настоящая книга не является исключением, ее содержание отражает, как это и должно быть интересы автора и его работы в области исследования операций и в вычислительной математике и теории управления.

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

В главе 3 рассматриваются две задачи, связанные с выбором экстремальных множеств вершин с заданными свойствами. Обсуждаются способы решения задач об определении максимальных независимых и минимальных доминирующих множеств, последняя обобщается до задачи о покрывающих множествах. Рассматриваются приложения задачи о покрывающих множествах к составлению расписаний вылета самолетов и работы транспорта, к задаче об информационном поиске, обсуждаются вопросы сведения других задач теории графов к задаче о покрывающих множествах.

В главе 4 задача о раскраске вершин рассматривается как особый случай задачи о покрывающих множествах, изучавшейся в предыдущей тлаве. Даны приложения задачи раскрашивания к составлению расписаний, размещению ресурсов, а также ее обобщения на задачу доставки.

Следующие две главы посвящены задачам размещения в графах. В главе 5 рассматривается задача размещения мультицентров в графе и ее применение к проблемам размещения на сети дорог всевозможных служб, таких, как пожарные команды, полицейские участки, станции скорой помощи. В главе 6 обсуждается задача размещения мультимедиан в графе и ее приложение к проблемам размещения таких служб, как склады или переключательные пункты в системах доставки товаров или в сетях связи. Глава 5 имеет дело с минимаксной, а глава 6 - с минисуммной задачами размещения.

В главе 7 рассматриваются задачи о деревьях, кратчайших остовах и задача Штейнера, а также приложения этих задач к проектированию электрических и газовых распреде ительных сетей,

В главе 8 разбираются задача поиска кратчайшей цепи между парами вершин и ее приложения к задачам выбора маршрута для максимизации пропускной способности или надежности, к специальному случаю сетей ПЕРТ и к анализу критических маршру-



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

Две следующие главы посвящены задачам поиска циклов в графах. В главе 9 рассматриваются общие циклы и разрезы. Здесь же разбираются задача поиска эйлеровых циклов и задача китайского почтальона с ее приложениями к сборке мусора, к доставке молока или почты и к инспектированию систем с распределенными параметрами. Глава 10 состоит из двух частей. В первой рассматривается задача нахождения гамильтонова цикла в неполном графе и ее приложение к машинному планированию. Вторая часть этой главы посвящена задаче поиска кратчайшего гамильтонова цикла, широко известного под названием задача коммивояжера , и ее приложениям к выбору транспортных маршрутов.

В главе 11 исследуются максимальные потоки и минимальные стоимости - задачи о максимальных потоках в графах, дугам которых приписаны пропускные способности и стоимости. Задачи О потоках в графах, у которых дугам приписаны выигрыши, встречаются при рассмотрении математических моделей арбитража, активных электрических цепей и т. д. Задачи о таких потоках также обсуждаются здесь.

В главе 12 речь идет о вычислении максимальных паросочета-ний графов и описывается обобщенный венгерский алгоритм. Подробно алгоритм разобран для двудольных графов, для случаев транспортной задачи и задачи о назначении, играющих большую роль в исследовании операций с приложениями к назначению людей на работу, размещению вспомогательных служб, составлению маршрутов самолетов и т. д. Взаимосвязь между главами этой книги представлена графически (см. стр. 10).

Часть этой книги была написана при финансовой поддержке Научного исследовательского совета по вопросам математического программирования, которому я очень признателен за оказанное содействие. В подготовке издания этой книги мне помогли очень многие. Я особенно благодарен профессору Сэму Эйлону, руководителю Отдела научного управления Империал колледжа, Питеру Виоле, Джеффу Сэлби, Питеру Брукеру и Сэму Кормэну. Я также хочу поблагодарить профессора Дональда Кнута, прочитавшего первый вариант рукописи и указавшего на несколько ошибок. Я в долгу перед г-жой Маргарет Хаджел, взявшей на себя тяжелый труд ПО перепечатке рукописи. Я должен отметить неоценимую помощь своей жены, которая не только безропотно терпела мою постоянную работу над книгой по вечерам, но также помогала при чтении корректур.

Никое Кристофидес

Октябрь 1973 Лондон



[ 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

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