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

1 Графы и их применение

2 Введение Если вы любите решать задачи на смекалку, логические, олимпиадного типа или головоломки, то, наверное, не раз составляли таблицы, изображали объекты точками, соединяли их отрезками или стрелками, подмечали закономерности у полученных рисунков, выполняли над точками и отрезками операции, не похожие на арифметические, алгебраические или на преобразования в геометрии, то есть вам приходилось строить математический аппарат специально для решения задачи. А это означает, что вы заново открывали для себя начала теории графов. Исторически сложилось так, что теория графов зародилась именно в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований учёных, была в царстве математики на положении Золушки, чьи дарования раскрылись в полной мере лишь тогда, когда она оказалась в центре всеобщего внимания. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми её связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кёнига в 30-е годы XX столетия. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, математической лингвистике, экономике, биологии, медицине. Широкое применение находят графы в таких областях прикладной математики, как программирование, теория конечных автоматов, электроника, в решении вероятностных и комбинаторных задач. Теория графов быстро развивается, находит всё новые приложения и ждёт молодых исследователей.

3 Часть I Начальные сведения по теории графов

4 1. Задача, приводящая к графам Задача. В первенстве класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и ещё с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем и Борисом; Дмитрий – с Виктором и Елена – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько ещё осталось? А Д Г ВБ Е Рис. 1 Решение. Изобразим данные задачи в виде схемы (рис.1). Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающих их точки отрезками. Получается схема, показанная на рисунке 1. Такие схемы называются графами. Точки А, Б, В, Г, Д, Е называются вершинами графа. Заметьте, что точки пересечения рёбер графа не всегда являются его вершинами. Во избежание путаницы вершины графа часто изображают не точками, а маленькими кружочками. Рёбра зачастую оказывается удобнее изображать не прямолинейными отрезками, а криволинейными – «дугами».

5 1. Задача, приводящая к графам Но вернёмся к нашей задаче. Число игр, проведённых к настоящему моменту, равно числу рёбер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим ещё один граф с теми же вершинами, но рёбрами будем соединять тех участников, которые ещё не играли друг с другом (рис.2). Рёбер у этого графа оказалось 8, значит, осталось провести 8 игр: Андрей должен сыграть в теннис с Виктором и Дмитрием: Борис – с Виктором, Дмитрием и Еленой и т.д. Графами мы пользуемся довольно часто. Возьмём схему железных дорог: здесь станции – это вершины графа, перегоны (участки пути между станциями) – рёбра графа. Вершины и рёбра многогранника (куба, пирамиды и т.д.) тоже образуют граф. А Д Г ВБ Е Рис. 2

6 2. Полный граф. Дополнение графа Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром (рис. 3). В полном графе каждая его вершина принадлежит одному и тому же числу рёбер. Для задания полного графа достаточно знать число его вершин. Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие рёбра. Например, граф Г на рисунке 4 неполный. Проведя недостающие рёбра (для удобства их можно выделить др. цветом или др. типом линии), получаем полный граф с пятью вершинами (рис.5 а). Вершины графа Г и рёбра, которые добавлены, тоже образуют граф. Он приведён на рисунке 5 (б). Такой граф называют дополнением графа Г и обозначают его Г. Дополнением графа Г называется граф Г с теми же вершинами, что и граф Г, и с теми и только теми рёбрами, которые необходимо добавить к графу Г, чтобы получился полный граф. Рис. 3Рис. 4Рис. 5 Г: а) Г': б)

7 3. Степень вершины Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат. Степенью вершины называется число рёбер графа, которым принадлежит эта вершина. Обозначать степени вершин А, В, С будем соответственно так: степ. А, степ. В, степ. С и т. п. У графа на рисунке 6 (а): степ. А = 1; степ. В = 2. У графа на рисунке 6 (б) степени всех вершин равны нулю. Вершина называется нечётной, если её степень - число нечётное. Вершина называется чётной, если её степень - число чётное. Задача. Участники слёта, познакомившись, обменялись конвертами с адресами. Докажите, что а) всего было передано чётное число конвертов; б) число участников, обменявшихся конвертами нечётное число раз, чётное. DС АВ Г: а) Рис. 6 DС АВ Г: б)

