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

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

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

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

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

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

В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "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 г. , Леонард Эйлер, задача о кенигсбергских мостах (Г. Кенигсберг расположен на берегах реки Прегель, в городе 7 мостов. Можно ли совершить прогулку, чтобы выйти из дома и вернуться обратно, пройдя по каждому мосту только один раз?) o Середина XIX в. , Г. Кирхгоф описание с помощью графов электрических цепей, А. Кэли химических схем o Как математическая дисциплина сформировалась в середине 30 -х гг. XX в. (1936 г, выход в свет o

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

o Головоломки, в которых требуется обрисовать некоторую фигуру, не прерывая и не повторяя линии, например или Сабли Магомета

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

Примеры графов o o Каркас любого многогранника в пространстве Схема линий в метро Структурные формулы молекул Генеалогическое дерево

Примеры задач, решаемых с помощью графов 1. Путешественники o В бюро по туризму составляют маршрут для путешественников, желающих проехать из города А в город В, осмотрев по пути все достопримечательности, расположенные в городах C, D, E, F, G, H, K, M. Составить маршрут поездки нужно таким образом, чтобы туристы посетили все указанные города и побывали в каждом из них ровно по одному разу.

o По условию задачи путешествие должно начаться в пункте А и закончится в пункте В. Заметим, что в города D и F ведут всего две дороги. Значит по этим дорогам путешественники обязательно проедут. Отметим их жирной линией. Тем самым определен участок маршрута CDEFG. Значит по дорогам AE, AG, EM туристы проезжать не будут (иначе они два раза посетят пункт E). Перечеркнем эти дороги. Отметим жирной линией участок AC, поскольку из A осталась только эта дорога. Перечеркнем CM (в С мы уже были). Через М остались неперечеркнуты две дороги: MH и MB, значит по ним туристы и поедут. Отметим их жирной линией. Осталась единственная возможность проехать из G в H

o Таким образом, мы нашли нужный маршрут. В этом нам помогла схема расположения городов и дорог, которая является на самом деле графом с 10 вершинами и 17 ребрами. Вершины A, D, F имеют степень два, вершины C и K – степень три, H, M, B – вершины четвертой степени, а G и E – пятой.

2. Знакомства o Может ли так случится, что в компании, состоящей из 8 человек, каждый знаком ровно с двумя другими людьми?

2. Знакомства (решение) o o Сопоставим участникам компании вершины графа, соединим две вершины ребром, если соответствующие два человека знакомы между собой. Чтобы каждый был знаком ровно с двумя другими людьми, любая вершина графа должна иметь степень 2. Примеры таких графов: Раз такие графы существуют, значит ситуация, описанная в задаче возможна.

3. Шахматный турнир o Пусть в турнире должны участвовать n шахматистов, все должны сыграть друг с другом ровно по одной партии. Сопоставим каждому участнику вершину графа, а каждой сыгранной парии ребро графа, соединяющее соответствующие вершины

Полный граф o o o До начала турнира граф состоит только из точек, у него нет ни одного ребра. Такие графы называются нуль-графами По окончании турнира каждый участник сыграл с любым другим и каждая пара вершина соединена между собой ребром. Такой граф называется полным. В полном графе с n вершинами степень каждой вершины равна (n-1) Неполный граф можно превратить в полный, добавив недостающие ребра. На рис. толстой линией изображен граф с 5 вершинами, который не является полным. Добавив

Ориентированный граф o o o Часто связи между объектами характеризуются определенной ориентацией (схема дорог с односторонним движением, подчиненность или старшинство в отношениях между людьми, результаты встреч между командами в спортивных состязаниях) Изображенный нами граф шахматного турнира не дает информации о том, кто же выиграл каждую партию. Можно на каждом ребре ставить стрелочку от вершины А к вершине В, если шахматист А проиграл шахматисту В, т. е. ориентировать ребра, указав на них направление Граф, на котором указано направление каждого ребра, называется

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

