Для чего нужна теория графов. Теория графов и важнейшие современные прикладные задачи

ВЛАДИМИРСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ УНИВЕРСИТЕТ

РЕФЕРАТ

«ТЕОРИЯ ГРАФОВ»

Выполнила:

Зудина Т.В.

Владимир 2001

1. Введение

2. История возникновения теории графов

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

4. Основные теоремы теории графов

5. Задачи на применение теории графов

6. Применение теории графов в школьном курсе математики

7. Приложение теории графов в различных областях науки и техники

8. Последние достижения теории графов

§1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ТЕОРИИ ГРАФОВ.

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года [см. стр. 41-42]:

"Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство… После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке [рис.1], на котором A обозначает остров, а B , C иD – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a , b , c , d , e , f , g ".

(РИСУНОК 1.1)

По поводу обнаруженного им способа решать задачи подобного рода Эйлер писал [см. стр. 102-104]:

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

Так можно ли обойти Кенигсбергские мосты, проходя только один раз через каждый из этих мостов? Чтобы найти ответ, продолжим письмо Эйлера к Маринони:

"Вопрос состоит в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, – таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре – A , B , C , D . Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным – по три моста, т. е. Число мостов, ведущих к отдельным участкам, нечетно, а этого одного уже достаточно для решения задачи. Когда это определено, применяем следующее правило: если бы число мостов, ведущих к каждому отдельному участку, было четным, то тогда обход, о котором идет речь, был бы возможен, и в то же время можно было бы начать этот обход с любого участка. Если же из этих чисел два были бы нечетные, ибо только одно быть нечетным не может, то и тогда мог бы совершиться переход, как это предписано, но только начало обхода непременно должно быть взято от одного из тех двух участков, к которым ведет нечетное число мостов. Если бы, наконец, было больше двух участков, к которым ведет нечетное число мостов, то тогда такое движение вообще невозможно… если можно было привести здесь другие, более серьезные задачи, этот метод мог бы принести еще большую пользу и им не следовало бы пренебрегать".

Обоснование вышеприведенного правила можно найти в письме Л. Эйлера к своему другу Элеру от 3 апреля того же года. Мы перескажем ниже отрывок из этого письма.

Математик писал, что переход возможен, если на участке разветвления реки имеется не более двух областей, в которые ведет нечетное число мостов. Для того, чтобы проще представить себе это, будем стирать на рисунке уже пройденные мосты. Легко проверить, что если мы начнем двигаться в соответствии с правилами Эйлера, пересечем один мост и сотрем его, то на рисунке будет изображен участок, где опять имеется не более двух областей, в которые ведет нечетное число мостов, а при наличии областей с нечетным числом мостов мы будем располагаться в одной из них. Продолжая двигаться так далее, пройдем через все мосты по одному разу.

История с мостами города Кенигсберга имеет современное продолжение. Откроем, например, школьный учебник по математике под редакцией Н.Я. Виленкина для шестого класса. В нем на странице 98 в рубрике развития внимательности и сообразительности мы найдем задачу, имеющую непосредственное отношение к той, которую когда-то решал Эйлер.

Задача № 569 . На озере находится семь островов, которые соединены между собой так, как показано на рисунке 1.2. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A ?

(РИСУНОК 1.2)

Решение. Поскольку эта задача подобна задаче о Кенигсбергских мостах, то при ее решении мы также воспользуемся правилом Эйлера. В результате получим следующий ответ: катер должен доставить путешественников на остров E или F , чтобы они смогли пройти по каждому мосту один раз. Из того же правила Эйлера следует невозможность требуемого обхода, если он начнется с острова A .

В заключение отметим, что задача о Кенигсбергских мостах и подобные ей задачи вместе с совокупностью методов их исследования составляют очень важный в практическом отношении раздел математики, называемый теорией графов. Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865), из современных математиков – К. Берж, О. Оре, А. Зыков.

§2. ОСНОВНЫЕ ТЕОРЕМЫ ТЕОРИИ ГРАФОВ

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

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

Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин ) и отрезков (ребер ), оба конца которых принадлежат заданному множеству точек (см. рис. 2.1).

(РИСУНОК 2.1)

В дальнейшем вершины графа мы будем обозначать латинскими буквами A , B ,C ,D . Иногда граф в целом будем обозначать одной заглавной буквой.

Определение 2.02. Вершины графа, которые не принадлежат ни одному ребру, называются изолированными .

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

Обозначение: O " – граф с вершинами, не имеющий ребер (рис. 2.2).

(РИСУНОК 2.2)

Определение 2.04. Граф, в котором каждая пара вершин соединена ребром, называется полным .

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

(РИСУНОК 2.3)

Определение 2.05. Степенью вершины называется число ребер, которым принадлежит вершина.

Обозначение: p (A ) – степень вершины A . Например, на рисунке 2.1: p (A )=2, p (B )=2, p (C )=2, p (D )=1, p (E )=1.

Определение 2.06. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k .

На рисунке 2.4 и 2.5 изображены однородные графы второй и третьей степени.

(РИСУНОК 2.4 и 2.5)

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