8 б) в равенстве N = степ. А 1 + степ. А степ. А n-1 + степ. А n сумма нечётных слагаемых должна быть чётной, а это может быть только в том случае, если число нечётных слагаемых чётно. А это означает, что число участников, обменявшихся конвертами нечётное число раз, чётное. В ходе решения задачи доказаны две теоремы. Теорема 1. В графе Г сумма степеней всех его вершин - число чётное, равное удвоенному числу рёбер графа. Теорема 2. Число нечётных вершин любого графа чётно. Решение. Пусть участники слёта А 1, А 2, А 3,..., А n - вершины графа, а рёбра соединяют на рисунке 7 пары вершин, изображающих ребят, обменявшихся конвертами: а) степень каждой вершины А i показывает число конвертов, которые передал участник А i своим знакомым. Общее число переданных конвертов N равно сумме степеней всех вершин графа. N = степ. А 1 +степ. А степ. А n-1 + степ. А n, но N = 2 р, где р - число рёбер графа, то есть N - чётное. Следовательно, было передано чётное число конвертов; А1А1 А2А2 А7А7 А6А6 А5А5 А3А3 А4А4 Рис Степень вершины

9 4. Путь в графе. Цикл Как пройти по рёбрам на рисунке 8 из А 1 в А 5 ? Вот три последовательности рёбер, следуя которым можно попасть из А 1 в А 5 : (А 1,А 4 ); (A 4,A 6 ). (А 1,А 2 ); (А 2,А 4 ); (А 4,А 5 ). (А 1, А 4 ); (А 4, А 2 ); (А 2, А 1 ); (А 1, А 4 ); (А 4, А 5 ). А4А4 А3А3 А5А5 А2А2 А1А1 Рис. 8 В одних - рёбра повторяются, в других - не повторяются. Можно указать маршрут от А 1 до А 5, содержащий все вершины графа. Таков, например, маршрут: (А 1, А 2 ); (А 2, А 4 ); (А 4, А 3 ); (А 3, А 1 ); (А 1, А 4 ); (А 4, А 5 ). Но не всякую последовательность рёбер, ведущих из А 1 в А 5, называют путём из А 1 в А 5. Путём от А 1 до А n в графе называется такая последовательность рёбер, ведущая от А 1 к А n, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза. Вершина А 1 - начало пути, вершина А n - конец.

10 4. Путь в графе. Цикл Путь от А 1 до А n называется простым, если он не проходит ни через одну из вершин графа более одного раза. Циклом называется путь, в котором совпадают его начальная и конечная вершины. Простым циклом в графе называется цикл, не проходящий ни через одну из вершин графа более одного раза. Длиной пути называется число рёбер этого пути. А5А5 А2А2 А3А3 А4А4 А6А6 А1А1 Рис. 9 Из определения следует, что последовательность рёбер (А 1, А 4 ); (А 4, А 2 ); (А 2, А 1 ); (А 1,А 4 ), (А 4,А 5 ) не является путём в графе. Заметим, что согласно определению вершины пути могут повторяться, т. е. путь может быть самопересекающимся. Аналогично длиной цикла называется число рёбер в этом цикле. От вершины А 1 до вершины А 6 графа на рисунке 9 можно пройти четырьмя путями; один из них - длины 1, второй - длины 2 и два пути длиной 6.

