Для чего нужна теория графов. Теория графов

ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЗАДАЧ

Методическая разработка

Учитель Синявина Надежда Васильевна

Задачи, приводящие к графам

1. Женя, Дима, Максим и Але­ша сыграли между собой по одной партии в шахматы. Сколько всего партий было сыграно?

Решение:

Женя сыграл партию с Димой, партию с Максимом и партию с Алешей - всего три партии. Дима также сыграл три партии - с Женей, Максимом и Алешей. Но партию Димы с Женей мы уже посчитали. Остается добавить одну партию, которую сыграли Максим с Алешей. Поэтому искомое число партий равно значению выражения 3+2+1.

Проще решить эту задачу с помощью рисунка.

Каждая линия обозначает сыгранную партию. Всего на схеме 6 линий, значит всего сыграно 6 партий.

2. Вася, Коля, Петя, Аня и Наташа - луч­шие лыжники в пятом классе. Для уча­стия в соревнованиях нужно выбрать из них одного мальчика и одну девоч­ку. Сколькими способами это можно сделать?

Решение:

Эту задачу можно решить с помощью следующей схемы.

Ответ: 6 способов.

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

На прощание эти ученые обменялись визитными карточками. Сколько карточек было передано из рук в руки?

Решение:

Ответ: 10 рукопожатий, 20 визитных карточек.

4. Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Ма­нилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаим­ное расположение имений и проселочных дорог, соединяющих их (рис. 1.1). Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

Решение. По схеме видно, что путешествие Чичиков начал с имения Е, а кончил имением О. Замечаем, что в имения В и С ведут только по две дороги, поэтому по этим дорогам Чичиков дол­жен был проехать. Отметим их жирной линией. Опреде­лены участки маршрута, проходящие через А: АС и АВ. По дорогам АЕ, АК и AM Чичиков не ездил. Перечеркнем их (рис. 1.2К Отметим жирной линией ED ; перечеркнем DK . Перечеркнем МО И МН отметим жирной линией М F ; перечеркнем FO ; отметим жирной линией FH , НК и КО . Найдем единственно возможный при данном условии маршрут.

Подведем первый итог: задача решена в ходе преобразования картинки. С рисунка остается только считать ответ: имение Е принадлежит Манилову, D - Коробочке, С - Ноздреву, А - Собакевичу, В - Плюшкину, М - Тентетникову, F - Бетрищеву, Н - Петуху, К - Констанжогло, О - Кошкареву.

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

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

Точки иначе называют вершинами, отрезки - ребрами графа.

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

На следующем рисунке одна изолированная вершина.

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

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

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

Вершина называется нечетной, если ее степень - число нечетное. Вершина называется четной, если ее степень - число четное.

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

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

Длиной пути называется число ребер этого пути.

Длиной цикла называется число ребер в этом цикле.

Две вершины А и В графа называются связными , если в графе существует путь с концами А и В.

Две вершины графа называются несвязными , если в графе не существует ни одного пути, связывающего их.

В графе вершины А и В - связные, а вершины А и Н - несвязные.

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

Граф называется несвязным , если хотя бы две вершины его не­связные.

Деревом называется всякий связный граф, не имеющий циклов.

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

Лесом называется несвязный граф, представляющий объединение деревьев.

Решение задач с помощью графов

Задача 1. Утверждают, что в одной компании из пяти человек каждый знаком с двумя и только с двумя другими. Возможна ли такая компания?

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

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

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

Каждая вершина графа с девятью вершинами может иметь степень, равную 0, 1, 2,…,7, 8. Предположим, что существует граф Г, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действитель­но, если в графе есть вершина А степени 0, то в нем не найдется вер­шина В со степенью 8, так как эта вершина В должна быть соединена ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.

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

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

Решение.

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

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

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

Во втором случае получились два простых цикла, не сцеплен­ные между собой в вершинах.

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

На участие в розыгрыше кубка поданы заявки от 16 команд. Схема проведения игр изображается графом на рисунке.

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

Какую информацию можно получить с помощью этого дерева?

Непосредственно с него считываются:

число всех участников розыгрыша кубка (число закрашенных вершин);

число этапов проведения розыгрыша (число ярусов из вершин в дереве не считая нижнего);

число команд, участвовавших в одной восьмой финала, в одной четвертой финала, в одной второй финала (число вершин соответственно в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе);

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

Задача 5. Вершины графа обозначают населенные пункты, ребра – дороги. Сколькими способами можно выбрать путь из А в С? Сколькими способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге?

Решение:

5 · 3=15 способами можно выбрать путь из А в С.

5 · 3 · 2 ·4 =120 способами можно доехать из А в С, затем вернуться обратно, если нельзя проезжать дважды по одной и той же дороге.

Задача 6. На гору ведут 5 дорог. Сколькими способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё? Как изменится ответ, если нельзя подниматься и спускаться по одной и той же дороге?

Решение:

5 · 5=25 способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё.

5 · 4 =20 способами можно выбрать маршрут для того, чтобы подняться на гору, а затем спуститься с неё, если нельзя подниматься и спускаться по одной и той же дороге.

Заключение.

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

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

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

Литература.

Федеральное Государственное образовательное учреждение высшего профессионального образования

«Мордовский государственный педагогический институт имени М.Е. Евсевьева»

Физико-математический факультет

Реферат

по теме:

«Теория графов »

Выполнила: студентка

группы МДМ-109

Добрынкина О.А.

Проверила: Лапина И.Э.

Саранск 2014

Введение………………………………………………………………………. 3

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

2. Примеры графов……………………………………………………………. 8

3. Эйлеровы графы…………………………………………………………… 13

4. Примеры приложений теории графов……………………………………. 16

5. Задача о кратчайшем пути………………………………………………… 18

6. Алгоритм нахождения максимального потока………………………….. 27

Заключение…………………………………………………………………… 38

Список литературы…………………………………………………………… 39

Введение

В последнее время наблюдается неуклонное вторжение математических методов в различные отрасли науки и техники. Процесс математизации затронул и экономическую науку.

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

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

Изучение графов актуально и на сегодняшний день. Найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут – все это примеры из нашей повседневной жизни. Эти и многие другие задачи могут быть решены при помощи графов.

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

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

Граф – система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (рис. 1).

Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис. 1, А); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 1, Б).

