Представление о плоском графе. Формула Эйлера. Задача о мостах.
Представление о плоском графе. Формула Эйлера. Задача о мостах.
В данной работе показаны элементы дискретной математики: характеристика и изображение плокого графа, формула Эйлера, задача о мостах и объяснение решения по теоремам Эйлера.
Эйлеровым путем в графе называется путь, проходящий по всем ребрам графа ровно по разу. Существование эйлерова пути как раз и означает, что граф можно нарисовать, не отрывая карандаша от бумаги и проводя каждое ребро ровно по разу. Эйлеровым циклом называется такой тип эйлерова пути, в котором начальная и конечная вершины совпадают (то есть, здесь образуется цикл и в нем начальной вершиной можно считать любую). Существование эйлерова цикла означает, что граф можно нарисовать еще и так, чтобы карандаш вернулся в первую нарисованную вершину. Эйлеровым графом для краткости называют граф, содержащий эйлеров путь или эйлеров цикл.
Критерий Эйлера: В связном графе существует эйлеров путь тогда и только тогда, когда в нем не более 2-х нечетных вершин, а эйлеров цикл - тогда и только тогда, когда в нем все вершины четные. В несвязном графе очевидно, что эйлерова пути существовать не может (но он существует в тех компонентах связности, которые удовлетворяют критерию).
Вы уже знаете о суперспособностях современного учителя?
Тратить минимум сил на подготовку и проведение уроков.
Быстро и объективно проверять знания учащихся.
Сделать изучение нового материала максимально понятным.
Избавить себя от подбора заданий и их проверки после уроков.
Просмотр содержимого документа
«Представление о плоском графе. Формула Эйлера. Задача о мостах. »
Представление о плоском графе.
Формула Эйлера.
Задача о мостах.
ГБОУ СПО Московский Издательско-Полиграфический Колледж им. Федорова
Плоский граф
Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины.
Граф, изоморфный плоскому графу, называется планарным . Планарный граф можно определить еще так: граф планарен, если его можно уложить на плоскости.
Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа.
Ясно, что плоское представление имеет только плоский граф . Обратно, у всякого плоского графа непременно найдется плоское представление.
Плоские графы — это простые циклы, деревья, лес, а также граф, содержащий цикл, из вершин которого "выходят" деревья.
Лес
Дерево
Пример . Примером неплоского графа может служить полный граф с пятью вершинами. Любые попытки начертить его плоское представление обернутся неудачей.
В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа G называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.
Пример :
На рисунке показано плоское представление графа G с тремя гранями: (1,5,4,1) , (1,3,2,4,1), (1,2,3,1). Часть плоскости, ограниченная простым циклом (1,2,4,1), гранью не является, так как содержит цикл (1,2,3,1).
Простой цикл, ограничивающий грань, называется границей грани . Две грани будем называть соседними , если их границы имеют хотя бы одно общее ребро.
Пример :
В данном графе часть плоскости, ограниченная простым циклом (1,2,3,4,1) , является гранью, так как ребро (4,5) , расположенное внутри грани, не образует цикла.
Не является гранью заштрихованная часть плоскости в данном примере, так как она содержит цикл, да к тому же эта часть плоскости не ограничена циклом. Ребро (1,2) является мостом, соединяющим циклы. Такие мосты называются перегородками.
В качестве грани можно рассматривать и часть плоскости, расположенную "вне" плоского представления графа. Она ограничена "изнутри" простым циклом и не содержит других циклов. Эту часть плоскости называют бесконечной гранью.
На рисунке часть бесконечной грани заштрихована. Всякое плоское представление графа либо не имеет бесконечной грани, либо имеет в точности одну бесконечную грань. Как особый случай вводится бесконечная грань в плоском представлении дерева и леса. В плоском представлении дерева и леса за грань принимают всю плоскость рисунка.
Формула Эйлера
Для всякого плоского представления связного плоского графа без перегородок число вершин ( V ), число ребер ( E ) и число граней с учетом бесконечной ( R ) связаны соотношением V – E + R = 2 .
Задача о мостах
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера , о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины (т.е. все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Рисунок одним росчерком
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. Решая задачу о кенигсбергских мостах, Эйлер сформулировал свойства графа: Невозможно начертить граф с нечетным числом нечетных вершин.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Применение графов
Лабиринт - это граф. А исследовать его - это найти путь в этом графе.
Первый многосвязный садовый лабиринт был сооружён в 1820-е годы в Чевнинге в Великобритании.
Задачи
№1 . Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.
Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?
Решение: Занумеруем последовательно клетки доски:
А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:
№2 Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение : Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями. Теперь сразу видно, что долететь с Земли до Марса нельзя.
№3 В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Связность графа
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.