11 5. Связность графа Задача. Может ли так случиться, что в одной компании из шести человек каждый знаком с двумя и только с двумя другими? Решение. Участника этой компании изобразим вершиной графа, а отношение знакомства между двумя участниками - ребром. Изобразим графы, которые могут соответствовать такой компании (рис.10 и 11). Итак, ситуация, рассмотренная в задаче, вполне возможна. Но случай, рассмотренный на рисунке 11, соответствует не одной, а двум компаниям, участники одной из них не знакомы с участниками другой. Про граф, изображенный на рисунке 10, говорят, что он связный, так как из каждой вершины по рёбрам можно попасть в любую другую. Делаем вывод, что в этом случае каждый через своих знакомых может познакомиться со всеми остальными. Во втором случае получились два простых цикла, не сцепленные между собой в вершинах. Такой граф называется несвязным. Рис. 10 Рис. 11 Рис. 12 H D E C B А Граф называется связным, если каждые две вершины его связные. Граф называется несвязным, если хотя бы две вершины его несвязные. Две вершины А и В графа называются связными, если в графе существует путь с концами А и В. Две вершины графа называются несвязными, если в графе не существует ни одного пути, связывающего их. Пример. В графе Г (рис.12) вершины А и В - связные, а вершины А и Н - несвязные.

12 Теорема 3. Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2. Прямая теорема. Если Г - связный граф и степень каждой его вершины равна 2, тогда Г - простой цикл. Доказательство. Из каждой вершины данного графа в любую другую ведёт путь. Начнём путь из какой-нибудь вершины А и пройдем по одному из двух рёбер, которым принадлежит эта вершина. Попав во вторую вершину, выйдем из неё по второму ребру и т. д. С необходимостью все рёбра графа будут пройдены, и мы вернёмся в исходную вершину А (рис.13). Путь замкнётся. Обратная теорема. Если граф Г - простой цикл, тогда степень каждой его вершины равна двум. Покажем, что в простом цикле не может быть вершины, степень которой не равна двум. Доказательство. Так как граф Г - замкнутый простой путь, то из каждой его вершины можно попасть в любую другую, не проходя ни через какую вершину более одного раза. Степень каждой вершины такого графа равна двум. Если какая-то вершина в графе имеет степень меньше двух, то она не принадлежит никакому простому циклу (рис.14). Если какая-то вершина имеет степень больше двух, то никакой простой цикл (по определению) не может содержать все рёбра, которым принадлежит эта вершина (рис.15). А А Рис. 15 Рис. 14 Рис Связность графа

13 6. Операция удаления ребра. Мост Важные закономерности, свойственные графам, обнаруживаются при удалении из них рёбер. При удалении ребра (А, В) из графа Г получается граф с теми же вершинами, что и граф Г, и всеми рёбрами, кроме ребра (А, В). Пример осуществления операции удаления ребра (А, В) из графа показан на рис.16. При удалении ребра из связного графа новый граф может оказаться как связным, так и несвязным. Приведите примеры. Ребро (А, В) называется мостом графа Г, если в графе, полученном после удаления из Г ребра (А, В), вершины А и В оказываются несвязными. На рисунке 16 мост (А, В) выделен штриховой линией. Существуют несколько признаков мостов. Известно, что признак какого-то объекта может заменить его определение, т. е. по признаку можно распознать объект. Рассмотрим признаки мостов. В А В А Рис. 16

14 6. Операция удаления ребра. Мост 1. Ребро (А, В) является мостом в том и только в том случае, если (А, В) - единственный путь, соединяющий вершины А и В (рис.17). 2. Ребро (А, В) является мостом в том и только в том случае, если найдутся две вершины С 1 и С 2 такие, что каждый путь, соединяющий их, содержит А и В (рис.18). 3. Ребро (А, В) является мостом в том и только в том случае, если оно не принадлежит ни одному циклу (рис.17 и 19). Докажем справедливость третьего признака. Прямая теорема. Если ребро (А, В) не ни одному циклу, то (А, В) - мост. Прямая теорема. Если ребро (А, В) не принадлежит ни одному циклу, то (А, В) - мост. Так как ребро (А, В) не принадлежит ни одному циклу, то при его удалении не останется пути, связывающего А и В, т. е. (А, В) является мостом (рис.17). Обратная теорема. Если ребро (А, В) - мост, то (А, В) не принадлежит ни одному циклу. Если бы ребро (А, В) принадлежало циклу (рис.19), то при удалении ребра (А, В) остался бы второй путь, связывающий А и В (на рисунке 19 он выделен штриховой линией), т. е. ребро (А, В) не было бы мостом. Следовательно, (А, В) не принадлежит циклу. В А В А С2С2 С1С1 Рис. 18 Рис. 19 В А Рис. 17