Опр. 1. Задано конечное множество X , состоящее из n элементов (X = {1, 2,…, n }), называемых вершинами графа, и подмножество V декартова произведения X ×X, то есть
, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V).

Опр. 2. Неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X.

Дугу между вершинами i и j,
, будем обозначать (i, j). Число дуг графа будем обозначать m (V = (
)).

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

Опр. 4. Две вершины называются смежными, если они соединены ребром (дугой). Смежные вершины называются граничными вершинами соответствующего ребра (дуги), а это ребро (дуга) – инцидентным соответствующим вершинам.

Опр.5. Путем называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.

Опр. 5.1. Простой путь – путь, в котором ни одна дуга не встречается дважды.

Опр. 5.2. Элементарный путь – путь, в котором ни одна вершина не встречается дважды.

Опр. 5.3. Контур – путь, у которого конечная вершина совпадает с начальной вершиной.

Опр. 5.4 Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы).

Опр.6. Граф, для которого из (i, j) V следует (j, i) V называется симметрическим.

Опр. 7. Если из (i, j) V следует, что (j, i)
V, то соответствующий граф называется антисимметрическим.

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

Опр. 8.2. Цепь – последовательность смежных вершин.

Опр. 9. Замкнутая цепь называется циклом.

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

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

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

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