Маршрут графа o o o Маршрут длины m произвольного графа – это такая последовательность m ребер (не обязательно различных), в которой граничные вершины двух соседних ребер совпадают. Длина маршрута – количество ребер (если по ребру проходим 2 раза, то и считаем это ребро 2 раза) Маршрут замкнутый, если его начальная и конечная вершины совпадают Цепь - незамкнутый маршрут, в котором все ребра различны Простая цепь - цепь, в которой все вершины различны (пример – задача 1. (О путешественниках)

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

o o o o B-D-A-C-D-A – незамкнутый маршрут A-C-D-A-B-D-A - замкнутый маршрут A-C-D-E-F-D-B – цепь A-B-G-H – простая цепь A-C-D-E-F-D-A – цикл D-E-F-D – простой цикл Посчитайте длину этих маршрутов Определите к какому типу относятся маршруты A-B-D-F-E-D-C-A; A-D-E; D-E-F-D; A-C-D-B-A;

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

Задача 4. Деление на части o Разрезаем лист бумаги на 3 части. Некоторые из полученных листиков снова разрезаем на 3 части. Некоторые из разрезанных листиков – еще раз на три части и т. д. Сколько получится отдельных листиков, если сделано k разрезаний?

Задача 4. Деление на части (решение) o o Листы бумаги вершины графа. Закрашенные вершины соответствуют разрезанным листикам, незакрашенные – неразрезанным. При разрезании одного листика число листиков увеличивается на 2. Если всего было разрезано k листиков, то число листиков увеличится на 2 k. Первоначально у нас был один лист. , поэтому после k разрезаний получится (2 k+1) листик. На графе проиллюстрирован случай, когда k=6. (2 k+1) =13

Теорема о сумме степеней вершин графа o o Пусть граф Г имеет N вершин и M рёбер. Каждая i-ая вершина имеет степень di Поскольку каждое ребро соединяет две вершины, оно добавляет двойку к сумме степеней вершин графа, поэтому сумма степеней вершин равна удвоенному количеству ребер

Задача 5. Количество дорог o Может ли в государстве, в котором из каждого города выходят ровно 3 дороги быть ровно 100 дорог?

Задача 5. Количество дорог (решение) o Предположим, такая ситуация возможна. В государстве N городов, из каждого города выходят 3 дороги. Значит мы имеем граф с N вершинами, каждая из которых имеет степень 3. Следовательно, сумма степеней вершин равна 3 N, а число ребер – 3 N/2. Это число по условию равно 100. Т. е. 3 N/2=100 или 3 N=200. Такого натурального числа не существует. Значит в этом государстве не может быть 100 дорог.

Самостоятельно o В некотором царстве царь издал указ: построить 7 городов и соединить их дорогами так, чтобы из каждого города выходило по 3 дороги. Выполним ли такой приказ? Станет ли он выполним, если из каждого города будут выходить 4 дороги?

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

Решение задачи о кенигсбергских мостах o o o Обозначим части города A, B, C, D. Это будут вершины графа. Мосты, соединяющие части города – ребра графа. Эйлер показал, что задача не имеет решения, т. е. не существует цикла, проходящего по всем рёбрам точно по одному разу. Ведь если бы такой цикл существовал, то в каждой вершине графа было бы столько входящих в неё рёбер, сколько и выходящих из неё, т. е. в каждой вершине графа было бы чётное число рёбер (войдя в вершину по одному ребру, мы должны выйти из нее по другому ребру). Однако это условие, очевидно, не выполнено для графа, представляющего карту Кёнигсберга. Убедитесь в этом, определив степень каждой вершины графа

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

Необходимое и достаточное условие существования эйлерового графа o o o Для того, чтобы граф имел эйлерову линию, он должен быть связным. Как и в задаче о кёнигсбергских мостах, ясно, что каждая эйлерова линия должна входить в каждую вершину и выходить из неё одно и то же число раз, т. е. степени всех вершин графа должны быть чётными. Значит, чтобы граф был эйлеровым, необходимы два условия: связность графа и чётность степеней всех его вершин. Эйлер доказал, что эти условия являются также и достаточными: связный граф, степени всех вершин которого чётные, обладает эйлеровой линией.

Самостоятельно o Определите, являются ли эти графы эйлеровыми? (можно ли обвести их одним росчерком пера, не прерывая и не повторяя линии, и вернуться в ту точку, с которой начали) Если да, найдите в них эйлеровы циклы (покажите, как это сделать)

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

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

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

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

Самостоятельно o В соответствии с теоремой об эйлеровом пути определите: существует ли эйлеров путь в графах? (можно ли расчертить одним росчерком без повторений, начав в одной из вершин, а кончив в другой). Если существует, найдите его (покажите, как это сделать)

Задача 7. 2. О кенигсбергских мостах для воображаемого города (самостоятельно) o На рисунке план воображаемого города, который Эйлер использовал для иллюстрации в своей работе. Начертите граф для плана Эйлера и определите, существует ли в нём эйлеров цикл? А эйлеров путь? Если да – то найдите его

Задача 8. Зоопарк (самостоятельно) o На рисунке схема зоопарка (вершины графа – вход, выход, перекрёстки, повороты, тупики, рёбра-дорожки, вдоль которых расположены клетки). Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути, т. е. найдите эйлеров путь.

Материал из Википедии - свободной энциклопедии

Тео́рия гра́фов - раздел дискретной математики , изучающий свойства графов . В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами . В строгом определении графом называется такая пара множеств. $G\; =\; (V,\; E)$, где $V$ есть подмножество любого счётного множества, а $E$ - подмножество $V\; \backslash times\; V$.

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

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

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

Родоначальником теории графов считается Леонард Эйлер . В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах , ставшей впоследствии одной из классических задач теории графов.

Терминология теории графов

Изображение графов на плоскости

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

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

Некоторые задачи теории графов

• Проблема семи мостов Кёнигсберга - один из первых результатов в теории графов, опубликован Эйлером в .
• Проблема четырёх красок - была сформулирована в 1852 году , но неклассическое доказательство получено лишь в 1976 году (достаточно 4-х красок для карты на сфере (плоскости)).
• Задача коммивояжёра - одна из наиболее известных NP-полных задач.
• Задача о клике - ещё одна NP-полная задача.
• Нахождение минимального стягивающего (остовного) дерева .
• Изоморфизм графов - можно ли путём перенумерации вершин одного графа получить другой.
• Планарность графа - можно ли изобразить граф на плоскости без пересечений ребер (или с минимальным числом слоёв, что находит применение при трассировке межсоединений элементов печатных плат или микросхем).

Применение теории графов

См. также

Напишите отзыв о статье "Теория графов"

Примечания

Литература

• Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002. - 336 с. ISBN 5-86134-101-X .
• Diestel R. . - NY: Springer-Verlag, 2005. - С. 422.
• Басакер Р., Саати Т.
• Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. - М .: Высш. школа, 1976. - С. 392.
• Берж К.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)
• Зыков А. А. . - М .: «Вузовская книга» , 2004. - С. 664. - ISBN 5-9502-0057-8 . (М.: Наука, 1987. 383c.)
• Химические приложения топологии и теории графов. Под ред. Р. Кинга. Пер. с англ. М.: Мир, 1987.
• Кирсанов М. Н. Графы в Maple. М.: Физматлит, 2007. 168 c. vuz.exponenta.ru/PDF/book/GrMaple.pdf eqworld.ipmnet.ru/ru/library/books/Kirsanov2007ru.pdf
• Кристофидес Н.
• Кормен Т. Х. и др. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М .: Вильямс , 2006. - С. 1296. - ISBN 0-07-013151-1 .
• Оре О. . - 2-е изд. - М .: Наука , 1980. - С. 336.
• Салий В. Н. Богомолов А. М. . - М .: Физико-математическая литература, 1997. - ISBN 5-02-015033-9 .
• Свами М., Тхуласираман К.
• Татт У.
• Уилсон Р.
• Харари Ф. . - М .: Мир , 1973. (Изд. 3, М.: КомКнига, 2006. - 296 с.)
• Харари Ф., Палмер Э. . - Мир , 1977.
• Сергей Мельников // Наука и жизнь . - 1996. - Вып. 3 . - С. 144-145 . В статье идёт речь об игре на графе Сим, придуманной Густавом Симмонсом.