15 7. Деревья. Лес Задача: а) Нарисуйте граф с семью вершинами и шестью рёбрами, не имеющий ни одного цикла. б) Нарисуйте связный граф с семью вершинами и шестью ребрами. в) Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь. Рис. 20 г) Постройте связный граф с семью вершинами, каждое ребро которого - мост. Рассмотрим внимательно рисунки, которые строили при решении задачи. Что характерно для всех построенных графов? Во-первых, они связные; во-вторых, они не содержат циклов. Такие графы выделяются в отдельный класс, представители которого именуются деревьями Деревом называется всякий связный граф, не имеющий циклов (рис.20). Граф, состоящий из одной изолированной вершины, тоже является деревом. Для каждой пары вершин дерева существует единственный соединяющий их путь. Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 20 висячие вершины выделены).

16 7. Деревья. Лес Лесом называется несвязный граф, представляющий объединение деревьев (рис.21 и 22). Всякое ребро в дереве (и в лесе) является мостом (признак 3). Постройте какое-нибудь дерево с пятью вершинами и подсчитайте число рёбер в полученном графе. Оказывается, что в любом дереве с пятью вершинами всегда будет четыре ребра. Теорема. Дерево с в вершинами имеет в - 1 ребро. Для того чтобы из одного дерева Г, не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из Г одно ребро. Для образования трёх деревьев необходимо удалить из Г два каких-нибудь ребра. Самое большее из дерева Г с в вершинами можно получить в деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить в - 1 ребро из дерева Г. Итак, действительно, в дереве с в вершинами в - 1 ребро. Рис. 21 Рис. 22

17 8. Изображение графа Один и тот же граф может выглядеть на рисунках по-разному. Например, на трёх рисунках 23 (а), (б), (в), мало похожих друг на друга, изображён один и тот же граф (полный граф с четырьмя вершинами). Чтобы убедиться в том, что два рисунка изображают один и тот же граф, необходимо проверить: 1. Одинаковое ли число вершин на обоих рисунках? 2. Одинаковое ли на них число рёбер? 3. Одинаковое ли на них число вершин имеет степень k Но выполнение перечисленных трёх условий еще не достаточно для того, чтобы два рисунка изображали один и тот же граф. Действительно, на рисунках 24 (а) и 24 (б) изображены графы, имеющие по 7 вершин, по 10 рёбер, причём по одной вершине степени 4, по четыре вершины степени 3, по две вершины степени 2. Но эти рисунки изображают разные графы, так как если на рисунке 24 (б) вершины степени 2 (В 6 и В 7 ) соединены между собой ребром, то на рисунке 24 (а) вершины степени 2 (А 6 и А 7 ) ребром не соединены. б) в) а) Рис. 23 А7А7 А3А3 А2А2 А1А1 А4А4 А5А5 А6А6 В7В7 В3В3 В2В2 В1В1 В4В4 В5В5 В6В6 б)а) Рис. 24 Сформулируем необходимое и достаточное условие соответствия двух рисунков одному и тому же графу. Они изображают один и тот же граф тогда и только тогда, когда между вершинами на первом и на втором рисунках существует такое взаимно однозначное соответствие, при котором: 1) две вершины графа на первом рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на втором рисунке; 2) две вершины графа на втором рисунке соединены ребром, если соединена ребром соответствующая пара вершин графа на первом рисунке.