Опр. 13. В неориентированном графе степенью вершины i называется число инцидентных ей ребер. Очевидно,
. Граф, степени всех вершин которого равны n – 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Опр. 14. Вершина, для которой не существует инцидентных ей ребер (= 0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро ( = 1) называется висячей.

Опр. 15. Определим матрицу смежности графа как квадратную матрицу n ×n, элемент которой равен единице, если (i, j) V, и нулю, если (i, j)
V, i, jX. Для неориентированного графа матрица смежности всегда симметрическая.

Опр. 16. Определим матрицу инциденций для ребер графа как прямоугольную матрицу n×m, элемент которой равен единице, если вершина i инцидентна ребру j, и нулю в противном случае, i = 1, n, j = 1, m.

Опр. 17. Матрица инциденций для дуг графа – прямоугольная матрицу m x n, элемент rij которой равен плюс единице, если дуга исходит из вершины i, минус единице, если дуга заходит в вершину i, и нулю в остальных случаях, i = 1, n, j = 1, m

Опр. 18. Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m = n – 1, а число висячих вершин равно
Легко показать, что в дереве любые две вершины связаны единственной цепью.

Опр. 19. Прадеревом называется ориентированное дерево, у которого одна из вершин, называемая корнем, не имеет заходящих дуг, а степени захода остальных вершин равны единице.

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

Опр. 21. Степенью грани называется число ее граничных ребер (висячие ребра считаются дважды).

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

2. Примеры графов

Вполне несвязные графы . Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с п вершинами через N n ; N 4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

Полные графы . Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами обычно обозначается через . Графы и изображены на рис. 2 и 3. имеет ровно n (n – 1)/2 ребер.

Регулярные графы . Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r , то граф называется регулярным степени r . Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф К n – регулярным степени n – 1.

Платоновы графы . Среди регулярных графов особенно интересны так называемые Платоновы графы – графы образованные вершинами и ребрами пяти правильных многогранников – платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;

Двудольные графы . Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V 1 и V 2 так, что каждое ребро в G соединяет какую-нибудь вершину из V 1 с какой-либо вершиной из V 2 (рис. 7);

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

где m , n – число вершин соответственно в V 1 и V 2 . Например, на рис. 8 изображен граф K 4 , 3 . Заметим, что граф
имеет ровно m + n вершин и mn ребер. Полный двудольный граф вида
называется звездным графом; на рис. 9 изображен звездный граф
.

Связные графы . Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов – каждый из таких связных графов называется компонентой (связности) графа G . (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.

Циклические графы и колеса . Связный регулярный граф степени 2 называется циклическим графом (или циклом); циклический граф. с п вершинами обозначается через С n . Соединение графов и
(п ≥ 3) называется колесом с п вершинами и обозначается W n . На рис. 11 изображены С 6 и W 6 ; граф W 4 уже появлялся на рис. 2.

3. Эйлеровы графы

Связный граф G называется эйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро; такая цепь называется эйлеровой цепью. Отметим, что в этом определении требуется, чтобы каждое ребро проходилось только один раз. Если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым; при этом каждый эйлеров граф будет полуэйлеровым. На рис. 13,14,15 изображены соответственно не эйлеров, полуэилеров и эйлеров графы.

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

Докажем простую лемму.

Лемма 1. Если степень каждой вершины графа G не меньше двух, то G содержит цикл.

Доказательство. Если в графе G имеются петли или кратные ребра, то утверждение очевидно; поэтому предположим, что G является простым графом. Пусть v – произвольная вершина графа G ; построим по индукции маршрут , выбирая вершину v 1 смежной вершине v , а для i ≥1 – выбирая v i +1 смежной v i и отличной от v i -1 (существование такой вершины v i +1 гарантировано условием леммы). Так как G имеет конечное число вершин, то в конце концов мы придем к вершине, которая уже была выбрана раньше. Предположим, что v k – первая такая вершина; тогда часть маршрута, лежащая между двумя вхождениями v h , и является требуемым циклом.

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

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

Проведем доказательство индукцией по числу ребер в G . В силу связности G , степень каждой вершины не меньше двух, а отсюда, по предыдущей лемме, заключаем, что граф G содержит цикл С. Если С проходит через каждое ребро графа G , то доказательство завершено; если нет, то, удаляя из G ребра, принадлежащие циклу С, получим новый (быть может, и несвязный) граф Н. Число ребер в Н меньше, чем в G , и любая вершина в Н по-прежнему имеет четную степень. Согласно индуктивному предположению, в каждой компоненте графа Н существует эйлерова цепь. В силу связности графа G , каждая компонента в Н имеет по крайней мере одну общую вершину с циклом С, поэтому искомую эйлерову цепь графа G можно получить так: идем по ребрам цикла С до тех пор, пока не встретим неизолированную вершину графа Н, затем следуем по эйлеровой цепи той компоненты в Н, которая содержит указанную вершину; далее продолжаем путь по ребрам цикла С, пока не встретим вершину, принадлежащую другой компоненте графа Н, и т.д.; заканчивается процесс тогда, когда мы попадаем обратно в начальную вершину (рис. 17).

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

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

4. Примеры приложений теории графов

1. «Транспортные» задачи, в которых вершинами графа являются пункты, а ребрами – дороги (автомобильные, железные и др.) и / или другие транспортные (например, авиационные) маршруты. Другой пример – сети снабжения (энергоснабжения, газоснабжения, снабжения товарами и т.д.), в которых вершинами являются пункты производства и потребления, а ребрами – возможные маршруты перемещения (линии электропередач, газопроводы, дороги и т.д.). Соответствующий класс задач оптимизации потоков грузов, размещения пунктов производства и потребления и т.д., иногда называется задачами обеспечения или задачами о размещении. Их подклассом являются задачи о грузоперевозках.

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

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

4. Управление проектами. (Управление проектами – раздел теории управления, изучающий методы и механизмы управления изменениями (проектом называется целенаправленное изменение некоторой системы, осуществляемое в рамках ограничений на время и используемые ресурсы; характерной чертой любого проекта является его уникальность, то есть нерегулярность соответствующих изменений.)). С точки зрения теории графов проект – совокупность операций и зависимостей между ними. Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ). В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени проекта, затрат, и др.).

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

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

