ДООМ "Тайна графов". Методические материалы

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

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

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

Рис. 1. Примеры графов

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

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

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

Рис. 2. Нулевой граф с пятью вершинами Рис. 3. Неполный граф с пятью вершинами

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

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

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

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2 Действительно, количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2. Граф, не являющийся полным, можно дополнить, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа . Cтепень вершины - количество ребер графа, исходящих из этой вершины. На рисунке изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А. На рисунке : Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0. Вершина называется нечетной - если степень этой вершины нечетная, четной - если степень этой вершины четная. Сформулируем некоторые закономерности, присущие определенным графам.  Закономерность 1 Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа. Доказательство. Каждая вершина соединена ребром с каждой вершиной, кроме самой себя, т. е. из каждой вершины графа, имеющего n вершин, исходит n—1 ребро. ч.т.д.

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

Задача. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог? Решение. Если в государстве k городов(вершин), то сумма степеней всех вершин равна 3k, и равна удвоенному произведению числа ребер – 2r. Отсюда число ребер (дорог) - 3k/2. Это число не может быть равно 100.

 Закономерность 3 Число нечетных вершин любого графа четно. Доказательство. Рассмотрим произвольный граф Г. Пусть в этом графе число вершин, степень которых 1, равна К1; число вершин, степень которых 2, равно K2; ...; число вершин, степень которых n, равно Кn. Тогда сумму степеней вершин этого графа можно записать как K1 + 2К2 + ЗК3 + ...+ nКn. С другой стороны: если число ребер графа R, то из закономерности 2 известно, что сумма степеней всех вершин графа равна 2R. Тогда можно записать равенство K1 + 2К2 + ЗК3 + ... + nКn = 2R. (1) Выделим в левой части равенства сумму, равную числу нечетных вершин графа (К1 + К3 + К5 +...) + (2K2 + 2К3 +4K4 + 4К5 + ...)=2R Вторая скобка- четное число как сумма четных чисел. Полученная сумма (2R) - четное число. Отсюда (К1 + К3 + К5 +...)-четное число. ч.т.д.

Задача. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей? Решение. Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 - степень 4, 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.

2. Кенигсбергские мосты

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

Решить эту задачу удалось в 1736 г. Леонарду Эйлеру. В ходе решения задачи (после интерпретации условия задачи в виде графа, где вершины - острова и берега, а ребра - мосты, представленного на рисунке), Л. Эйлер установил, помимо уже рассмотренных нами, следующие закономерности:  Закономерность 4 (вытекает из рассмотренной нами закономерности 3). Невозможно начертить граф с нечетным числом нечетных вершин.  Закономерность 5. Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.  Закономерность 6. Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.  Закономерность 7. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком». Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной. Решение. Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа, представленного на рисунке. Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то, согласно закономерности 7. такой граф начертить «одним росчерком» невозможно. Значит, и пройти по кенигсбергским мостам, соблюдая заданные условия, нельзя.

Задача. Муха забралась в банку из- под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается. Решение. ребра и вершины образуют граф, все 8 вершин которого имеют степень 3 (см. закономерности). Следовательно, требуемый условием обход невозможен.

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

На рисунке с помощью графа изображена схема дорог между населенными пунктами. Например, из пункта A (вершина графа) в пункт H можно добраться различными маршрутами: ADGH, AEH, AEFCEH, ABCEH .

Чем отличается маршрут AEH от маршрута AEFCEH? Тем, что во втором маршруте на «перекрестке» в точке E мы побывали дважды. Этот маршрут длиннее, чем AEH. Маршрут AEH можно получить из маршрута AEFCEH «вычеркнув» из последнего маршрут FCE. Маршрут AEH является путем в графе, а маршрут AEFCEH путем не является. Существуют различные маршруты, по которым можно добраться, например, из вершины A в вершину H. Маршруты CFEC, ADGHECBA, ADFCEA — циклы: CFEC и др. — элементарные циклы. Путем в графе от одной вершины к другой называется такая последовательность ребер, по которой можно проложить маршрут между этими вершинами, при этом никакое ребро маршрута не должно встречаться более одного раза. Вершина, от которой проложен маршрут, называется началом пути, вершина в конце маршрута — конец пути. Циклом называется путь, в котором совпадают начало с концом. Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом. Если же цикл включает в себя все ребра графа по одному разу, то такой цикл называется Эйлеровой линией. На рисунке приведены примеры Эйлеровых линий.

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

