Представление о плоском графе. Формула Эйлера. Задача о мостах.

Формула Эйлера.
Задача о мостах.

его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются

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

Плоский граф

графа непременно найдется плоское представление. 
Плоские графы — это простые циклы, деревья, лес,

а также граф, содержащий цикл, из вершин которого "выходят" деревья.

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

Лес

Дерево

плоском представлении графа  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.

выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём

он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

графа), а частям города — точки соединения линий (вершины графа).

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

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

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

карандаш от бумаги, при этом движение нужно начать с одной

из этих нечетных вершин и закончить во второй из них.

найти путь в этом графе.

Первый многосвязный садовый лабиринт был

сооружён в 1820-е годы в Чевнинге в Великобритании.

квадрата 4x4 убрать угловые клетки.
Можно ли обойти ее ходом шахматного

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

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

ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон –

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

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

соединить проводами так, чтобы каждый телефон был соединен ровно с

пятью другими ?

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

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

графа равно половине суммы степеней его вершин. Так как количество

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

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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