5. Задача о кратчайшем пути

Пример 1. Задача о волке, козе и капусте. Коза, капуста и волк находятся на берегу реки; перевозчику надо переправить их через реку, но его лодка так мала, что он может взять с собой не более одною из этих трех «пассажиров». По очевидным причинам нельзя оставлять без надзора волка с козой, а козу с капустой. Как должен поступить перевозчик?

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

В более общем случае необходим систематический алгоритм, изложим несколько методов.

Задача о кратчайшем пути

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

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

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

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

Обозначим – длину дуги (i; j). Кратчайший путь в сети, имеющей правильную нумерацию, определяется следующим алгоритмом.

Алгоритм 1.

;

Шаг k: помечаем вершину k индексом
i

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

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

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

Алгоритм 2 (алгоритм Форда).

Шаг 0: Помечаем нулевую вершину индексом
, все остальные вершины индексами
, i = 1, n;

Шаг k: Рассматриваем все дуги. Если для дуги (i; j)
>, то вычисляем новое значение
;

Индексы устанавливаются за конечное число шагов. Обозначим
- установившиеся значения индексов, которые обладают следующим свойством: величина равна длине кратчайшего пути из нулевой вершины в вершину i. Кратчайший путь из вершины 0 в вершину i определяется методом обратного хода.

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

Алгоритм 3.

Шаг 0: Помечаем нулевую вершину индексом
;

Шаг k: Пусть уже помечено некоторое множество вершин. Обозначим Q – множество непомеченных вершин, смежных с помеченными. Для каждой вершины
вычисляем величину
где минимум берется по всем помеченным вершинам i, смежным с вершиной k. Помечаем вершину k, для которой величина минимальна, индексом
.

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

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

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

Пример 1.

Рис. 3. Исходные данные к задаче о кратчайшем пути.

Ситуацию можно описать не только ориентированным графом, но и таблицей (табл. 1).

Табл.1. Исходные данные к задаче о кратчайшем пути

Начало дуги

Конец дуги

Время в пути

Спрашивается в задаче: как кратчайшим путем попасть из вершины 1 в вершину 4?

Решение. Введем обозначение: С (Т) – длина кратчайшего пути из вершины 1 в вершину Т. (Поскольку любой путь, который надо рассмотреть, состоит из дуг, а дуг конечное число, и каждая входит не более одного раза, то претендентов на кратчайший путь конечное число, и минимум из конечного числа элементов всегда достигается.) Рассматриваемая задача состоит в вычислении С (4) и указании пути, на котором этот минимум достигается.

Для исходных данных, представленных на рис. 3 и в табл. 1, в вершину 3 входит только одна стрелка, как раз из вершины 1, и около этой стрелки стоит ее длина, равная 1, поэтому С(3)=1. Кроме того, очевидно, что С(1)=0.

В вершину 4 можно попасть либо из вершины 2, пройдя путь, равный 4, либо из вершины 5, пройдя путь, равный 5. Поэтому справедливо соотношение С(4) = min {С(2) + 4; С(5) + 5}.

Таким образом, проведена реструктуризация задачи – нахождение С(4) сведено к нахождению С(2) и С(5).

В вершину 5 можно попасть либо из вершины 3, пройдя путь, равный 2, либо из вершины 6, пройдя путь, равный 3. Поэтому справедливо соотношение С(5) = min {С(3) + 2; С(6) + 3}.