18 Теория графов - наука сравнительно молодая: во времена Ньютона такой науки ещё не было, хотя и были в ходу «генеалогические деревья», представляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях Петербургской Академии наук. Начиналась эта работа с рассмотрения задачи о кенигсбергских мостах. Задача. Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи). Различные части города были соединены семью мостами, как показано на рис.25. В воскресные дни горожане совершают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и потом вернуться в начальную точку пути? 9. Задача о кенигсбергских мостах Рис. 25 D А В С a b cd e f g

19 Рис Задача о кенигсбергских мостах D А В С ab cd e f g Решение. Обозначим различные части города буквами А, В, С, Д, а мосты – буквами a, b, c, d, e, f, g. В этой задаче существенны лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, и, наоборот, переходя из одной части города в другую, мы непременно пройдём по мосту. Поэтому изобразим план города в виде графа, вершины которого А, В, С и Д (рис.26) изображают отдельные части города, а рёбра a, b, c, d, e, f, g - мосты, соединяющие соответствующие части города. Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый и непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами, этот граф можно было бы вычертить, не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру. Но это невозможно – какую бы вершину мы ни выбрали за исходную, нам придётся проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро (мост, которым мы воспользуемся затем, чтобы покинуть эту часть города): число рёбер, входящих в каждую вершину, будет равно числу рёбер, выходящих из неё, т.е. общее число рёбер, сходящихся в каждой вершине, должно быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует.

20 10. Эйлеровы графы Попробуйте обвести изображения графов на рисунке 27, не отрывая карандаша от бумаги и не проходя уже по обведённому ребру вторично. Задание по обведению рёбер удается выполнить для графов на рис.27 (а, б, г, д). Графы на рис.27 (в, е) нарисовать без отрыва карандаша от бумаги или не проходя дважды по рёбрам не удастся. В чём секрет? Какие свойства графа повлияли на это? Для удобства введём специальные понятия. Эйлеровым путём в графе называется путь, содержащий все рёбра графа. Эйлеровым циклом в графе называется цикл, содержащий все рёбра графа. Граф, обладающий эйлеровым циклом, называется эйлеровым графом. б)в)а) д)е)г) Рис. 27 К задачам на эйлеровы графы относятся головоломки, в которых требуется вычертить на плоскости одним росчерком замкнутые кривые, обводя каждый участок в точности один раз. Принято всякую замкнутую линию, если её можно начертить, не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз, называть уникурсальной. Рисунок графа, обладающего эйлеровым путём или эйлеровым циклом, является уникурсальной линией.

21 10. Эйлеровы графы Теорема. Если граф Г обладает эйлеровым циклом, то он связный и все его вершины чётные. Доказательство. Связность графа следует из определения эйлерова цикла. Эйлеров цикл содержит каждое ребро и притом только один раз, поэтому, сколько раз эйлеров путь приведёт конец карандаша в вершину, столько и выведет, причём уже по другому ребру. Следовательно, степень каждой вершины графа должна состоять из двух одинаковых слагаемых: одно - результат подсчёта входов в вершину, другое - выходов. Верно и обратное утверждение. Теорема. Если граф Г связный и все его вершины чётные, то он обладает эйлеровым циклом. Если граф не обладает эйлеровым циклом, то можно поставить задачу об отыскании одного эйлерова пути или нескольких эйлеровых путей, содержащих все рёбра графа. Теорема. Если граф Г обладает эйлеровым путём с концами А и В (А не совпадает с В), то граф Г связный и А и В - единственные нечётные его вершины. Доказательство. Связность графа следует из определения эйлерова пути. Если путь начинается в А, а заканчивается в другой вершине В, то и А и В - нечётные, даже если путь неоднократно проходил через А и В. В любую другую вершину графа путь должен был привести и вывести из неё, то есть все остальные вершины должны быть чётными. Верно и обратное. Теорема. Если граф Г связный и А и В единственные нечётные вершины его, то граф Г обладает эйлеровым путём с концами А и В.

