Множества. Комбинаторика. Отношения (стр. 23 )

ТЕОРЕМА. Для любого плоского связного графа G имеем .

Доказательство. Рассмотрим два плоских непересекающихся графа G1 и G2. Пусть – дуга, одна вершина которой принадлежит , а другая G2. Пусть – наложениена По лемме 2 , поскольку граф . Кроме того, наложение графа на граф G2 также связно, а поэтому . Аналогично получим . Из произвольности графов получаем, что любые два плоских связных графа имеют одну и ту же эйлерову характеристику. Поэтому достаточно подсчитать её для простейшего плоского связного графа. <

Замечание. Условие связности графа существенно для доказательства теоремы. Например, для несвязного графа имеем

3.1.8 Теорема Понтрягина – Куратовского

ТЕОРЕМА. Графы К3.3 и К5 не допускают плоской реализации.

Доказательство. Предположим, что граф К3.3 имеет плоскую реализацию. Тогда для него

В графе К3.3 нет циклов длины З, так как любое ребро ведёт из одной группы вершин к другой, т. е. любой цикл в имеет длину ³4. Так как то для числа рёбер графа имеем

,

где – число рёбер, ограничивающих грань с номером , Полученное противоречие доказывает первую часть теоремы.

Допустим, что граф К5 допускает плоскую реализацию. Для него: Пусть имеют тот же смысл, что и раньше. Очевидно, . Противоречие. <

Доказанная теорема допускает обращение.

ТЕОРЕМА Понтрягина – Куратовского. Для того, чтобы граф был планарным чтобы он не содержал подграфов, гомеоморфных К3.3 и К5. <

Упражнения

1) Является и плоским двудольный граф с двумя вершинами? Полный граф К6?

2) Является ли плоским граф:

G1: 12 13 14 25 26 27 35 37 36 46 47 45 56 67;

G2: 12 23 34 48 81 14 82 45 56 67 87 46;

G3: 12 13 15 18 23 24 34 38 45 46 47 56 57 58 67 78.

3.1.9 Эйлеровы графы

Задача о кенигсбергских мостах. Постановка и решение этой задачи Эйлером знаменует начало разработки теории графов. Расположение мостов через реку Прегель в г. Кенигсберге в его время приведено на рис. 1.

Требуется пройти каждый мост по одному разу и вернуться в исходную часть города. Можно построить граф задачи, в которой каждой части города соответствует вершина, а каждому мосту – ребро, инцидентное вершинам, относящимся к соединяемым им частям (рис.2). Обходу мостов соответствует маршрут графа, который по условию должен быть простым циклом. Эйлеровой цепью графа называется маршрут, включающий все рёбра графа. Замкнутая эйлерова цепь – эйлеров цикл. Эйлерову цепь и эйлеров цикл называют эйлеровыми графами.

ТЕОРЕМА. Граф имеет эйлеров цикл а) связен, б) все его вершины имеют положительные чётные степени.

Доказательство. Необходимость очевидна.

Докажем вначале, что в графе , все вершины которого имеют чётную степень для любого ребра x найдётся цикл, содержащий x. Пусть a0, a1 – концы ребра x. Так как степень вершины a1 чётна, то найдётся другое ребро x2, отличное от x, инцидентное a1. Пусть a2 – вторая концевая точка ребра x2. Маршрут простой. Продолжая таким образом получим последовательность простых маршрутов увеличивающейся длины. В силу конечности графа через некоторое время продлить маршрут будет невозможно. Это значит, что маршрут заканчивается в вершине a0.

Рассмотрим в графе G замкнутый простой маршрут , содержащий наибольшее число рёбер. Покажем, что в графе нет вершин, не лежащих на этом маршруте. Предположим, что некоторая вершина b не лежит на нём. Так как граф связан, то существуют цепи между b и каждой из всех вершин максимального маршрута. Рассмотрим наиболее короткую цепь Вершины не могут совпадать с вершинами , в противном случае можно было бы выбрать цепь длины <m. Следовательно, ребро ym не входит в выбранный путь.

Из множества рёбер графа удалим и полученное множество рёбер обозначим через . В графе все вершины имеют чётную степень, т. е. в нём существует простой замкнутый маршрут, включающий ребро ym. Пусть это будет маршрут .

Если в исходный маршрут вместо ai подставить этот маршрут, то получим маршрут длины >. Это противоречит тому, что – максимальная длина простого замкнутого маршрута в графе. Следовательно, простой замкнутый маршрут максимальной длины проходит через все вершины графа.

Предположим, что он содержит не все рёбра графа. Тогда в графе найдётся ребро y, инцидентное одной из вершин ai и не входящее в максимальный маршрут. Повторив рассуждения, проведённые для ym, получим противоречие. <

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

Необходимость очевидна.

Пусть a,b – две вершины нечётной степени. Соединим их ещё одним ребром x. После этого все вершины графа приобретут чётную степень, т. е. в нём существует замкнутая эйлерова цепь. Осталось удалить из неё ребро x. <

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

ТЕОРЕМА. Если число вершин графа n > 3 и степени всех вершин больше, чем n/ 2, то граф гамильтонов. <

Упражнения

1)  Приведите примеры эйлерова, но не гамильтонова графа; неэйлерова, но гамильтонова графа; неэйлерова и одновременно негамильтонова графа.

2)  Существуют ли эйлеровы циклы или гамильтоновы цепи для следующих графов:

3.1.10 Оценка числа графов

Лемма 1. >;

Доказательство. Проведём индукцию по n. При имеем >. Пусть >. Тогда (к+1)! >>, так как >, что в свою очередь следует из известного неравенства