Мы знаем, что С(3) = 1. Поэтому С(5) = min {3; С(6) + 3}.

Поскольку очевидно, что С(6) – положительное число, то из последнего соотношения вытекает, что С(5) = 3.

В вершину 2 можно попасть либо из вершины 1, пройдя путь, равный 7, либо из вершины 3, пройдя путь, равный 5, либо из вершины 5, пройдя путь, равный 2. Поэтому справедливо соотношение С(2) = min {С(1) + 7; С(3) + 5; С(5) + 2}.

Нам известно, что С(1) = 0, С(3) = 1, С(5) = 3. Поэтому С(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.

Теперь мы можем найти С(4): С(4) = min {С(2) + 4; С(5) + 5} = min {5 + 4; 3 + 5} = 8.

Таким образом, длина кратчайшего пути равна 8. Из последнего соотношения ясно, что в вершину 4 надо идти через вершину 5. Возвращаясь к вычислению С(5), видим, что в вершину 5 надо идти через вершину 3. А в вершину 3 можно попасть только из вершины 1. Итак, кратчайший путь таков: 1 → 3 → 5 → 4.

Задача о кратчайшем пути для конкретных исходных данных (рис. 3и табл. 1) полностью решена.

Пример 2.

Найти кратчайший путь (длина пути) из Академгородка (остановка Цветной проезд) до железнодорожного вокзала.

Остановки:

цветной проезд

дом быта

3,3"- институт ядерной физики

4 Баня №22

5 Речной вокзал

6 – Сеятель

7 – кафе «Огонек»

8 – Мост

9 – Главный Вокзал

Найти кратчайший путь из вершины 1 в вершины 9.

Исходные данные:

Рис. 4

Табл. 2

Начало дуги

Конец дуги

Длина пути (км.)

3,06

10,9

26,78

21,57

4,26

4,35

2,55

Решение: С (Т) – длина кратчайшего пути из вершины 1 в вершину Т. Нам необходимо найти С(9).

С(1)=0, С(2)=3 (в вершину 2 входит только одна стрелка, ее длина равна 3).

В вершину 9 можно попасть из вершины 5, пройдя путь 4,35, из вершины 6, пройдя путь 25 и из вершины 8, пройдя путь 2,55.

Следовательно, С(9) = min {С(5) + 4,35; С(6) + 25; С(8) + 2,55}

Таким образом необходимо найти С(5), С(6), С(8).

В вершину 5 можно попасть из вершины 1, пройдя путь 26,78, либо из вершины 7, пройдя путь 19

С(5) = min {С(1) + 26,78; С(7) + 19}

Необходимо найти С(7). В вершину 7 можно попасть из вершины 3, пройдя путь 7,6 и из 3" пройдя 7,6.

С(7) = min {С(3) + 7,6; С(3") + 7,6}= min {1,7+7,6; 3,06+7,6}=9,3

С(5) = min {26,78; 9,3+ 19}=26,78

В вершину 6 можно попасть из вершины 2, пройдя путь равный 0,5

С(6)=С(2)+0,5=3+0,5=3,5

В вершину 8 можно попасть из вершины 4, пройдя путь 21,57 и из вершины 5, пройдя путь 4,62.

С(8) = min {С(4) + 21,57; С(5) + 4,26}

С(4)=10,9 (из условия).

С(8) = min {10,09+ 21,57; 26,78 + 4,26}=31,4

Следовательно

С(9)= min {26,78+4,35; 3,5+25; 31,4+2,55}= min {31,13; 28,5; 33,95}=28,5

Таким образом, длина кратчайшего пути равна 28,5 км.

Кратчайший путь: 1 → 2 → 6 → 9.

6. Алгоритм нахождения максимального потока

Идея этого алгоритма состоит в поиске сквозных путей с положительными потоками от источника к стоку.

Рассмотрим ребро (i , j ) с (начальной) пропускной способностью
. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись
- остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла j , получающего поток из узла i , определим метку
, где - величина потока, протекающего от j узла к узлу i . Чтобы найти максимальный поток, выполняем следующие действия.

Этап 1.

Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем
=
. Назначим
и пометим узел 1 меткой. Полагаем i =1.

Этап 2.

- множество узлов j , в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью >0 для всех j . Если
, выполняем 3 этап, в противном случае переходим к 4.

Этап 3.

В находим узел k , такой, что
. Положим
и пометим узел k меткой
. Если k =n , сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i =k и возвращаемся к 2 этапу.

Этап 4.

Откат назад. Если i =1, сквозной путь не возможен, и переходим к 6. Если
, находим помеченный узел r , непосредственно предшествующий узлу i , и удаляем его из множества узлов, смежных с узлом r . Полагаем i =r и возвращаемся ко 2 этапу.

Этап 5.

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

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

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

1)
, если поток идет от узла i к j ,

2)
, если поток идет от узла j к i .

Этап 6.

Решение.

а) при m найденных сквозных путях максимальный поток выражается

б) Имея значения начальных
и конечных
пропускных способностей ребра (i , j ), можно вычислить оптимальный поток через это ребро следующим образом. Положим . Если >0, поток, проходящий через ребро (i , j ) равен . Если >0, тогда поток равен . (случай, когда одновременно >0 и >0, невозможен).

Пример 1. Найти максимальный поток в сети рис. 1

Итерация 1.
=

1)
и помечаем узел 1 меткой
. i =1

2)

3) k =3, так как . Назначаем
и помечаем узел 3 меткой
. i =3 и возвращаемся к 2)

4)

5) k =5 и . Помечаем узел 5 меткой
. Получаем сквозной путь.

6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: .
:

Итерация 2.

1)
и помечаем узел 1 меткой
. i =1

2)

3) k =2, и помечаем узел 2 меткой
. i =2 и возвращаемся к 2)

2")

3") k =3 и
. Помечаем узел 3 меткой
. i =3 и возвращаемся к 2)

2»)
(
, поэтому узел 5 не включается в

3») k =4,
и помечаем узел 4 меткой
. i =4 и возвращаемся к 2)

2""")
(так как узлы 1 и 3 помечены, они не включаются в )

3""") k =5 и
. Помечаем узел 5 меткой
. Получен сквозной путь. Переходим к 5)

5)
и . Вычисляем остаточные пропускные способности вдоль пути :

Итерация 3.

1)
и помечаем узел 1 меткой
. i =1

2)

3) k =2,
и помечаем узел 2 меткой
. i =2 и возвращаемся к 2)

2")

Рис. 2. Исходные данные к примеру 2

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).

Табл.2. Исходные данные к задаче о максимальном потоке

Пункт отправления

Пункт назначения

Пропускная способность

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу – в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы – 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 – по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)

Табл.3. Решение задачи о максимальном потоке

Пункт отправления

Пункт назначения

План перевозок

Пропускная способность

Задача линейного программирования при максимизации потока. Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть Х KM - объем перевозок из пункта К в пункт М. Согласно рис. 2 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных Х KM, а именно, Х 01, Х 02, Х 03, Х 12, Х 13, Х 14, Х 23, Х 24, Х 34. Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:

F → max,

Х 01 + Х 02 + Х 03 = F (0)

– Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)

– Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)

– Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)

– Х 14 - Х 24 - Х 34 = – F (4)

Х 01 ≤ 2

Х 02 ≤ 3

Х 03 ≤ 1

Х 12 ≤ 4

Х 13 ≤ 1

Х 14 ≤ 3

Х 23 ≤ 1

Х 24 ≤ 2

Х 34 ≤ 2

Х КМ ≥ 0, К, М = 0, 1, 2, 3, 4

F ≥ 0.

Здесь F – целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) – (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) – это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию – через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).

Заключение

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

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

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

Список литературы

"Соросовский образовательный журнал" №11 1996 (ст. "Плоские графы");

«В помощь учителю математики», Йошкар-Ола, 1972 ст. "Изучение элементов теории графов"

Берж, К.С.Теория графов и ее применение./К. С. Берж.- М.: ИЛ, 2007.-178с.

Бурков, В.Н. Элементы теории графов./В. Н. Бурков. – М.: Просвещение,2010.-352с.

Гарднер, М. С"Математические досуги". / М. С. Гарднер.- М. :"Мир",2004.-347с.

Гарднер, М. С."Математические головоломки и развлечения"./ М С гарднер.-М. :"Мир",2005.-221с.

Зыков, А. А. Теория конечных графов./ А. А. Зыков.- Новосибирск: "Наука",2006.-257с.