22 11. Гамильтоновы циклы и пути в графах В 1857 году ирландский математик Гамильтон предложил игру, названную «путешествие по додекаэдру». Игра сводилась к обходу по рёбрам всех вершин правильного додекаэдра (рис.28) при условии, что ни в одну из вершин нельзя заходить более одного раза. Додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников. У него 20 вершин и 30 рёбер. На рисунке 28 изображён додекаэдр с прозрачными гранями. Вершины и рёбра додекаэдра составляют некоторый плоский граф. Плоское его представление можно получить следующим образом. Пусть рёбра проволочного додекаэдра можно растягивать без разрывов. Взявшись за вершины А, В, C, D, E, растянем «каркас» додекаэдра на плоскости так, чтобы не появилось новых точек пересечения рёбер (рис.29). Плоское представление готово. Рис. 29 Рис. 28 А С В D Е А С В D Е

23 11. Гамильтоновы циклы и пути в графах Задача. Найдите цикл, содержащий все вершины додекаэдра, причём в точности по одному разу каждую. Для определенности начните путь из вершины 1 и в первую очередь посетите вершины 2, 3, 4 и 5 (рис.30). Один из возможных циклов показан на рисунке 31. Если использовать нумерацию вершин этого рисунка, то другой цикл запишется так: 1, 2, 3, 4, 5, 6, 19, 18, 14, 15, 16, 17, 7, 8, 9, 10, 11, 12, 13, 20. Гамильтоновым циклом (путём) в графе называется цикл (путь), проходящий через каждую вершину графа в точности по одному разу. Гамильтоновым путём в графе называется путь, проходящий через каждую вершину графа в точности по одному разу. Гамильтонов путь (цикл) всегда является простым. Он может не содержать всех рёбер графа. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом. Рис. 30 Рис

24 11. Гамильтоновы циклы и пути в графах Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все рёбра, и притом по одному разу каждое, вторые - все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их отыскания резко отличаются по степени трудности. Как вы уже знаете, для решения вопроса о существовании эйлерова цикла на графе достаточно выяснить, все ли его вершины четны. Критерий же существования гамильтонова цикла на произвольном графе ещё не найден. Решение этой проблемы имеет практическую ценность, так как к игре Гамильтона близка известная задача о коммивояжере, который должен объехать несколько пунктов и вернуться обратно. Он обязан побывать в каждом пункте в точности по одному разу и заинтересован затратить на поездку как можно меньше времени. А для этого требуется определить все варианты посещения городов и подсчитать в каждом случае затрату времени. По своей математической постановке игра Гамильтона близка к задаче о порядке переналадки станков, задаче о подводке электроэнергии к рабочим местам и др. Рассмотрим здесь несколько достаточных условий существования гамильтоновых циклов в графе. Во-первых, всякий полный граф является гамильтоновым. Действительно, он содержит такой простой цикл, которому принадлежат все вершины данного графа. Во-вторых, если граф, помимо простого цикла, проходящего через все его вершины, содержит и другие рёбра, то он также является гамильтоновым. На рисунке 32 простой (гамильтонов) цикл выделен жирной линией (1, 2), (2, 3), (3, 4), (4, 5), (5, 1). Заметим также, что если граф имеет один гамильтонов цикл, то он может иметь и другие гамильтоновы циклы Рис. 32

25 Часть II Задача о мостах «Помощь молодожёнам»

