Графы. Задача о мостах.
Характеристика плоского графа. Формула Эйлера. Задача о мостах.
Скачать:
| Вложение | Размер |
|---|---|
 grafy_danilchenko_parkina.pptx | 361.89 КБ |
Предварительный просмотр:
Подписи к слайдам:
Содержание Плоский граф. Планарный граф Формула Эйлера Задача о мостах Рисунок одним росчерком пера Применение графов Задачи
Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины. Граф , изоморфный плоскому графу, называется планарным . Планарный граф можно определить еще так: граф планарен , если его можно уложить на плоскости. Рисунок графа, в котором никакие два его ребра не пересекаются, если не считать точками пересечения общие вершины, называют плоским представлением графа . Плоский граф
Ясно, что плоское представление имеет только плоский граф . Обратно, у всякого плоского графа непременно найдется плоское представление. Плоские графы — это простые циклы, деревья, лес, а также граф, содержащий цикл, из вершин которого "выходят" деревья. Пример . Примером неплоского графа может служить полный граф с пятью вершинами. Любые попытки начертить его плоское представление обернутся неудачей.
В качестве характеристики плоского представления графа вводится понятие грани. Гранью в плоском представлении графа 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. Планета имеет форму выпуклого многогранника, причем в его вершинах расположены города, а каждое ребро является дорогой. Две дороги закрыты на ремонт. Докажите, что из любого города можно проехать в любой другой по оставшимся дорогам. Решение. Пусть A и B - данные города. Докажем сначала, что из A в B можно было проехать до закрытия на ремонт двух дорог. Рассмотрим для этого проекцию многогранника на некоторую прямую, не перпендикулярную ни одному из его ребер (при такой проекции вершины многогранника не сливаются).
Пусть A' и B' - проекции точек A и B, а M' и N' - крайние точки проекции многогранника (в точки M' и N' проецируются вершины M и N). Если идти из вершины A так, что в проекции движение будет происходить по направлению от M' к N' , то, в конце концов, мы обязательно попадем в вершину N. Аналогично из вершины B можно пройти в N. Таким образом, можно проехать из A в B (через N). Если полученный путь из A и B проходит через закрытую дорогу, то есть еще два объезда по граням, для которых это ребро является общим. Вторая закрытая дорога не может находиться сразу на двух этих объездах. Значит, из города A в город B можно проехать, по крайней мере, одним путем. Задачи
Сказка "12 месяцев". История и современность
Фильм "Золушка"
Сказка на ночь про Снеговика
Приключения Тома Сойера и Гекельберри Финна
Голубая лягушка