4 история возникновения теории графов основоположник. Основы теории графов история возникновения и развития

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

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

(РИСУНОК 1.1)

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

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

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

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

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

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

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

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

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

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

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

Графы строят для того, чтобы отобразить отношения на множествах . Пусть, например, множество A = {a 1 , a 2 , ... a n } - множество людей, а каждый элемент будет отображён в виде точки. Множество B = {b 1 , b 2 , ... b m } - множество связок (прямых, дуг, отрезков - пока не важно). На множестве A задано отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой. Естественно, число знакомых у одних людей может отличаться от числа знакомых у других людей, а некоторые вполне могут и не быть ни с кем знакомы (такие элементы будут точками, не соединёнными ни с одной другой). Вот и получился граф!

То, что мы сначала назвали "точками", следует называть вершинами графа, а то, что называли "связками" - рёбрами графа.

Теория графов не учитывает конкретную природу множеств A и B . Существует большое количество самых разных конкретных задач, при решении которых можно временно забыть о специфическом содержании множеств и их элементов. Эта специфика никак не сказывается на ходе решения задачи, независимо от её трудности! Например, при решении вопроса о том, можно ли из точки a добраться до точки e , двигаясь только по соединяющим точки линиям, неважно, имеем ли мы дело с людьми, городами, числами и т.д. Но, когда задача решена, мы получаем решение, верное для любого содержания, которое было смоделировано в виде графа. Не удивительно поэтому, что теория графов - один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с собеседником и вопросы любви, и вопросы музыки или спорта, и вопросы решения различных задач, причем делает это без всякого перехода (переключения), без которого в подобных случаях не обойтись человеку.

А теперь строгие математические определения графа.

Определение 1. Графом называется система объектов произвольной природы (вершин) и связок (рёбер), соединяющих некоторые пары этих объектов.

Определение 2. Пусть V – (непустое) множество вершин, элементы v ∈V – вершины. Граф G = G (V ) с множеством вершин V есть некоторое cемейство пар вида: e = (a , b ) , где a ,b ∈V , указывающих, какие вершины остаются соединёнными. Каждая пара e = (a , b ) - ребро графа. Множество U - множество рёбер e графа. Вершины a и b – концевые точки ребра e .

Графы как структура данных. Широким применением теории графов в компьютерных науках и информационных технологиях обусловлено добавлением к вышеизложенным определениям понятия графа как структуры данных. В компьютерных науках и информационных технологиях граф определяется как нелинейная структура данных. Что же тогда - линейная структура данных и чем от них отличаются графы? Линейные структуры данных характеризуются тем, что связывают элементы отношениями типа "простого соседства". Линейными структурами данных являются, например, массивы, таблицы, списки, очереди, стеки, строки. В противоположность им нелинейные структуры данных - такие, в которых элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порождённые и подобные. Итак, граф - нелинейная структура данных.

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

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

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

Классические задачи теории графов и их решения

Один из первых опубликованных примеров работ по теории графов и применения графов - работа о "задаче с Кёнигсбергскими мостами" (1736 г.), автором которой является выдающийся математик 18-го века Леонард Эйлер. В задаче даны река, острова, которые омываются этой рекой, и несколько мостов. Вопрос задачи: возможно ли, выйдя из некоторого пункта, пройти каждый мост только по одному разу и вернуться в начальный пункт? (рисунок ниже)

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

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

По устоявшейся традиции эйлеровым графом называется граф, в котором можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер. Задача средней трудности на эйлеровы графы - в материале "Основные виды графов ".

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

Кэли в 1858 г., занимаясь чисто практическими задачами органической химии, открыл важный класс графов, называемых деревьями. Он стремился перечислить изомеры насыщенных углеводородов, с данным числом атомов углерода. Кэли прежде всего сформулировал задачу абстрактно: найти число всех деревьев с p вершинами, каждое из которых имеет вершины со степенями 1 и 4. Ему не удалось сразу решить эту задачу, и он стал изменять её формулировку таким образом, чтобы можно было решить новую задачу о перечислении:

• корневых деревьев (в которых выделена одна из вершин);
• всех деревьев;
• деревьев, у которых степени вершин не превышают 4;
• деревьев, у которых степени вершин равны 1 и 4 (постановка задачи из химии).

Задачи с графами для закрепления основных понятий

Пример 1. Пусть A - множество чисел 1, 2, 3 : A = {1, 2, 3} . Построить граф для отображения отношения "

Решение. Очевидно, что числа 1, 2, 3 следует представить в виде вершин графа. Тогда каждую пару вершин должно соединять одно ребро. Решая эту задачу, мы пришли к таким основным понятиям теории графов, как ориентированные и неориентированные графы . Неориентированные графы - такие, рёбра которых не имели направления. Или, как говорят ещё чаще, порядок двух концов ребра не существенен. В самом деле, граф, построенный в самом начале этого урока и отображавший отношение знакомства между людьми, не нуждается в направлениях рёбер, так как можно утверждать, что "человек номер 1" знаком с "человеком номер 2" в той же мере, как и "человек номер 2" с "человеком номер 1". В нашем же нынешнем примере одно число меньше другого, но не наоборот. Поэтому соответствующее ребро графа должно иметь направление, показывающее, какое всё же число меньше другого. То есть, порядок концов ребра существенен. Такой граф (с рёбрами, имеющими направление) называется ориентированным графом или орграфом.

Итак, в нашем множестве A число 1 меньше числа 2 и числа 3, а число 2 меньше числа 3. Этот факт отображаем рёбрами, имеющими направление, что показывается стрелками. Получаем следующий граф:

Пример 2. Пусть A - множество чисел 2, 4, 6, 14 : A = {2, 4, 6, 14} . Постоить граф для отображения отношения "делится нацело на" на этом множестве.

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

Пример 3. Пусть даны множества A = {α, β, γ} и B = {a, b, c} . Построить граф для отображения отношения "декартово произведение множеств".

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

Пример 4. В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пётр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений "Игорь работает с объектами О4, О7", "Сергей работает с объектами О1, О2, О3, О5, О6", "Пётр работает с объектом О8".

Решение. Граф, отображающий данные отношения, будет так же двудольным, так как менеджер не работает с менеджером и объект не работает с объектом. Однако, в отличии от предыдущего примера, граф будет ориентированным. В самом деле, например, Игорь работает с объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость давать рёбрам направления может показаться "математической тупостью". Но всё же, и это вытекает из строгого характера математики, если отношение носит односторонний характер, то давать направления рёбрам нужно. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для планирования, где тоже применяются графы и маршрут по вершинам и рёбрам должен проходить строго в заданном направлении. Итак, получаем следующий ориентированный двудольный граф:

И вновь к примерам с числами.

Пример 5. Пусть задано множество C = {2, 3, 5, 6, 15, 18} . Построить граф, реализующий отношение, определяющее все пары чисел a и b из множества C , у которых при делении второго элемента на первый получаем частное, которое является целым числом больше 1.

Решение. Граф, отображающий данные отношения, будет ориентированным, так как в условии есть упоминание о втором и первом элементе, то есть, ребро будет направлено от первого элемента ко второму. Из этого однозначно понятно, какой элемент является перым, а какой вторым. Ещё добавим терминологии: ориентированные рёбра принято называть дугами. В нашем графе будет 7 дуг: e 1 = (3, 15) , e 2 = (3, 18) , e 3 = (5, 15) , e 4 = (3, 6) , e 5 = (2, 18) , e 6 = (6, 18) , e 7 = (2, 6) . В этом примере рёбра (дуги) графа просто пронумерованы, но порядковые номера - не единственное, что можно приписать дуге. Дуге можно приписать также весы означающие, например, стоимость пересылки груза из одного пункта в другой. Но с весами дуг мы познакомимся позже и подробнее. Итак, получаем следующий ориентированный граф:

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

Пример 6. На кусочке шахматной доски размером 3 Х 3 размещены два белых коня и два чёрных коня так, как показано на рисунке ниже.

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

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

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

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

Пример 7. Задача о волке, козе и капусте. На одном берегу реки находятся человек (Ч), лодка, волк (В), коза (Кз) и капуста (Кп). В лодке одновременно могут находиться человек и не более одного из перевозимых объектов. Человек должен перевезти на другой берег все объекты, соблюдая условие: нельзя оставлять без присмотра волка вместе с козой и козу вместе с капустой.

Решение. В конструируемом графе вершины - конфигурации, а рёбра - отношение "связь одним плаваньем лодки" между конфигурациями. Конфигурация означает расположение объектов на первоначальном берегу и на противоположном берегу. Каждая конфигурация отображается в виде (A |B ) , где A - объекты, находящиеся на первоначальном берегу, а B - объекты, находящиеся на противоположном берегу. Первоначальная конфигурация, таким образом, - (ЧВКпКз | ) . Например, после переправки на другой берег козы конфигурация будет (ВКп |ЧКз ) . Конечная конфигурация всегда ( |ЧВКпКз ) . Теперь можем построить граф, зная уже, что означают вершины и рёбра:

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

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

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

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

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

Графы и задача о потоках

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

Каждая дуга графа отображает трубу. Числа над дугами (весы) - пропускная способность труб. Узлы - места соединения труб. Вода течёт по трубам только в одном направлении. Узел S - источник воды, узел T - сток. Требуется максимизировать объём воды, протекающей от источника к стоку.

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

Графы и сетевое планирование

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

PERT - Program (Project) Evaluation and Review Technique - техника оценки и анализа программ (проектов), которая используется при управлении проектами.

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

Если в сети есть дуги (a , b ) и (b , c ) , то работа, представленная дугой (a , b ) , должна быть завершена до начала выполнения работы, представленной дугой (b , c ) . Каждая вершина (v i ) представляет момент времени, к которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (v i ) .