26 1. Задача По аналогии с задачей Л. Эйлера о Кенигсбергских мостах можно рассмотреть следующую задачу: Задача: Город Тверь – один из живописных городов Центральной России. Главная река страны Волга разделяет город на две части. Кроме того, Тверь расположена на берегах рек Тверцы, Тьмаки и Лазури. Через город проходит железнодорожная магистраль, соединяющая Москву с Санкт-Петербургом. Различные части Твери соединены между собой многочисленными мостами, что придаёт особый колорит городу. У жителей Твери есть традиция: в день свадьбы молодожёны совершают мини-путешествие, стремясь на машине объехать как можно больше городских мостов. Считается, что пара, сумевшая объехать все мосты города, будет счастливой всю жизнь. Возникает вопрос: можно ли объехать все мосты города Тверь ровно один раз? Если можно, то какой маршрут движения выбрать и сколько времени займёт такая прогулка?

27 2. Решение Решение: 1. Составим схему города Тверь: 1. Составим схему города Тверь: Буквами А, В, С, Д, Е, F обозначены части города. Буквами a, b, c, d, e, f, i, j, k, l, m, n, o, p, r, s – мосты, соединяющие части города. С c d D В А E F n m p o r j i sf e k l a b ж. д. р. Лазурь р. Тьмака р. Тверца р. Волга

28 2. Решение 2. Построим граф, соответствующий схеме города Твери. Граф состоит из 6 вершин А, В, С, Д, Е, F, соответствующих частям города на схеме и 16 рёбер a, b, c, d, e, f, i, j, k, l, m, n, o, p, r, s, среди которых рёбра l и m - ориентированные, остальные – неориентированные. Каждое ребро графа соответствует определённому мосту Твери. Например, ребро a – Старый мост через Волгу, ребро e - Восточный мост, ребро j – мост через железную дорогу и т.д. С c d D В А E F n m p o r j i sf e l a b k

29 2. Решение 3. Найдём степени вершин графа. степень А = 5, степень В = 7, степень С = 3, степень D = 8, степень Е = 5, степень F = 4. Вывод 1. Так как граф содержит вершины нечётных степеней, то согласно теореме Эйлера, у графа не существует эйлерова цикла, т.е. цикла, содержащего все рёбра графа без повторений. Это значит, что невозможно составить маршрут, начало и конец которого совпадают, и который проходит по каждому мосту города ровно один раз.

30 2. Решение 4. Для того чтобы у графа существовал эйлеров путь, необходимо и достаточно, чтобы степени только двух вершин графа были нечётные, а остальные чётные. Вывод 2. Так как граф содержит 4 вершины нечётных степеней, то для него невозможно составить эйлеров путь, т.е. маршрут, содержащий все рёбра графа ровно один раз, начало и конец которого приходятся на вершины с нечётными степенями. 5. Чтобы задача имела решение, необходимо изменить степени двух нечётных вершин графа на чётные.

31 2. Решение I способ: Убрать ребро r (мост через Волгу на окружной дороге). Тогда граф будет иметь 15 рёбер и степени вершин будут следующими: степень А = 4, степень В = 6, степень С = 3, степень D = 8, степень Е = 5, степень F = 4. Для нового графа (I) выполняется условие о существовании эйлерова пути. Он может начинаться и заканчиваться или в вершине Е, или в вершине С. Так как задача посвящена молодожёнам, то начало пути – вершина Е (место нахождения центрального ЗАГСа), а конец пути – С. С c d D В А E F n m p o j i sf e l a b k (I)

32 2. Решение Один из возможных маршрутов следующий: n k a d e s j i f l o p m b c. Центральный ЗАГС, пл. Капошвара, ул. Спартака, мост через Тьмаку (n), пр-кт. Калинина, ул. С.Перовской, мост через Тьмаку (k), Старый мост через Волгу (a), ул. Мусоргского, мост через Тверцу (d), Затверецкий бульвар, ул. Маяковского, Восточный мост через Волгу (e), ул. Вагжанова, пер. Вагжановский, мост через Лазурь (s), пр-кт Победы, ул. Орджоникидзе, мост через железную дорогу (j), ул. Можайского, Октябрьский пр-кт, мост через железную дорогу (i), Волоколамский пр-кт, мост через Лазурь (f), Смоленский пер., ул. Новоторжская, мост через Тьмаку (l), ул. Бебеля, Комсомольская пл., мост через Тьмаку (o), ул. Заслонова, мост через Тьмаку (p), ул. Строителей, пр-кт Калинина, ул. Брагина, мост через Тьмаку (m), Тверской пр-кт, Новый мост через Волгу (b), мост через Тверцу (c), ул. Туполева.

