Содержание

 

      Введение

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

     Основной  объект теории графов-граф и его  обобщения. Первые задачи теории графов были связаны с решением математических развлекательных задач и головоломок.

     Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении  задачи о Кенигсбергских мостах.

     Существует  еще один вид задач, связанных  с путешествиями вдоль графов. Речь идёт о задачах, в которых требуется отыскать путь, проходящий через все вершины, причем не более одного раза через каждую. Цикл, проходящий через каждую вершину один и только один раз, носит название гамильтоновой линии. К сожалению, пока еще не найден общий критерий, с помощью которого можно было бы решить, является ли данный граф гамильтоновым, и если да, то найти на нём все гамильтоновы линии.

     Сформулированная  в середине 19 в. проблема четырех  красок также выглядит как развлекательная задача, однако попытки ее решения привели к появлению некоторых исследований графов, имеющих теоретическое и прикладное значение. Проблема четырех красок формулируется так: ”Можно ли область любой плоской карты раскрасить четырьмя цветами так, чтобы любые две соседние области были раскрашены в различные цвета?”. Гипотеза о том, что ответ утвердительный, была сформулирована в середине 19 в. В 1890 году было доказано более слабое утверждение, а именно, что любая плоская карта раскрашивается в пять цветов.

     Многочисленные  попытки решения задачи оказали  влияние на развитие ряда направлений  теории графов. В 1976 году анонсировано положительное решение задачи с  использованием ЭВМ.

     Другая  старая топологическая задача, которая  особенно долго не поддавалась решению и будоражила умы любителей головоломок, известна как “задача об электро-, газо- и водоснабжении”. В 1917 году Генри Э.Дьюдени дал ей такую формулировку. В каждый из трёх домов, изображенных на рисунке, необходимо провести газ, свет и воду. Свет вода газ Можно ли так проложить коммуникации, чтобы они, нигде не пересекаясь друг с другом, соединяли каждый дом с источниками электричества, газа и воды? Оказывается нельзя.

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

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

       В начале 20 в. графы стали использоваться для представления некоторых математических объектов и формальной постановки различных дискретных задач; при этом наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт. После выхода в свет в 1936 году монографии Д. Кёнига термин «граф» стал более употребительным, чем другие. В этой работе были систематизированы известные к тому времени факты. В 1936 году вышла небольшая брошюра Ойстена Оре, содержащая блестящее элементарное введение в теорию графов. В 1962 году в Англии была издана книга французского математика Клода Бержа “Теория графов и её приложение”. Обе книги, безусловно, представляют интерес для любителей занимательной математики.

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

     Значительно расширились исследования по теории графов в конце 40-х – начале 50-х  годов, прежде всего в силу развития кибернетики и вычислительной техники. Благодаря развитию вычислительной техники, изучению сложных кибернетических систем, интерес к теории графов возрос, а проблематика теории графов существенным образом обогатилась. Кроме того, использование ЭВМ позволило решать возникающие на практике конкретные задачи, связанные с большим объемом вычислений, прежде не поддававшиеся решению.

     Для ряда экстремальных задач теории графов были разработаны методы их решения, например, один из таких методов  позволяет решать задачи о построении максимального потока через сеть.

     Для отдельных классов графов (деревья, плоские графы и т. д.), которые изучались и ранее, было показано, что решения некоторых задач для графов из этих классов находятся проще, чем для произвольных графов.

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

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

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

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

 

Алгоритмы на графах

1. Основные понятия

      Граф G (рис.1) задается множеством точек (вершин) х₁, х₂,..., х_n. (которое обозначается через Х) и множеством линий (ребер) а₁, а₂,...,а_m. (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х, А).

      Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом, (рис.2).

     Например, если дорога имеет не двух-, а одностороннее движение то направление этого движения будет показано стрелкой.

     Если  ребра не имеют ориентации, то граф называется неориентированным (рис 3).

      В ориентированном графе дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т.е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рис. 2 обозначение (х₁ ,х₃) относится к дуге а₁.

     Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(Х, Г). Так, например, для графа на рис. 2:

     Г (х₁)={х₂, х₃}, т.е. вершины х₂ и х₃ являются конечными вершинами дуг, у которых начальной вершиной является вершина х₁.

     На  рис. 3: Г (х₁)={х₂, х₄, х₅}, (неориентированное ребро представляется как две противоположно направленные дуги, соединяющие те же самые вершины.)

      Путем (или ориентированным маршрутом) ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

     Так, на рис. 5 последовательности дуг

     а₆, а₅, а₉, а₈, а₄. (1)

     а₁, а₆, а₅, а₉. (2)

     а₁, а₆, а₅, а₉, а₁₀, а₆, а₄. (3)

     являются  путями.

     Ориентированной цепью (орцепью) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например приведенные выше пути (1) и (2) являются орцепями, а путь (3) не является таким, т.к. дуга а₆ в нем используется дважды.

     Простой орцепью называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (2) является простой орцепью, а пути (1) и (3) – нет.

     Маршрут есть неориентированный “двойник” пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер а₁, а₂,..., а_q, в которой каждое ребро а_q за исключением первого и последнего ребер, связано с ребрами а_i-1 и а_i+1 своими концевыми вершинами. Последовательности дуг:

     а₂, а₄, а₈, а₁₀, (4)

     а₂, а₇, а₈, а₄, а₃, (5)

     а₁₀ , а₇ , а₄ , а₈ , а₇ , а₂. (6)

     в графе, изображенном на рис. 5, являются маршрутами; две точки над символом дуги означают, что ее ориентацией  пренебрегают, т.е. дуга рассматривается  как неориентированное ребро. Также  путь или маршрут можно изображать последовательностью вершин. Например, путь (1) будет выглядеть следующем образом: х₂, х₅, х₄, х₃, х₅, х₆.

     Иногда  дугам графа приписываются числа, называемые весом, стоимостью, или длиной этой дуги. В этом случае граф называется графом со взвешенными дугами. А если вес приписывается вершинам графа, то тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам и вершинам, то он называется просто взвешенным.

     Связный граф без циклов называется деревом. Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярные генеалогические деревья. Пример – генеалогическое дерево.

     Эквивалентные определения дерева.

1. Связный  граф называется деревом, если  он не имеет циклов.

2. Содержит N-1 ребро и не имеет циклов.

3. Связный  и содержит N-1 ребро. 

4. Связный  и удаление одного любого ребра  делает его несвязным.

5. Любая  пара вершин соединяется единственной  цепью. 

6. Не  имеет циклов и добавление  одного ребра между любыми  двумя вершинами приводит к  появлению одного и только  одного цикла.

2. Способы задания графа

     1. Геометрический:  
 
 
 

     2. Матрицей смежности: