Основы теории графов история возникновения и развития.  Граф это что такое Граф: определение — История.НЭС История теории графов

вершин (узлов), соединённых рёбрами . В строгом определении графом называется такая пара множеств G = (V , E) {\displaystyle G=(V,E)} , где V {\displaystyle V} есть подмножество любого счётного множества , а E {\displaystyle E} - подмножество V × V {\displaystyle V\times V} .

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

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

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

Родоначальником теории графов считается Леонард Эйлер . В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах , ставшей впоследствии одной из классических задач теории графов. Термин «граф» впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature [ ] .

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

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

См. также

Примечания

Литература

• Дистель Р. Теория графов Пер. с англ. - Новосибирск: Издательство института математики, 2002. - 336 с. ISBN 5-86134-101-X .
• Diestel R. Graph Theory, Electronic Edition . - NY: Springer-Verlag, 2005. - С. 422.
• Басакер Р., Саати Т. Конечные графы и сети. М.: Наука, 1974. 368c.
• Белов В. В., Воробьев Е. М., Шаталов В. Е. Теория графов. - М. : Высш. школа, 1976. - С. 392.
• Берж К. Теория графов и её приложения. М.: ИЛ, 1962. 320c.
• Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384с. (Изд.2, испр. М.: УРСС, 2009. 392 с.)

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

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

Правило Эйлера:

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

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

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

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

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

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

Тео́рия гра́фов. 1

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

Правило Эйлера. 1

Литература

1. Белов Теория Графов, Москва, «Наука», 1968.

2. Новые педагогические и информационные технологии Е.С.Полат, Москва, «Akademia» 1999 г.

3. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат , 1988.

4. Кук Д., Бейз Г. Компьютерная математика. – М.: Наука , 1990.

5. Нефедов В.Н., Осипова В.А. Курс дискретной математики. – М.: Издательство МАИ , 1992.

6. Оре О. Теория графов. – М.: Наука , 1980.

7. Исмагилов Р.С., Калинкин А.В. Матеpиалы к пpактическим занятиям по куpсу: Дискpетная математика

Родоначальником теории графов принято считать математика Леонарда Эйлера (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 ) .

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

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

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

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

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

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