33 2. Решение На плане в масштабе 1 : данный маршрут имеет протяжённость 155 см. Найдём длину маршрута: х=155. 0,25 х=155. 0,25 х=38,75 х=38,75 Учитывая среднюю скорость движения по городу 40 км/ч, получаем среднее время t = s / v t = 38,75/40 = 58 (мин) на плане на местности 155 см х км 1 см 0,25 км 1551 х 0,25=

34 2. Решение II способ: Убрать ребро d (дальний мост через Тверцу). Тогда получим граф (II) с шестью вершинами А, В, С, Д, Е, F и 15-ю рёбрами. получим граф (II) с шестью вершинами А, В, С, Д, Е, F и 15-ю рёбрами. Степени вершин: Степени вершин: степень А = 4, степень А = 4, степень В = 7, степень С = 2, степень D = 8, степень Е = 5, степень F = 4. У графа (II) только две вершины В и Е имеют нечётную степень, поэтому, согласно условию существования эйлерова пути, существует путь из Е в В, содержащий каждое ребро графа (II) ровно один раз. С c D В А E F n m p o r j i sf e l a b k (II)

35 2. Решение Возможный маршрут: n k b c e f i j s a r o p m l. Центральный ЗАГС, пл. Капошвара, ул. Спартака, мост через Тьмаку (n), пр-кт. Калинина, ул. С.Перовской, мост через Тьмаку (k), Новый мост через Волгу (b), мост через Тверцу (c), ул. Туполева, ул. Маяковского, Восточный мост через Волгу (e), ул. Вагжанова, мост через Лазурь (f), Волоколамский пр-кт, мост через железную дорогу (i), Октябрьский пр-кт, ул. Можайского, ул. Левитана, мост через железную дорогу (j), ул. Орджоникидзе, пр-кт Победы, ул. Терещенко, мост через Лазурь (s), Смоленский пер., ул. Советская, пл. Революции, Старый мост через Волгу (a), С-Петербургское шоссе, окружная дорога, мост через Волгу (r), пр-кт 50 лет Октября, Комсомольская пл., мост через Тьмаку (o), ул. Заслонова, мост через Тьмаку (p), ул. Строителей, ул. М.Конева, пр-кт Калинина, ул. Брагина, мост через Тьмаку (m), мост через Тьмаку (l), ул. Бебеля.

36 2. Решение На плане в масштабе 1 : данный маршрут имеет протяжённость 199 см. Найдём длину маршрута: х=199*0,25 х=199*0,25 х=49,75 х=49,75 Учитывая среднюю скорость движения по городу 40 км/ч, получаем среднее время t = s / v; t = 49,75/40 = 1,2 (ч). Вывод 3. Работа над данной задачей показала, что можно составить маршрут движения по городу так, чтобы он начинался и заканчивался в разных частях города и содержал 15 мостов ровно по одному разу. Время, необходимое на объезд 15-ти мостов, примерно 1 час. на плане на местности 155 см х км 1 см 0,25 км 1551 х 0,25=

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

38 Литература 1. Березина Л.Ю. Графы и их применение. – М.: Просвещение, Гусев В.А., Орлов А.И., Розенталь А.Л. Внеклассная работа по математике в 6 – 8 классах. – М.: Просвещение, Оре О. Теория графов. – М.: Наука, Уилсон Р. Введение в теорию графов. – М.: МИР, Гуцанович С.А. Занимательная математика в базовой школе. – Минск: Тетрасистемс, 2004.