Программа интенсивного факультативного курса «Введение в теорию графов»

Локтева Наталья Владимировна,

педагог дополнительного образования

муниципального учреждения дополнительного образования

«Малая академия» (г. Краснодар)

Программа

интенсивного факультативного курса «Введение в теорию графов»

Пояснительная записка

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

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

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

Предлагаемый курс является предметно-ориентированным.

Цель курса:

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

Задачами курса являются

- расширение и углубление знаний учащихся в области математики,

- повышение общей математической культуры школьников,

- обучение решению задач методами и приемами теории графов,

- развитие у школьников абстрактного мышления, пространственного воображения,

- формирование аналитических способностей,

- формирование исследовательских навыков и умений.

Формы проведения занятий: занятия смешанного типа – лекция, беседа, практикум.

Формы организации познавательной деятельности учащихся: индивидуальные, групповые.

Методы, используемые в работе: проблемно-поисковые, эвристические, метод проектов.

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

Курс разработан для учащихся 5-8 классов. Для усвоения курса достаточно базовых математических знаний за 5 класс.

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

Курс рассчитан на 10 занятий по 40 минут.

Содержание курса

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

Занятие 1

Графы. Основные определения. Подсчет числа ребер

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

Занятие 2

Эйлеровы графы. Деревья

Определение эйлерова графа. Необходимые и достаточные условия существования эйлерова цикла. Цепь, цикл, определение дерева. Существование в дереве висячей вершины. Число ребер в дереве. Корневое дерево. Остовное дерево и минимальное остовное дерево.

Занятие 3

Плоские графы и теорема Эйлера

Планарный граф. Грань плоского графа. Внешние и внутренние грани. Теорема Эйлера. Формула Эйлера. Неравенство для связного планарного графа.

Занятие 4

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

Определение ориентированного графа. Маршрут и цепь в ориентированном графе. Сильный ориентированный граф. Связный ориентированный граф. Эйлеров ориентированный граф.

Для исследовательской деятельности учащимся по данному курсу можно предложить следующие темы:

Уникурсальные графы.

Эйлеровы циклы и пути в графах.

Дерево возможных вариантов.

Графы и игры на шахматной доске.

Графы в решении логических задач.

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

Графы в психологии.

Графы с цветными ребрами.

Тематическое планирование

Литература.

Бахтина Т.П. Раз задачка, два задачка…: Пособие для учителей. – Минск: Асар, 2000.

Березина Л.Ю. Графы и их применение. – М., 1979.

Генкин С.А., Итенберг И.В., Фомин Д.В. Ленинградские математические кружки. – Киров, 1994.

Гончаров Л. В. Предметные недели в школе. Математика – Волгоград: Учитель, 2003.

Мельников О.И. Занимательные задачи по теории графов: Учеб.-метод. пособие. – Минск: ТетраСистемс, 2001.

Мельников О. И. Незнайка в стране графов. – М.: КомКнига, 2006.

Никольская И. Л Факультативный курс по математике 7–9. – М.: Просвещение, 1991.

Смыкалова Е.В. Дополнительные главы по математике для учащихся 6 класса. – СПб: СМИО Пресс, 2001.

Спивак А. В. Математический кружок 6-7 классы. – М.: Посев, 2003

Спивак А. В. Тысяча и одна задача по математике: Кн. для учащихся 5-7 кл. – М.: Просвещение, 2002.

Фарков А. В. Математические олимпиады в школе. 5-11 класс. – М.: Айрис-пресс, 2005.

Фирсов Е. Г. Интеллектуальные игры для школьников. – Ярославль: Академия развития, 1998.

Приложение 1

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

Граф и его виды

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

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик Денеш Кениг.

Леонард Эйлер (1707-1783). Математик, механик, физик и астроном. Ученый необычайной широты интересов. Автор свыше 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др., оказавших значительное влияние на развитие науки. Л.Эйлер по происхождению швейцарец. В 1726 был приглашен работать в Петербург, в 1727 переехал жить в Россию. В 1731-1741 и начиная с 1766 был академиком Петербургской академии наук (в 1741-1766 работал в Берлине, оставаясь почетным членом Петербургской Академии наук).

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

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

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

Задача 1: Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение:

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

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

Например, все три фигуры на рисунке изображают один и тот же граф.

Рассмотрим процесс соединения точек А, Б, В, Г, Д ребрами.

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

2. Ситуация, когда совершены еще не все рукопожатия, может схематически быть изображена, например, с помощью рисунка З: пожали руки А и Б, А и Г, Д и Г, В и Д. Следующий момент, когда добавятся, например, пожатия рук А и В, Г и Б, попробуйте изобразить сами.

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