4. Связные графы. Деревья Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути не существует, вершины называются не связными. Так, на рисунке любая пара вершин, взятая из набора А,Б,В,Г,Д ,будет связной, т.к. от любой из них к любой можно "пройти" по ребрам графа. Пары вершин, одна из которых взята из набора А,Б,В,Г,Д, а другая из набора Е,Ж,З, не будут связными, т.к. от одной к другой "пройти" по ребрам не удается. Граф называется связным, если любая пара его вершин — связная. Граф называется несвязным, если в нем есть хотя бы одна несвязная пара вершин. На рисунке, очевидно, изображен несвязный граф. Если, например, на рисунке между вершинами Д и Е провести ребро, то граф станет связным. Такое ребро в теории графов, после удаления которого, граф из связного превращается в несвязный, называется мостом. Примерами мостов на рисунке могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа.

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

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

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

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

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

Это легко видеть на рисунке, если удалить, например, ребро А5А6 или ребро А1А3, или ребро А4А10 (оставив «вторым деревом» вершину A10). Теорема. Дерево с n вершинами имеет n-1 ребро. Доказательство. Для дерева — изолированной вершины n=1 и ребер 0, что соответствует теореме (n—1 = 1—1 = 0). Если из графа «дерева», не являющегося изолированной вершиной, удалить одно ребро, то получается два дерева с теми же вершинами. Для получения трех деревьев нужно удалить два ребра; для получения четырех деревьев — три ребра и т. д. Наибольшее количество деревьев из графа с n вершинами можно получить n (n изолированных вершин), чего можно достичь, удалив n—1 ребро. ч.т.д. Задача. В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог? Решение. Из условия задачи следует, что граф дорог Древляндии - дерево. У этого дерева есть висячая вершина. Удалим ее вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию 100 раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет ребер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было 100. 5. Изоморфные графы. Понятие плоского графа. Формула Эйлера. Для подсчета числа рукопожатий, совершенных четырьмя товарищами А, Б, В и Г при встрече (задача п.1), можно воспользоваться полным графом с четырьмя вершинами. На рисунке представлено несколько вариантов изображения полного графа с четырьмя вершинами.

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

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

Задача. В трех различных домах живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались? Решение. После проведения восьми тропинок можно убедиться, что провести девятую, не пересекающуюся ни с какой из ранее проведенных тропинок, не удается. Построим граф, вершины которого А, Б, В, 1, 2, 3 соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя. Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3, которое не пересекло бы уже имеющихся в графе ребер).Таким образом, ответ на вопрос задачи будет таким: «Нельзя!» Помимо вершин и ребер плоского графа часто пользуются еще одной его характеристикой — гранями. Гранью плоского графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри циклов. На рисунке изображен плоский граф с четырьмя гранями: АВЕА, ЕБВГДЕ, ЕДГЕ и внешняя по отношению к циклу АБВГЕА область, ее называют также «бесконечной» гранью (на рисунке она отмечена штриховкой). Дерево имеет одну грань - внешнюю (бесконечную грань). Эйлер установил зависимость между количеством вершин, ребер и граней произвольного графа следующим соотношением: В-Р+Г=2, где В- количество вершин, Р – ребер, Г- граней. Эту формулу называют также формулой Эйлера для многогранников, так как это соотношение справедливо для вершин, ребер и граней всех пространственных многогранников. Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно. Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее? Тогда могут помочь сориентироваться в этой ситуации стрелки, расположенные, например, прямо на ребрах-улицах рассматриваемой схемы (графа) города. Ребро графа называется ориентированным ребром, если одну из его вершин считать началом, а другую — концом этого ребра. Граф, у которого все ребра ориентированные, называется ориентированным графом.

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

Так, на рисунке изображена (с помощью графа) схема игр между командами А, Б, В, Г, Д, Е. Но эта схема не дает информации о результатах игры. Обычно используют ориентацию ребра от выигравшей команды к проигравшей, т. е. если А выиграла у Д, то граф ориентируют от А к Д . На втором рисунке (с помощью ориентированного графа) показаны результаты игр между командами, изображенными с помощью графа на предыдущем рисунке. Если игра может быть сыграна вничью, то обычно ребро графа оставляют неориентированным (ребро ВЕ) и такой граф называют смешанным. По аналогии с ранее рассмотренными (неориентированными) графами ориентированные графы имеют такие характеристики, как степень вершины, понятия пути и цикла. Перечислим их. Степенью выхода вершины ориентированного графа называется число ребер, для которых эта вершина является началом (число ребер, «выходящих» из вершины). Степенью входа вершины ориентированного графа называется число ребер, для которых эта вершина является концом (число ребер, «входящих» в вершину). Так, на рисунке изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие: Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3 Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, ..., Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз. На ниже приведенном рисунке показаны примеры путей в ориентированном графе. Причем, первые два пути— простые — ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым, т. к. через вершину Г путь «проходил» дважды.

Ориентированным циклом называется замкнутый путь в ориентированном графе. На предыдущем рисунке приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути. Так, на рисунке пути от А к Д могут быть различны и иметь различную длину. Первый путь имеет длину 2, второй - 3, а третий — 4. Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка равно 2. Записывают так: S(АД)=2. Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным (обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке бесконечно:

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