Глава 1. Задача китайского почтальона
Историческая справка.
Еще с древнейших времен люди задумывались, как лучше пройти путь, что бы затратить как можно меньше усилий, времени или денег. Гонцы должны были разнести новость сразу в несколько поселений и, для сокращения пути, вероятнее всего, прокладывали кратчайшие пути на карте, обозначив города точками, а свой путь – дугами. И так продолжалось многие столетия, пока не появились средства массовой информации. Хотя и сейчас, в наше время задача коммивояжера (далее ЗК) имеет широкое прикладное применение. Например, в 1984 году, после того как был проведен анализ последовательности и временных затрат на операции на конвейерах заводов компании "General Motors" и приняты рекомендованные меры, удалось увеличить общую производительность почти на 13% при неизменном числе рабочих и том же оборудовании. Расчеты производились на компьютерах IBM 360gr, которые в то время являлись одними из самых производительных систем в мире. Просчет и оптимизация 200 основных и 87 вспомогательных операций занял около 230 часов. Считается, что это было первое коммерческое применение компьютерных технологий в области управления производством в целом. И это, наверное, явилось наиболее ярким решением «задачи о коммивояжере».
Первая публикация, посвященная решению подобной задачи, появилась в одном китайском журнале, где она была названа задачей почтальона. Иногда ее даже называют задачей китайского почтальона. Формулировка задачи коммивояжера была впервые четко сформулирована в 1934 году.
1.2. Основные термины и теоремы теории графов.
Граф - упорядоченная пара двух множеств Х и Е, где Х – множество вершин, а Е –
множество дуг.
Любое конечное множество точек (вершин), некоторые из которых попарно соедине-
ны стрелками, (в теории графов эти стрелки называются дугами), можно рассматри-
вать как граф.
Граф называется ориентированным, если указано направление дуг. Иначе он неориентированный.
Основные элементы графа:
Точки – вершины
Дуги или ребра – отрезки, соединяющие вершины.
3. Петля – ребро, у которого начало и конец совпадают
Виды вершин (Рис. 1.1): а) Петля (х1) б)Изолированная в)смежные – соединены общим ребром. г) Висячая (х4) Виды ребер: а) Кратные – соединяющие одни и те же вершины (е3, е4) б) смежные вершины в) смежные другому ребру – имеют общие вершины.
|
Рис. 1.1 Виды ребер и вершин
|
Кратностью пары вершин называется число соединяющих их ребер.
Степень вершины - количество ребер графа, исходящих из этой вершины.
Рис. 1.2 Граф с 5ю вершинами |
На рисунке 1.2 изображен граф с пятью верши-нами. Степень вершины А обозначим Ст.А. На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0. |
Граф называется вырожденным, если у него нет рёбер.
Вершина Х называется инцидентной ребру G , если ребро соединяет эту верши-
ну с какой-либо другой вершиной.
Вершины называются смежными , если существует ребро , их соединяющее.
Два ребра G1 и G2 называются смежными, если существует вершина, инцидентная одновременно G1 и G2.
Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами. При этом ни-какое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец
пути.
Каждый граф можно представить в пространстве множеством точек, соответствующих вершинам, которые соединены линиями, соответствующими ребрам (или ду-
гам - в последнем случае направление обычно указывается стрелочками) - такое представление называется укладкой графа. .
Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежные.
Конечная последовательность необязательно различных рёбер E1,E2,...En назы-
вается маршрутом длины n, если существует последовательность V1, V2, ... Vn необя-
зательно различных вершин, таких, что Ei = (Vi-1,Vi ).
Маршрут, в котором все рёбра попарно различны, называется цепью. Маршрут,
в котором все вершины попарно различны, называется простой цепью.
Замкнутый маршрут, все рёбра которого различны, называется циклом. Если все вершины цепи или цикла различны, то такая цепь или цикл называются простыми
(или элементарным). Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией.
На рисунке 1.3 приведены примеры Эйлеровых линий.
Рис. 1.3 Примеры Эйлеровых линий
Очевидно, путь, проложенный по сторонам любого многоугольника, начинающийся и заканчивающийся в одной и той же его вершине, является Эйлеровой линией.
Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую — концом этого ребра. Граф, у которого все ребра ориентированные, называется ориентированным графом (рис. 1.4)
|
Рис.1.4 Ориентированный граф
|
Граф называется связным, если для любых двух вершин существует путь, соединяю-
щий эти вершины.
Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины. На рисунке 1.5 приведен пример графа «дерева». Вершина дерева, имеющая степень единицу, называется висячей вершиной (на рис. 1.5 они отмечены кружком).
|
Рис.1.5 Дерево
|
Свойство 1. Для каждой пары вершин дерева существует единственный путь, их сое-диняющий.
Этим свойством пользуются при нахождении всех предков, например, по мужской линии, любого человека, чья родословная представлена в виде генеалогического дерева, которое является «деревом» и в смысле теории графов.
Например, на рисунке 1.6 (являющегося деревом, вершины которого изображены прямоугольниками с помещенной в них информацией) представлено генеалогическое де-рево некоего Сергея.
Рис. 1.6 Генеалогическое Древо
По этому дереву однозначно находится предок Сергея в любом поколении по любой
линии.
Свойство 2. Всякое ребро в дереве является мостом.
Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева. Это легко видеть на рисунке 1.7, если удалить, например, ребро А5А6 или ребро А1А3, или ребро А4А10 (оставив «вторым деревом» вершину A10)
Рис.1.7 Дерево
Теорема 1.
Сумма степеней всех вершин равна удвоенному числу ребер графа
Теорема 2. (Лемма о рукопожатиях)
В конечном графе число вершин нечетной степени чётно.
Теорема 3.
Граф связен тогда и только тогда, когда множество его вершин нельзя разбить на два
непустых подмножества так, чтобы обе граничные точки каждого ребра находились в одном и том же множестве.