Теория графов

Введение

ТЕОРИЯ ГРАФОВ - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (потому что во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин. Основной объект теории графов-граф и его обобщения.

Первые задачи теории графов были связаны с решением математических развлекательных задач и Одним из первых результатов в теории графов явился критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Вот пересказ отрывка из письма Эйлера от 13 марта 1736 году: ” Мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел лёгкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может“. Кенигсбергские мосты схематически можно изобразить так.

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

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

 

 

 

 

 

 

 

I. Основные понятия теории графов

1. Граф G(V,E) - комбинаторный объект, состоящий  из двух конечных множеств: V - называемого множеством вершин  и множества пар элементов  из V, т.е. Е VxV, называемого множеством ребер, если пары неупорядочены, и множеством дуг, если пары упорядочены. В первом случае граф G(V,E) называется неориентированным, во втором ориентированным. Если е = (v₁,v₂).

Е, то говорят, что ребро е соединяет  вершины v₁,v₂, если v₁ = v₂, то ребро е называется петлей. Две вершины v₁,v₂ называются смежными, если существует соединяющее их ребро. Аналогично, два различных ребра смежны, если они имеют общую вершину.

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

Путь - это последовательность ребер e₁, е₂, ... , е_m, такая, что e_i, e_i+1 имеют общую вершину. Число ребер называется длиной пути. Если ни одна из вершин не появляется более одного раза, то путь называется простым. Ясно, что в простом пути ни одно ребро не используется дважды.

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

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

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

Двудольные графы. Это графы, у которых множество вершин можно разбить на два множества V₁, и V₂ , и так что каждое ребро графа соединяет только некоторую вершину из V₁ с некоторой вершиной из V_2.

Граф единичного n-мерного куба В_n. Вершины графа - n-мерные двоичные наборы. Ребра соединяют вершины, отличающиеся одной координатой.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Маршруты, цепи цыклы  

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

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

    Маршрут   называется циклическим, если v1=vn+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется его длиной. Цикл длины 3 часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер.

 Минимальная из длин  циклов графа называется его  обхватом.  
    Свойства маршрутов, цепей и циклов:  
1) Всякий незамкнутый маршрут, содержит в себе простую цепь. В частности, любая цепь, содержит в себе простую цепь. Причем, если маршрут содержит в себе вершину , то в общем случае, простая цепь может не содержать в себе вершину w.  
2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.  
3) Всякая цепь, может быть разбита на простую цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.  
4) Для любых трех вершин из существования цепи , следует существование цепи. Причем может не существовать цепи, содержащей вершину w.  
5) Объединение двух несовпадающих простых  цепей содержит простой цикл.

6) Если граф содержит 2 несовпадающих цикла с общим  ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.  
    Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины существовал маршрут.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Литература

1. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., “Мир”, 1965, 174 с.

2. В. П. Сигорский. Математический аппарат инженера. - К., “Техніка”, 1975, 768 с.

3. Ю. Н. Кузнецов, В. И.  Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа, 1980, 300 с., ил.

4. Е. В. Маркова, А.  Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. - М., Наука, 1979, 345 с.

5. Е. П. Липатов. Теория  графов и её применения. - М., Знание, 1986, 32 с.

6. В. М. Бондарев, В. И.  Рублинецкий, Е. Г. Качко. Основы программирования. - Харьков, Фолио; Ростов на Дону, Феникс, 1998, 368 с.

7. Ф. А. Новиков Дискретная  математика для программистов. - Санкт-Петербург, Питер, 2001, 304 с., ил.