Среда, 17.04.2024, 01:34
Мультимедийное пособие по дискретной математике
|
Меню сайта
Лекции
Лекции
|
Эйлеровы графы Дан граф. Требуется найти в нем маршрут, проходящий по каждому ребру ровно один раз. Начало и конец – в одной вершине. Такой маршрут называется Эйлеровым циклом, а граф, в котором он существует, называется Эйлеровым графом. Степень вершины в графе – это число ребер, инцидентных этой вершине. Критерий эйлеровости графа. Для того, чтобы связный граф без петель был Эйлеровым, необходимо и достаточно, чтобы степень его вершины была четным числом. Планарные графы. Определение. Укладкой графа называется такое его геометрическое изображение, при котором ребра пересекаются только в вершинах. Если существует укладка графа на плоскости, то граф называется планарным. Сама же укладка графа без пересечения ребер называется плоским графом. Любой граф можно изобразить в трехмерном пространстве без пересечения ребер.  Для любого графа xi, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости. Граф будет планарным, если существует его укладка на сфере.  Доказательство следует из взаимно однозначного соответствия точек на сфере с точками плоскости из стереографических проекций. Следствие. Граф любого выпуклого многогранника планарен. Ребра плоского графа разбивают плоскость на несколько частей, одна из которых бесконечна. Эти части и являются гранями плоского графа. Теорема Эйлера о плоских графах. Формула Эйлера. Для плоского графа справедливо соотношение. M – N + P = 2. Докажем индукцией по числу граней P = 1 Если P = 1, то граф – дерево. В нем нет ни одного цикла. У дерева число вершин больше числа ребер на 1. M = N + 1 N + 1 – N + 1 = 2 – справедливо. Пусть p = k, и утверждение верно. Тогда оно верно и при P= k+1 Берем ребро графа, отделяющее бесконечную грань от внутренних и удаляем это ребро из графа. Т.к. оно циклическое, то в новом графе g1 (он также будет связным) число вершин M останется прежним. N1 = N – 1 P1 = P – 1 M = M k + 1-1 = k Для g1 справедливо предположение индукции. M1 + N1 + P1 = 2 M – N – 1 + K = 2 M – N + K – 1 = 2 M – N + P = 2 Что и требовалось доказать. Следствие 1. Для плоского связного простого графа справедливо соотношение n <= 3*(m-2) Следствие 2. Для плоского связного простого графа без треугольных граней справедливо соотношение n <= 2*(m-2) Следствие 3. Граф K5 – непланарен.  И если бы он был плоским, то для него было бы справедливо следствие 1. N <= 3*(m-2) 10 <= 9 – неверно. Противоречие. Значит, он не может быть нарисован плоским. Следствие 4. Граф K3-3 непланарен.  Нет треугольных граней. Если бы он был плоским, то для него было бы справедливо следствие 2. 9 <= 2*(6-2) 9 <= 8 – неверно. Противоречие из предположения, что он не может быть плоским. Операцией разбиения ребра графа называется следующая процедура: Ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра. Два графа называются гомеоморфными, если каждый из них может быть получен из одного и того же графа путем применения конечного числа раз операции разбиения ребер. Теорема Понтрягина – Куратовского. Чтобы граф был планарным, необходимо и достаточно, чтобы он не содержал гомеоморфных подграфов. |
Поиск
Счеткич визитов
Друзья сайта
|