Ссылки

• : программа, предоставляющая пользователю, широкий набор средств и методов для визуализации и поиска информации в графах

Классический анализ Теория функций Дифференциальные и интегральные уравнения

Отрывок, характеризующий Теория графов

Но прежде чем он договорил эти слова, князь Андрей, чувствуя слезы стыда и злобы, подступавшие ему к горлу, уже соскакивал с лошади и бежал к знамени.
– Ребята, вперед! – крикнул он детски пронзительно.
«Вот оно!» думал князь Андрей, схватив древко знамени и с наслаждением слыша свист пуль, очевидно, направленных именно против него. Несколько солдат упало.
– Ура! – закричал князь Андрей, едва удерживая в руках тяжелое знамя, и побежал вперед с несомненной уверенностью, что весь батальон побежит за ним.
Действительно, он пробежал один только несколько шагов. Тронулся один, другой солдат, и весь батальон с криком «ура!» побежал вперед и обогнал его. Унтер офицер батальона, подбежав, взял колебавшееся от тяжести в руках князя Андрея знамя, но тотчас же был убит. Князь Андрей опять схватил знамя и, волоча его за древко, бежал с батальоном. Впереди себя он видел наших артиллеристов, из которых одни дрались, другие бросали пушки и бежали к нему навстречу; он видел и французских пехотных солдат, которые хватали артиллерийских лошадей и поворачивали пушки. Князь Андрей с батальоном уже был в 20 ти шагах от орудий. Он слышал над собою неперестававший свист пуль, и беспрестанно справа и слева от него охали и падали солдаты. Но он не смотрел на них; он вглядывался только в то, что происходило впереди его – на батарее. Он ясно видел уже одну фигуру рыжего артиллериста с сбитым на бок кивером, тянущего с одной стороны банник, тогда как французский солдат тянул банник к себе за другую сторону. Князь Андрей видел уже ясно растерянное и вместе озлобленное выражение лиц этих двух людей, видимо, не понимавших того, что они делали.
«Что они делают? – думал князь Андрей, глядя на них: – зачем не бежит рыжий артиллерист, когда у него нет оружия? Зачем не колет его француз? Не успеет добежать, как француз вспомнит о ружье и заколет его».
Действительно, другой француз, с ружьем на перевес подбежал к борющимся, и участь рыжего артиллериста, всё еще не понимавшего того, что ожидает его, и с торжеством выдернувшего банник, должна была решиться. Но князь Андрей не видал, чем это кончилось. Как бы со всего размаха крепкой палкой кто то из ближайших солдат, как ему показалось, ударил его в голову. Немного это больно было, а главное, неприятно, потому что боль эта развлекала его и мешала ему видеть то, на что он смотрел.
«Что это? я падаю? у меня ноги подкашиваются», подумал он и упал на спину. Он раскрыл глаза, надеясь увидать, чем кончилась борьба французов с артиллеристами, и желая знать, убит или нет рыжий артиллерист, взяты или спасены пушки. Но он ничего не видал. Над ним не было ничего уже, кроме неба – высокого неба, не ясного, но всё таки неизмеримо высокого, с тихо ползущими по нем серыми облаками. «Как тихо, спокойно и торжественно, совсем не так, как я бежал, – подумал князь Андрей, – не так, как мы бежали, кричали и дрались; совсем не так, как с озлобленными и испуганными лицами тащили друг у друга банник француз и артиллерист, – совсем не так ползут облака по этому высокому бесконечному небу. Как же я не видал прежде этого высокого неба? И как я счастлив, я, что узнал его наконец. Да! всё пустое, всё обман, кроме этого бесконечного неба. Ничего, ничего нет, кроме его. Но и того даже нет, ничего нет, кроме тишины, успокоения. И слава Богу!…»