Касаткин, В. Н. "Необычные задачи математики"./ В. Н. Касаткин.-Киев: "Радяньска школа", 2007.-232с.

Олехник, С. Н. "Старинные занимательные задачи"./ C .Н. Олехник.- М. "Наука",2008.-431с.

Оре, О. С."Графы и их применения"./О. С. Оре.- М.:"Мир", 2005-269с.

Реньи, А. Н."Трилогия о математике"./ А. Н. Реньи.- М.:"Мир",2010-198с.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v1, v2, если оно соединяет эти вершины и наоборот, каждая из вершин v1, v2 инцидентна ребру е.

Рассмотрим графическое представление графов таблица 1.

Таблица 1. Графическое представление графов

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

Рассмотрим некоторые важные типы графов.

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

Заметим, что у вполне несвязного графа все вершины изолированы

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

Заметим, что для полного графа выполняется равенство

где m - число ребер, n - число вершин графа.

Определение. Граф, у которого все вершины имеют одну и ту же локальную степень n, называется регулярным (или однородным) степени n.

Регулярные графы степени 3 называются кубическими (или трехвалентными).

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

Среди регулярных графов особенно интересны так называемые платоновы графы - графы, образованные вершинами и ребрами пяти правильных многогранников - Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.На рисунке 6 приведен граф, соответствующий кубу.

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

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

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

Заметим, что граф Кm. n имеет ровно m + n вершин и mn ребер.

Определение. Объединением графов

называется граф

Определение. Пересечением графов

называется граф

Определение. Соединением графов G1 и G2 является новый граф, у которого

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

Определение. Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

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

Определение. Связный регулярный граф степени 2 называется циклическим графом. Обозначается Сn .

Определение. Соединение графов N1 и Cn-1 (n3) называется колесом с n вершинами. Обозначается Wn (рисунок 10)

Определение. Дополнением простого графа G называется простой граф с множеством вершин V(G), в котором две вершины смежны тогда и только тогда, когда они не смежны в исходном графе.

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

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

Вполне несвязные графы . Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Будем обозначать вполне несвязный граф с п вершинами через N n ; N 4 показан на рис. 1. Заметим, что у вполне несвязного графа все вершины изолированы. Вполне несвязные графы не представляют особого интереса.

Полные графы . Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с n вершинами обычно обозначается через. Графы и изображены на рис. 2 и 3. имеет ровно n (n - 1)/2 ребер.

Регулярные графы . Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна r, то граф называется регулярным степени r. Регулярные графы степени 3, называемые также кубическими (или трехвалентными) графами (см., например, рис. 2 и 4). Другим известным примером кубического графа является так называемый граф Петерсена, показанный на рис. 5. Отметим, что каждый вполне несвязный граф является регулярным степени 0, а каждый полный граф К n - регулярным степени n - 1.

Платоновы графы . Среди регулярных графов особенно интересны так называемые Платоновы графы - графы образованные вершинами и ребрами пяти правильных многогранников - платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра. Граф соответствует тетраэдру (рис. 2); графы, соответствующие кубу и октаэдру, показаны на рис. 5 и 6;

Двудольные графы . Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V 1 и V 2 так, что каждое ребро в G соединяет какую-нибудь вершину из V 1 с какой-либо вершиной из V 2 (рис. 7);

тогда G называется двудольным графом. Такие графы иногда обозначают G(V 1, V 2), если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому - в терминах раскраски его вершин двумя цветами, скажем красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой - синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V 1 соединена с каждой вершиной из V 2 ; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается где m, n - число вершин соответственно в V 1 и V 2 . Например, на рис. 8 изображен граф K 4 , 3 . Заметим, что граф имеет ровно m + n вершин и mn ребер. Полный двудольный граф вида называется звездным графом; на рис. 9 изображен звездный граф.

Связные графы . Граф связный, если его нельзя представить в виде объединения двух графов, и несвязный в противном случае. Очевидно, что всякий несвязный граф G можно представить в виде объединения конечного числа связных графов - каждый из таких связных графов называется компонентой (связности) графа G. (На рис. 10 изображен граф с тремя компонентами.) Доказательство некоторых утверждений для произвольных графов часто бывает удобно сначала провести для связных графов, а затем применить их к каждой компоненте в отдельности.