Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Формула Эйлера. Следствия из формулы Эйлера



Грань – область графа, ограниченная ребрами.

Плоское изображение графа – изображение, в котором ребра графа не пересекаются.

Планарный граф – граф, имеющий плоское изображение.

Формула Эйлера. Для плоского изображения связного планарного графа справедлива формула: n-m+r=2, гдеr- количество граней, n – число ребер, m – число вершин.

Доказательство.

Пусть – планарный граф с плоским изображением. Возможны 2 случая.

1) – дерево, .

2) не является деревом. Тогда в нем есть циклы. Удалим любое ребро цикла. Число ребер и граней уменьшится на 1.

Тогда граф .

Удаляем ребра в циклах, пока их не останется.

Получим граф , так как в графе нет циклов

является деревом .

Плоский граф – граф, заданный плоским изображением.

Триангуляцией называется плоский граф, все грани которого – треугольники.

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

Следствия из формулы Эйлера.

1)Если в плоском графе каждая грань – k-элементный цикл (каждая грань ограничена k ребрами), то число ребер .

2)В каждой триангуляции число ребер .

3)Необходимое условие планарности.

В планарном графе с числом вершин n≥3, число ребер

4)В каждой триангуляции найдется вершина, степень которой .

Необходимое и достаточное условие планарности графа.

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

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

Теорема. Критерий планарности графа (Понтрягина-Куратовского).

Граф планарен ó, когда не содержит частей, изоморфных графам типа I или типа II.

Доказательство.

Необходимость.

От противного: граф содержит изоморфизм к графам типа I или типа II. Тогда и – полные планарные графы.

В графе : По следствию 2 (из Эйлера) – противоречие.

В графе : . По формуле Эйлера: .

Оценим число ребер.

Каждое ребро не принадлежит 3-х элементному циклу, но принадлежит 4-х элементному.

– противоречие, так как .

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

Если в графе ребер, то путь не может быть

Эйлеров путь – путь длины .

Эйлеров граф – граф, содержащий циклический Эйлеров путь.



Теорема. Критерий эйлеровости графа.

Связный граф является Эйлеровым ó, когда все его вершины четные.

Доказательство.

Необходимость.

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

Достаточность.

Пусть степени всех вершин – четные. Докажем, что существует циклический Эйлеров путь. Выберем любую вершину , двигаясь по ребрам, окрашиваем их. Продолжим движение по неокрашенным, вернемся в . Получим циклический путь, который состоит из окрашенных ребер. ( )

1 случай: все ребра окрашены.

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

Пусть у степень четная, тогда путь может закончиться в вершине .

, где – некоторая цепь. Получили другой циклический путь.

Если остались еще неокрашенные ребра, то продолжаем процедуру. Получаем Эйлеров путь.


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!