На правом фланге у Багратиона в 9 ть часов дело еще не начиналось. Не желая согласиться на требование Долгорукова начинать дело и желая отклонить от себя ответственность, князь Багратион предложил Долгорукову послать спросить о том главнокомандующего. Багратион знал, что, по расстоянию почти 10 ти верст, отделявшему один фланг от другого, ежели не убьют того, кого пошлют (что было очень вероятно), и ежели он даже и найдет главнокомандующего, что было весьма трудно, посланный не успеет вернуться раньше вечера.
Багратион оглянул свою свиту своими большими, ничего невыражающими, невыспавшимися глазами, и невольно замиравшее от волнения и надежды детское лицо Ростова первое бросилось ему в глаза. Он послал его.
– А ежели я встречу его величество прежде, чем главнокомандующего, ваше сиятельство? – сказал Ростов, держа руку у козырька.
– Можете передать его величеству, – поспешно перебивая Багратиона, сказал Долгоруков.
Сменившись из цепи, Ростов успел соснуть несколько часов перед утром и чувствовал себя веселым, смелым, решительным, с тою упругостью движений, уверенностью в свое счастие и в том расположении духа, в котором всё кажется легко, весело и возможно.
Все желания его исполнялись в это утро; давалось генеральное сражение, он участвовал в нем; мало того, он был ординарцем при храбрейшем генерале; мало того, он ехал с поручением к Кутузову, а может быть, и к самому государю. Утро было ясное, лошадь под ним была добрая. На душе его было радостно и счастливо. Получив приказание, он пустил лошадь и поскакал вдоль по линии. Сначала он ехал по линии Багратионовых войск, еще не вступавших в дело и стоявших неподвижно; потом он въехал в пространство, занимаемое кавалерией Уварова и здесь заметил уже передвижения и признаки приготовлений к делу; проехав кавалерию Уварова, он уже ясно услыхал звуки пушечной и орудийной стрельбы впереди себя. Стрельба всё усиливалась.
В свежем, утреннем воздухе раздавались уже, не как прежде в неравные промежутки, по два, по три выстрела и потом один или два орудийных выстрела, а по скатам гор, впереди Працена, слышались перекаты ружейной пальбы, перебиваемой такими частыми выстрелами из орудий, что иногда несколько пушечных выстрелов уже не отделялись друг от друга, а сливались в один общий гул.
Видно было, как по скатам дымки ружей как будто бегали, догоняя друг друга, и как дымы орудий клубились, расплывались и сливались одни с другими. Видны были, по блеску штыков между дымом, двигавшиеся массы пехоты и узкие полосы артиллерии с зелеными ящиками.
Ростов на пригорке остановил на минуту лошадь, чтобы рассмотреть то, что делалось; но как он ни напрягал внимание, он ничего не мог ни понять, ни разобрать из того, что делалось: двигались там в дыму какие то люди, двигались и спереди и сзади какие то холсты войск; но зачем? кто? куда? нельзя было понять. Вид этот и звуки эти не только не возбуждали в нем какого нибудь унылого или робкого чувства, но, напротив, придавали ему энергии и решительности.
«Ну, еще, еще наддай!» – обращался он мысленно к этим звукам и опять пускался скакать по линии, всё дальше и дальше проникая в область войск, уже вступивших в дело.
«Уж как это там будет, не знаю, а всё будет хорошо!» думал Ростов.
Проехав какие то австрийские войска, Ростов заметил, что следующая за тем часть линии (это была гвардия) уже вступила в дело.
«Тем лучше! посмотрю вблизи», подумал он.
Он поехал почти по передней линии. Несколько всадников скакали по направлению к нему. Это были наши лейб уланы, которые расстроенными рядами возвращались из атаки. Ростов миновал их, заметил невольно одного из них в крови и поскакал дальше.
«Мне до этого дела нет!» подумал он. Не успел он проехать нескольких сот шагов после этого, как влево от него, наперерез ему, показалась на всем протяжении поля огромная масса кавалеристов на вороных лошадях, в белых блестящих мундирах, которые рысью шли прямо на него. Ростов пустил лошадь во весь скок, для того чтоб уехать с дороги от этих кавалеристов, и он бы уехал от них, ежели бы они шли всё тем же аллюром, но они всё прибавляли хода, так что некоторые лошади уже скакали. Ростову всё слышнее и слышнее становился их топот и бряцание их оружия и виднее становились их лошади, фигуры и даже лица. Это были наши кавалергарды, шедшие в атаку на французскую кавалерию, подвигавшуюся им навстречу.
Кавалергарды скакали, но еще удерживая лошадей. Ростов уже видел их лица и услышал команду: «марш, марш!» произнесенную офицером, выпустившим во весь мах свою кровную лошадь. Ростов, опасаясь быть раздавленным или завлеченным в атаку на французов, скакал вдоль фронта, что было мочи у его лошади, и всё таки не успел миновать их.
Крайний кавалергард, огромный ростом рябой мужчина, злобно нахмурился, увидав перед собой Ростова, с которым он неминуемо должен был столкнуться. Этот кавалергард непременно сбил бы с ног Ростова с его Бедуином (Ростов сам себе казался таким маленьким и слабеньким в сравнении с этими громадными людьми и лошадьми), ежели бы он не догадался взмахнуть нагайкой в глаза кавалергардовой лошади. Вороная, тяжелая, пятивершковая лошадь шарахнулась, приложив уши; но рябой кавалергард всадил ей с размаху в бока огромные шпоры, и лошадь, взмахнув хвостом и вытянув шею, понеслась еще быстрее. Едва кавалергарды миновали Ростова, как он услыхал их крик: «Ура!» и оглянувшись увидал, что передние ряды их смешивались с чужими, вероятно французскими, кавалеристами в красных эполетах. Дальше нельзя было ничего видеть, потому что тотчас же после этого откуда то стали стрелять пушки, и всё застлалось дымом.
В ту минуту как кавалергарды, миновав его, скрылись в дыму, Ростов колебался, скакать ли ему за ними или ехать туда, куда ему нужно было. Это была та блестящая атака кавалергардов, которой удивлялись сами французы. Ростову страшно было слышать потом, что из всей этой массы огромных красавцев людей, из всех этих блестящих, на тысячных лошадях, богачей юношей, офицеров и юнкеров, проскакавших мимо его, после атаки осталось только осьмнадцать человек.

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

Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.

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

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

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

Введение

Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов.

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

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

Теоретическая часть

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

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

Рис. 1.

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

Рис. 2

3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 3). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно - объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.