На рисунке 2.6 изображен исходный граф G , состоящий из четырех вершин и трех отрезков, а на рисунке 2.7 – дополнение данного графа – граф G " .

(РИСУНОК 2.6 и 2.7)

Мы видим, что на рисунке 2.5 ребра AC и BD пересекаются в точке, не являющейся вершиной графа. Но бывают случаи, когда данный граф необходимо представить на плоскости в таком виде, чтобы его ребра пересекались только в вершинах (этот вопрос будет рассмотрен подробно далее, в параграфе 5).

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

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

(РИСУНОК 2.8)

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

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

Граф – это совокупность двух множеств: множества точек, которые называются вершинами , и множества ребер А . Каждый элемент есть упорядоченная пара элементов множества , вершины и называются концевыми точками или концами ребра а . Граф называется конечным , если множества R и конечны.

Это определение графа должно быть дополнено в одном важном отношении. В определении ребра можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несущественен, т. е. если , то говорят, что a есть неориентированное ребро ; если же этот порядок существенен, то a называется ориентированным ребром (ориентированное ребро часто называется дугой ). В последнем случае называется также начальной вершиной , а – конечной вершиной ребра a . Граф называется неориентированным , если каждое его ребро неориентировано, и ориентированным , если ориентированы все его ребра. В ряде случаев естественно рассматривать смешанные графы, имеющие как ориентированные, так и неориентированные ребра.

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

Число ребер, инцидентных одной вершине , будем обозначать через . Это число называется локальной степенью или просто степенью графа в вершине . В случае ориентированного графа G обозначим через и число ребер, соответственно выходящих из вершины и входящих в . Эти числа называются локальными степенями G в . Если все числа конечны, то граф называется локально-конечным . Вершина степени 1 называется висячей . Вершина степени 0 называется изолированной .

Рисунок 14.1.

На рис. 14.1 и – параллельные ребра, – петля; вершина и ребро инцидентны друг другу; – смежные вершины, – смежные вершины; степень вершины равна трем, – висячая вершина, – изолированная.

Теорема 14.1. В графе G сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа: , где n – число вершин графа, m – число его ребер.

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

Примеры использования теории графов.

История возникновения теории графов.

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

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

Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.

В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "analysis situs"; понятие "точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной.

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

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

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

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

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

Теория графов «открывалась» независимо много раз: её с полным основанием можно считать разделом прикладной математики. В самом деле, наиболее раннее известное упоминание этой теории встречается в работах Эйлера, и хотя проблему, которой он занимался, можно рассматривать как обычную головоломку, псе же она возникла из практики.

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

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

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

Задача о кёнигсбергских мостах

Отцом теории графов (так же как и топологии) является Эйлер (1707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов.

В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке.

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

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

Вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.

Рисунок 1. Парк в городе Кенигсберге, 1736 г.

Рисунок 2. Граф к задаче о кенигсбергских мостах

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки.

Получился «граф». Этот граф показан на рисунке 2., где точки отмечены теми же буквами, что и четыре части суши.

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

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

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

Электрические цепи

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

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

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

Рисунок 3. Сеть N, соответствующий ей граф G .

Вместо этого он предложил простую, но эффективную методику (ставшую позднее стандартной процедурой), в соответствии с которой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его «остовных деревьев». На рисунке 3 дан пример электрической цепи N, соответствующего ей графа G.

Химические изомеры

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

Он стремился перечислить изомеры предельных (насыщенных) углеводородов С n Н 2 n + 2 с данным числом n атомов углерода; рисунок 4.

Рисунок 4. Изобутан

В социальной психологии.

В 1936 г. психолог Курт Леви н высказал предположение, что «жизненное пространство» индивидуума можно представить с помощью планарной карты 1).

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

Рисунок 5. Карта и соответствующий ей граф.

Подчеркнем, что К.Леви н фактически имел дело с графами, как это видно из рисунка 5.

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

Предположение Левина относится только к планарным картам, поскольку он всегда рисовал свои рисунки на плоскости. В последствии идея К.Левина была развита в социометрических процедурах.

В теории организаций

Графы могут быть представлены не только в строгой классической форме. Так жизненный цикл компании И.Адизеса представлен следующим форме.

Рисунок 6. Жизненный цикл компании

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

Производственные подразделения

Рис. Функциональная организационная структура

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

Такой теорией стала «Теория графов».

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

Начнём с определения, однозначного определения теория графов не имеет, ниже представлены три определения, но существуют и другие.

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

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

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

Неформально граф можно рассматривать как множество точек и соединяющих эти точки линий со стрелками или без них.

Первой работой теории графов как математической дисциплины считают статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам.

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

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

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

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

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

