Методические пособия по технологии. Шерстяная костюмная ткань, тик

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

РЕФЕРАТ

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

Выполнила:

Зудина Т.В.

Владимир 2001

1. Введение

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

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

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

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

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

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

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

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

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

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

(РИСУНОК 1.1)

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

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

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

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

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

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

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

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

(РИСУНОК 1.2)

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

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

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

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

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

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

(РИСУНОК 2.1)

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

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

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

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

(РИСУНОК 2.2)

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

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

(РИСУНОК 2.3)

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

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

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

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

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

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

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

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

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

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

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

(РИСУНОК 2.8)

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

Учебное издание

Ююкин Николай Алексеевич

ЛР № . Подписано в печать

Уч. Изд. л.. , .

Воронежский государственный технический университет

394026 Воронеж, Московский просп. 14

СПРАВОЧНИК МАГНИТНОГО ДИСКА

Кафедра высшей математики и физико-математического моделирования

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Воронеж 2004

ВВЕДЕНИЕ

Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися по специальностям:

090102 – Компьютерная безопасность;

090105 – Комплексное обеспечение информационной безопасности автоматизированных систем;

090106 - Информационная безопасность телекоммуникационных систем.

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

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

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

в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цикла

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

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

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

Достижению данной цели служат следующие задачи:

изучить максимально широкий круг понятий теории графов;

получить навыки решения учебных и практических задач;

овладеть методами оптимизации;

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

Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Математическая логика и теория алгоритмов”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении общепрофессиональных и специальных дисциплин.

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

1.1. Задачи теории графов.

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

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

Первая задача . Задача о Кенигсбергских мостах была поставлена и решена Эйлером в 1786 году. Город располагался на берегах и двух островах реки Преголи. Острова между собой и берегами были связаны семью мостами, как показано на рисунке.

Возникал вопрос: можно ли выйдя из дома, вернуться обратно, проходя по каждому мосту ровно один раз?

Вторая задача . Задача о трех домах и трех колодцах. Имеется три дома и три колодца.

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

решена Понтрягиным и независимо от него Куратовским в

Третья задача . О четырех красках. Любую карту на плоскости раскрасить четырьмя красками так, чтобы никакие две соседние области не были закрашены одним цветом.

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

1.2. Основные определения.

Графом G= (V,E ) называется совокупность двух множеств - непустого множества вершинV и множества неупорядоченных и упорядоченных пар вершинE . В дальнейшем будут рассматриватьсяконечные графы , т.е. графы с конечным множеством вершин и конечным семейством пар. Неупорядоченная пара вершин называетсяребром , а упорядоченная -дугой .

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

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

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

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

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

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

Граф, состоящий из одной изолированной вершины (K 1 ), называетсятривиальным .

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

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

1.3. Степени вершин графа.

Степенью (валентностью) (обозначениеd (v ) илиdeg (v )) вершиныv простого графаG называется число ребер или дуг инцидентных данной вершинеv . При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.

Если степени всех вершин н-графа равныk , то граф называетсярегулярным (однородным) степениk . Если степень вершины равна0 , то она являетсяизолированной . Если степень вершины равна1 , то вершина называетсяконцевой (висячей, тупиковой).

Для орграфа число дуг исходящих из вершины v назы-

Теорема Эйлера : Сумма степеней вершин графа равна

удвоенному количеству ребер, т.е.

d (vi )

Где n – число вершин;m – число

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

1.4. Изоморфизм графов.

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

метками (номерами). Граф считается полностью заданным в строгом смысле , если нумерация его вершин и ребер фиксирована. При этом графыG 1 иG 2 называютсяравными (обозначениеG 1 =G 2 ) ,, если их множества вершин и ребер совпадают. Два графа или псевдографаG 1 = (V 1 ,E 1 ) иG 2 = (V 2 ,E 2 ) называют-

оказываются изоморфными, если существуют взаимно одно-

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

2 (1) .

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

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

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

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

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

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

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

• Основные определения

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

• Способы представления

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

• Деревья

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

• Остовное дерево наименьшего веса

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

• Методы систематического обхода вершин графа

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

• Задача о путях во взвешенных ориентированных графах

• Изоморфизм графов

  Для ориентированного графа (V, Е) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин. В неориентированном графе (V, Е) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u, v} ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением р, т.е. (u, v) ∈ р и (v, u) ∈ р.

• Топологическая сортировка

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

• Элементы цикломатики

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

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

О курсе

Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В нашем курсе мы, конечно же, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.

Формат

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

Информационные ресурсы

1. В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
2. А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
3. М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
4. M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
5. B. Bollobás. Modern Graph Theory. Springer, 1998.
6. J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.

Требования

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

Программа курса

1. Понятие графа и виды графов.
2. Различные применения графов: от Кенигсберских мостов до Интернета.
3. Связность графа, подграфы и степень вершины.
4. Эквивалентные определения деревьев.
5. Планарность и критерий Куратовского
6. Формула Эйлера.
7. Хроматическое число планарного графа.
8. Перечисление деревьев: код Прюфера и формула Кэли.
9. Формула для числа унициклических графов.
10. Эйлеровы циклы и критерий эйлеровости.
11. Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
12. Паросочетания. Теорема Холла и Кенига.
13. Экстремальная теория графов. Теорема Турана.
14. Аналог теоремы Турана для графов на плоскости.
15. Теория Рамсея. Знакомства среди шести человек.
16. Определение числа Рамсея.
17. Нижняя и верхняя оценки чисел Рамсея.

Результаты обучения

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

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

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

Чтобы решать задачи с таким множеством, нужно каждый объект из этого множества обозначить как что-то. Общепринято это самое что-то называть вершинами графа.

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

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

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

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

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

Дуга и ребро отличаются тем, что ребро — это такая двунаправленная связь. Захотел, ушел к соседу, захотел, вернулся от соседа. Если не очень понятно, то можно представить дом, аэродром, летящий самолет и парашютиста. Парашютист может пойти из своего дома на аэродром, но когда пришел на аэродром, вспомнить, что свой счастливый парашют забыл дома, затем вернуться домой, взять парашют. — Такая дорога, по которой можно гулять туда и обратно, называется ребром.
Если парашютист находится в самолете и прыгает с самолета, но парашютист забыл в самолете надеть свой счастливый парашют, то сможет ли парашютист забрать что забыл? Такой путь, который идет только в одну сторону, называется дугой. Обычно говорят, что ребро соединяет две вершины, а дуга идет из одной вершины в другую.

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

Вы часто будете встречать понятия смежности и инцендентности. На рисунке красным цветом отмечены два ребра, которые идут в одну точку. Такие ребра, как и вышеописанные вершины, тоже называются смежными.

Многое не описано, но эта часть информации может быть кому-то поможет.