В таком графе:

• одна вершина, не имеющая предшественников, определяет момент времени начала выполнения работ;
• одна вершина, не имеющая последователей, соответствует моменту времени завершения комплекса работ.

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

Весь блок "Теория графов"

История возникновения и развития теории графов 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 На рисунке схема зоопарка (вершины графа – вход, выход, перекрёстки, повороты, тупики, рёбра-дорожки, вдоль которых расположены клетки). Найдите маршрут, по которому экскурсовод мог бы провести посетителей, показав им всех зверей и не проходя более одного раза ни одного участка пути, т. е. найдите эйлеров путь.

нем. Graf), дворянский титул. В России введен Петром I (первым его получил в 1706 Б. П. Шереметев). В конце 19 в. учтено свыше 300 графских родов. Ликвидирован Декретом ВЦИК и Совнаркома от 11.11.1917.

Отличное определение

Неполное определение ↓

Граф

Антон (Graf, Anton) 1736, Винтертур - 1813, Дрезден. Немецкий живописец. Учился в 1753-1756 у И. У. Шелленберга в Винтертуре, затем у И. Я. Хайда в Аугсбурге. Работал как портретист в Регенсбурге, Винтертуре, Аугсбурге, Мюнхене, Цюрихе. С 1766 - придворный художник в Дрездене. С 1789 - профессор дрезденской Академии художеств. Член берлинской, венской, мюнхенской академий художеств. Много путешествовал по Германии и Швейцарии. Портретист, писал также пейзажи, занимался миниатюрой. Ранние произведения художника исполнены в традиции парадного барочного портрета. Образы знатных особ королевского дворца Пруссии полны торжественности и представительности в портретах Фридрих, принц Прусский (1777-1778), Фредерика, принцесса Прусская (1787), Фридрих Вильгельм II, король Пруссии (1788, все - Берлин, Шарлоттенбург). Сильная светотень и теплая колористическая гамма свидетельствуют об увлечении молодого художника манерой Рембрандта. В 1780-1790-е Граф часто пишет модели на фоне пейзажа, несколько смягчающего напряженность, статику фигур в его портретах (Генрих VIII, 1804, Германия, частное собрание; И. Ф. фон Тильман, Нюрнберг, Германский нац. музей). В духе неоклассицистических вкусов эпохи изображает портретируемых в виде античных граций в пейзаже (Фредерика Хиллендорф, 1803, Германия, частное собрание). Более глубоки по передаче внутреннего состояния портреты близких художнику людей: Художник К. К. Люнвиг (1808, Гамбург, Кунстхалле), лирические женские образы - Луиза Элизабета Функ (1790, Лейпциг, Музей изобразительных искусств), Каролина Сюзанна Граф (1805, Гамбург, Кунстхалле). Тонкой светотеневой моделировкой подчеркнута присущая образам Графа четкая пластика фигур. Воздушное сфумато, окутывающее фигуры, свидетельствует об изучении приемов английского портрета XVIII в. Портреты выдающихся деятелей эпохи Просвещения - С. Гесснера (1765-1766, Цюрих, Кунстхалле), Г. Э. Лессинга (1771, Лейпциг, библиотека Университета), К. М. Виланда (1794, Веймар, Музей Гете), И. Г. Зульцера (1771, Винтертур, Кунстхалле) - пожалуй, самое значительное, что было создано художником. В портретах тестя художника И. Г. Зульцера, известного немецкого философа, эстетика и математика, и С. Гесснера, швейцарского поэта, автора поэтического сборника Идиллии (1756), Граф использует схему барочного портрета, изображая модели в момент как бы прерванного движения. Подлинный художник века Просвещения, Граф стремится раскрыть одухотворенность и светлый ум людей, ставших культурным достоянием нации. Портреты написаны на темном фоне, как и ряд других поздних произведений (Х. И. Медем, 1796; Г. Л. Гогель, 1796, оба - Санкт-Петербург, Гос. Эрмитаж). Интерес к психологически углубленной разработке образа присущ и автопортретам художника. В ранних автопортретах 1765 (Нью-Йорк, Историческое общество) и 1766 (Дрезден, Картинная галерея) мотив прерванного движения вносит некоторую традиционность в композиционное решение. Поздние работы (1794-1795, Дрезден, Картинная галерея; 1808, Винтертур, Кунстхалле) создают образ художника, чье творчество обозначило многие важные явления немецкой культуры XVIII в., закладывая традиции реалистической образности последующего столетия. В поздний период художником был написан ряд пейзажей, характеризующих прекрасное владение рисунком с натуры, интерес к пленэру, разработке проблемы "пейзажа настроения" (Вид окрестностей Дрездена, 1800; Утро, ок. 1800; Полдень, ок. 1800; Вечер, ок. 1800, все - Дрезден, Картинная галерея).

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

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

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

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

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

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

В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "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. Жизненный цикл компании

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

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

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

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

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

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

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

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

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

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