3. На рисунке 4 изображен граф, соответствующий всем совершенным рукопожатиям. Этот граф является полным графом.

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2

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

Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

Задача 2.

Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение:

Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 3.

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

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

Решение:

Занумеруем последовательно клетки доски:

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

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

Задачи к теме «Понятие графа»

Задача 4.

На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Решение.

Занумеруем клетки доски, как показано на рисунке:

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

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

Задача 5.

В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение.

Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степень вершины

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

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

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

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

Доказательство:

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

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Доказательство

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

Теорема (о честности числа нечетных вершин).

Число нечетных вершин любого графа четно.

Докажем теорему немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 6. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с 5 другими?

Решение:

Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным 15  5/2 = 37,5. Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Доказательство:

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

Задача 7. Кенигсбергские мосты

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

Решение:

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

Путь в графе. Цикл

Чем отличается маршрут AEH от маршрута AEFCEH?

Тем, что во втором маршруте на «перекрестке» в точке E мы побывали дважды. Этот маршрут длиннее, чем AEH. Маршрут AEH можно получить из маршрута AEFCEH «вычеркнув» из последнего маршрут FCE.

Маршрут AEH является путем в графе, а маршрут AEFCEH путем не является.

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

Маршруты CFEC, ADGHECBA, ADFCEA – циклы: CFEC и др. – элементарные циклы.

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

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

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

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

На рисунке приведены примеры Эйлеровых линий.

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

Связные графы

Определение 1:

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

Определение 2:

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

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

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

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом.

Задача 8.

В стране Семерка 15 городов, каждый из городов соединен дорогами не менее чем с 7 другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство:

Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

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

Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Рассмотрим пример задачи, в которой используется компонента связности:

Задача 9.

В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство:

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

Задача 10.

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

Решение:

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

Деревья

Определение.

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

Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины.

Свойство 1.

Для каждой пары вершин дерева существует единственный путь, их соединяющий.

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

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

По этому дереву однозначно находится предок Сергея в любом поколении по любой линии.

Свойство 2.

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

Теорема.

Дерево с n вершинами имеет n – 1 ребро.

Доказательство:

Для дерева – изолированной вершины n = 1 и ребер 0, что соответствует теореме

(n–1 = 1–1 = 0). Если из графа «дерева», не являющегося изолированной вершиной, удалить одно ребро, то получается два дерева с теми же вершинами. Для получения трех деревьев нужно удалить два ребра; для получения четырех деревьев – три ребра и т. д. Наибольшее количество деревьев из графа с n вершинами можно получить n (n изолированных вершин), чего можно достичь, удалив n–1 ребро. ч.т.д.

Изоморфные графы

Понятие плоского графа.

Формула Эйлера.

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

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

Граф для задачи 1 тоже можно нарисовать по-другому:

Такие графы называют изоморфными (одинаковыми).

Для того чтобы выяснить, изоморфны ли 2 графа, нужно убедиться в том, что у них:

1) одинаковое количество вершин

2) если вершины одного графа соединены ребром, то и соответствующие им вершины другого графа тоже соединены ребром.

На втором изображении ребра графа пересекаются, графы на первом и третьем изображениях не имеют пересекающихся ребер.

Простые циклы и деревья являются наглядными примерами плоских графов.

Задача 11.

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

Решение

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

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).

Таким образом, ответ на вопрос задачи будет таким: «Нельзя!»

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

Определение 2.

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

Дерево имеет одну грань – внешнюю (бесконечную грань).

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

В – Р = 1

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

И, зная, что у дерева одна грань (Г=1):

Р – Г = Р – 1

Очевидно, что рассматриваемое преобразование не изменяет исходного числа вершин B.

Пользуясь формулами и равенством: P = В – 1 получим:

Р – Г=В – 2.

(доказательство предоставляем вам)

Последняя формула или такой ее вид:

В-Р+Г=2

называется формулой Эйлера.

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

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

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

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

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

Определение 1.

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

Определение 2.

Граф, у которого все ребра ориентированные, называется ориентированным графом.

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

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

Определение 3.

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

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

Определение 4.

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер

A1A2, A2A3, ..., Аn-1Аn

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

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

Определение 5.

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

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

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними.

Расстояние между вершинами А и Д на графе рисунка равно 2; записывают так: S(АД) = 2.

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

ДОПОЛНЕНИЯ

Графы Эйлера

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

Задача.

Выясните, какие графы, изображенные на рисунке, являются уникурсальными?

Ответ: а), б), г), д), ж), з).

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

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

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

Задачи:

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

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?

Задачи на тему «Степени вершин и подсчет числа ребер»

3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.