Основные определения
Графы, как уже отмечалось в примерах, есть способ „визуализации" связей между определенными объектами. Связи эти могут быть „направленными", как, например, в генеалогическом древе, или "ненаправленными" (сеть дорог с двусторонним движением). В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные (или направленные) и неориентированные.
Способы представления
До сих пор мы задавали ориентированные и неориентированные графы, изображая их с помощью рисунков. Можно задать граф как пару множеств, следуя определению, однако этот способ довольно громоздкий и представляет, скорее, теоретический интерес. Развитие алгоритмических подходов к анализу свойств графов требует иных способов описания графов, более пригодных для практических вычислений, в том числе с использованием ЭВМ. Рассмотрим три наиболее распространенных способа представления графов.
Деревья
Определение 5.5. Неориентированным деревом называют связный и ациклический неориентированный граф. Определение 5.6. Ориентированным деревом называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0.
Остовное дерево наименьшего веса
Следующая задача известна в теории графов под названием задачи Штейнера: на плоскости заданы п точек; нужно соединить их отрезками прямых таким образом, чтобы суммарная длина отрезков была наименьшей.
Методы систематического обхода вершин графа
Важными задачами теории графов являются задачи глобального анализа как неориентированных, так и ориентированных графов. К этим задачам относятся, например, задачи поиска циклов или контуров, вычисление длин путей между парами вершин, перечисление путей с теми или иными свойствами и т.п. Глобальный анализ графа следует отличать от локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа.
Задача о путях во взвешенных ориентированных графах
Изоморфизм графов
Для ориентированного графа (V, Е) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин. В неориентированном графе (V, Е) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u, v} ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением р, т.е. (u, v) ∈ р и (v, u) ∈ р.
Топологическая сортировка
Определение 5.17. Ориентированной сетью (или просто сетью) называют бесконтурный ориентированный граф*. Поскольку сеть является бесконтурным графом, можно показать, что существуют вершины (узлы) сети с нулевой полустепенью исхода, а также вершины (узлы) с нулевой полустепенью захода. Первые называют стоками или выходами сети, а вторые - источниками или входами сети.
Элементы цикломатики
При обсуждении алгоритма поиска в глубину в неориентированном графе рассматривался вопрос о поиске так называемых фундаментальных циклов графа. При этом под фундаментальным понимался цикл, содержащий в точности одно обратное ребро, и между фундаментальными циклами и обратными ребрами устанавливалось взаимно однозначное соответствие, фундаментальные циклы возникают всякий раз, как только фиксировано произвольное разбиение всех ребер неориентированного графа на древесные (формирующие некоторый максимальный оспьовный лес исходного графа) и обратные, причем в общем случае это разбиение может быть задано совершенно независимо от алгоритма поиска в глубину. Поиск в глубину есть лишь один из способов реализации такого разбиения.

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

Теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).

Задача о кенигсбергских мостах.

В прусском городке Кенигсберг на реке Прегал семь мостов. Можно ли найти маршрут прогулки, который проходит ровно 1 раз по каждому из мостов и начинается и заканчивается в одном месте?

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

Последовательность вершин (может быть с повторением), через которые проходит искомый маршрут, как и сам маршрут, называется Эйлеровым циклом .

Задача о трех домах и трех колодцах.

Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) Куратовским (1896 – 1979) в 1930 году.

Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой . Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. Гипотеза не доказана до сих пор.

Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера.

Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки…

Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.

Определение 7.1. Графом G = G (V , E ) называется совокупность двух конечных множеств: V – называемого множеством вершин и множества E пар элементов из V, т.е. EÍV´V, называемого множеством рёбер , если пары неупорядочены, или множеством дуг , если пары упорядочены.

В первом случае граф G (V , E ) называется неориентированным , во втором – ориентированным.

ПРИМЕР. Граф с множеством вершин V = {а,b,с} и множеством ребер Е ={{а, b}, {b, с}}

ПРИМЕР. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},

Если e=(v 1 ,v 2), еÎЕ, то говорят, что ребро е соединяет вершины v 1 и v 2 .

Две вершины v 1 ,v 2 называются смежными , если существует соединяющее их ребро. В этой ситуации каждая из вершин называется инцидентной соответствующему ребру.

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

Число вершин графа G обозначим v , а число ребер - e :

Геометрическое представление графов следующее:

1) вершина графа – точка в пространстве (на плоскости);

2) ребро неориентированного графа – отрезок;

3) дуга ориентированного графа – направленный отрезок.

Определение 7.2. Если в ребре e=(v 1 ,v 2) имеет место v 1 =v 2 , то ребро е называется петлёй . Если в графе допускается наличие петель, то он называется графом с петлями или псевдографом .

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

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

Определение 7.3. Граф G  (V  , E  ) называется подграфом (или частью ) графа G (V ,E ), если V  V , E  E . Если V  = V , то G  называется остовным подграфом G .

Пример 7 . 1 . Дан неориентированный граф.

Определение 7.4. Граф называется полным , если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K n .

Графы К 2 , К 3, К 4 и К 5 .

Определение 7.5. Граф G =G (V , E ) называется двудольным , если V можно представить как объединение непересекающихся множеств, скажем V =A B , так что каждое ребро имеет вид (v i , v j ), где v i A и v j B .

Каждое ребро связывает вершину из А с вершиной из В, но никакие две вершины из А или две вершины из В не являются связанными.

Двудольный граф называется полным двудольным графом K m , n , если A содержит m вершин, B содержит n вершин и для каждого v i A , v j B имеем (v i , v j )E .