Комбинаторика
<<  Задачи по комбинаторике с решениями Определение графа  >>
Эйлеровы графы
Эйлеровы графы
Изоморфизм графов
Изоморфизм графов
Подграф
Подграф
Планарный и плоский графы
Планарный и плоский графы
Укладка планарных графов
Укладка планарных графов
Маршруты, связность и компоненты
Маршруты, связность и компоненты
Cвязность и компоненты
Cвязность и компоненты
Маршруты орграфа
Маршруты орграфа
Метрические характеристики
Метрические характеристики
Эйлеровы графы
Эйлеровы графы
Эйлеровы пути и циклы
Эйлеровы пути и циклы
Эйлеров цикл в связном графе
Эйлеров цикл в связном графе
Выходя из произвольной вершины идем вдоль ребер соблюдая следующие
Выходя из произвольной вершины идем вдоль ребер соблюдая следующие

Презентация: «Эйлеровы графы». Автор: Valery. Файл: «Эйлеровы графы.pps». Размер zip-архива: 2400 КБ.

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

содержание презентации «Эйлеровы графы.pps»
СлайдТекст
1 Эйлеровы графы

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

{ изоморфизм графов - подграф - планарный и плоский графы - укладка плоских графов - маршруты, связность и компоненты - метрические характеристики - Эйлеровы графы - Эйлеровы пути и циклы - Эйлеров путь в связном графе - Алгоритм Флери – нахождение эйлерова цикла }

2 Изоморфизм графов

Изоморфизм графов

Графы G1 и G2 называются изоморфными, если существует такая биекция f множества VG1 на множество VG2 , что (a,b) принадлежит EG1 тогда и только тогда, когда ( f(a), f(b) ) принадлежит EG2 . Отображение f в этом случае называется изоморфизмом графа G1 на G2 .

a

b

c

d

a

b

d

c

d

c

x (VG1)

f(x) (VG2)

Изоморфизм - бинарное отношение на множестве графов. Очевидно, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.

3 Подграф

Подграф

Подграфом графа G называется граф, все вершины которого принадлежат V(G) , а все рёбра принадлежат E(G) .

G1 – полный граф

G2 – подграф графа G1

G3 – подграф графов G1 , G2 Максимально пустой подграф G2

4 Планарный и плоский графы

Планарный и плоский графы

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

Изображенные три графа – планарные, но только два из них плоские.

Жордановой кривой на плоскости называют непрерывную кривую без самопересечений.

Граф, который может быть уложен на плоскости, называется планарным.

5 Укладка планарных графов

Укладка планарных графов

Двудольный граф. Это графы, у которых множество вершин можно разбить на два множества V1 , и V2 , так что каждое ребро графа соединяет только некоторую вершину из V1 с некоторой вершиной из V2 .

K3,3

Говорят, что граф может быть уложен в данном пространстве, если он изоморфен некоторому графу, изображенному в этом пространстве при помощи точек – вершин графов, и жордановых кривых, представляющих ребра, причем эти кривые не пересекаются друг с другом. Графы K5 , K3,3 – непланарные графы.

Задача о трех домах и трех колодцах, между которыми требуется провести непересекающиеся дорожки, иллюстрируется двудольным графом K3,3 . Видно, что решение невозможно, если граф будет плоским (планарным).

Дома

Дорожки

Колодцы

6 Маршруты, связность и компоненты

Маршруты, связность и компоненты

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

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

Для графа на множестве вершин задается отношение соединимости: вершина a соединима с вершиной b , если существует соединяющий их маршрут. Это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются областями связности, а порождаемые ими подграфы - компонентами связности графа. В связном графе имеется только одна компонента связности - весь граф. Компоненты связности можно определить как максимальные по включению связные подграфы данного графа.

7 Cвязность и компоненты

Cвязность и компоненты

g

e

b

d

{e}

h

s

f

a

{d}

c

{f,h,g,s}

{a,b,c}

У приведенного графа имеется две области связности:

{d,e,f,h,g,s}

Вершина называется шарниром (точкой сочленения), если при ее удалении число компонент связности увеличивается. У приведенного графа это e и f.

Ребро, при удалении которого увеличивается число компонент связности, называется перешейком. У приведенного графа их два – (d,e) и (e,f).

8 Маршруты орграфа

Маршруты орграфа

Соответственно определяются и два типа связности орграфов. Орграф называется связным (или слабо связным), если для каждой пары вершин в нем имеется соединяющий их маршрут. Он называется сильно связным, если для каждой упорядоченной пары вершин a, b в нем имеется ормаршрут, ведущий из a в b . Максимальные по включению подмножества вершин орграфа, порождающие сильно связные подграфы, называются его областями сильной связности, а порождаемые ими подграфы - компонентами сильной связности.

Для ориентированного графа можно определить два типа маршрутов. Неориентированный маршрут (или просто маршрут) - это чередующаяся последовательность вершин и ребер, где ei = (xi,xi+1 ) = (xi+1,xi ) , и ориентированный (ормаршрут), где переход вдоль ребра ведется от вершины с меньшим индексом к вершине с большим индексом.

9 Метрические характеристики

Метрические характеристики

Если в графе нет пути, соединяющего a и b, то есть эти вершины принадлежат разным компонентам связности, то расстояние между ними считается бесконечным.

Расстояние от заданной вершины a до наиболее удаленной от нее вершины x называется эксцентриситетом вершины – ecc(a) = maxx изV(G) d(a,x). Наибольший эксцентриситет называется диаметром графа diam(G), наименьший – радиусом rad(G).

Функция d(a,b) обладает следующими свойствами:

Расстоянием между двумя вершинами графа называется наименьшая длина пути, их соединяющего. Расстояние между вершинами a и b обозначается d(a,b).

D(x,y) >= 0, причем d(x,y) = 0 тогда и только тогда, когда x = y d(x,y) = d(y,x) d(x,y) + d(y,z) >= d(x,z) (неравенство треугольника)

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

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

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

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

В одном из писем Эйлер писал по этому поводу: "... это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека ..."

На языке теории графов задача состоит в том, чтобы определить, имеется ли в графе путь, проходящий через все его ребра (напомним, что путь, по определению, не может дважды проходить по одному ребру). Такой путь называется эйлеровым путем, а если он замкнут, то эйлеровым циклом..

11 Эйлеровы пути и циклы

Эйлеровы пути и циклы

В этом графе есть эйлеров цикл

В этом графе цикла нет, но есть эйлеровы пути

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

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

Доказательство: Необходимость : при каждом прохождении цикла через какую либо вершину используются два ребра: по одному входим, по другому выходим из вершины. Таким образом у всех вершин степень четная. Доказывается и достаточность условия.

12 Эйлеров цикл в связном графе

Эйлеров цикл в связном графе

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

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

Пример эйлерова цикла в связном графе

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

13 Выходя из произвольной вершины идем вдоль ребер соблюдая следующие

Выходя из произвольной вершины идем вдоль ребер соблюдая следующие

правила: стираем ребра по мере их прохождения, а также изолированные вершины, которые при этом образуются; на каждом этапе идем по мосту только тогда, когда нет другой возможности.

Алгоритм Флери - построение эйлерова цикла

«Эйлеровы графы»
http://900igr.net/prezentacija/algebra/ejlerovy-grafy-225663.html
cсылка на страницу
Урок

Алгебра

35 тем
Слайды