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

1

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

3 Графы G 1 и G 2 называются изоморфными, если существует такая биекция f множества V G1 на множество V G2, что (a,b) принадлежит E G1 тогда и только тогда, когда ( f(a), f(b) ) принадлежит E G2. Отображение f в этом случае называется изоморфизмом графа G 1 на G 2. dd cc x (V G1 ) abcd f(x) (V G2 ) abdc Изоморфизм - бинарное отношение на множестве графов. Очевидно, что это отношение рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности. Классы эквивалентности называются абстрактными графами. Когда говорят, что рассматриваются абстрактные графы, это означает, что изоморфные графы считаются одинаковыми. Абстрактный граф можно представлять себе как граф, у которого стерты имена (пометки) вершин, поэтому абстрактные графы иногда называют также непомеченными графами.

4 Подграфом графа G называется граф, все вершины которого принадлежат V (G), а все рёбра принадлежат E (G). G 1 – полный граф G 2 – подграф графа G 1 G 3 – подграф графов G 1, G 2 Максимально пустой подграф G 2

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

6 Говорят, что граф может быть уложен в данном пространстве, если он изоморфен некоторому графу, изображенному в этом пространстве при помощи точек – вершин графов, и жордановых кривых, представляющих ребра, причем эти кривые не пересекаются друг с другом. Графы K 5, K 3,3 – непланарные графы. Двудольный граф Двудольный граф. Это графы, у которых множество вершин можно разбить на два множества V 1, и V 2, так что каждое ребро графа соединяет только некоторую вершину из V 1 с некоторой вершиной из V 2. Задача о трех домах и трех колодцах Задача о трех домах и трех колодцах, между которыми требуется провести непересекающиеся дорожки, иллюстрируется двудольным графом K 3,3. Видно, что решение невозможно, если граф будет плоским (планарным). Дорожки Колодцы Дома K 3,3

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

8 У приведенного графа имеется две области связности: a b c d e f g hs {a,b,c} {d,e,f,h,g,s} {f,h,g,s} {d} {e} Вершина называется шарниром (точкой сочленения), если при ее удалении число компонент связности увеличивается. У приведенного графа это e и f. Ребро, при удалении которого увеличивается число компонент связности, называется перешейком. У приведенного графа их два – (d,e) и (e,f).

9 Для ориентированного графа можно определить два типа маршрутов. Неориентированный маршрут (или просто маршрут) - это чередующаяся последовательность вершин и ребер, где e i = (x i,x i +1 ) = (x i +1,x i ), и ориентированный (ормаршрут), где переход вдоль ребра ведется от вершины с меньшим индексом к вершине с большим индексом. Соответственно определяются и два типа связности орграфов. Орграф называется связным (или слабо связным), если для каждой пары вершин в нем имеется соединяющий их маршрут. Он называется сильно связным, если для каждой упорядоченной пары вершин a, b в нем имеется ормаршрут, ведущий из a в b. Максимальные по включению подмножества вершин орграфа, порождающие сильно связные подграфы, называются его областями сильной связности, а порождаемые ими подграфы - компонентами сильной связности. Очевидно, разные области сильной связности не могут иметь общих вершин, так что множество вершин каждого орграфа разбивается на области сильной связности.

10 Расстоянием между двумя вершинами графа называется наименьшая длина пути, их соединяющего. Расстояние между вершинами a и b обозначается d(a,b). Функция d(a,b) обладает следующими свойствами: В математике функцию двух переменных, определенную на некотором множестве и удовлетворяющую вышеперечисленным условиям, называют метрикой, а множество, на котором задана метрика, - метрическим пространством. Таким образом, множество вершин любого графа можно рассматривать как метрическое пространство. Расстояние от заданной вершины a до наиболее удаленной от нее вершины x называется эксцентриситетом вершины – ecc(a) = max x из V (G) d(a,x). Наибольший эксцентриситет называется диаметром графа diam(G), наименьший – радиусом rad(G). 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) (неравенство треугольника) Если в графе нет пути, соединяющего a и b, то есть эти вершины принадлежат разным компонентам связности, то расстояние между ними считается бесконечным.

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

12 В этом графе есть эйлеров цикл В этом графе цикла нет, но есть эйлеровы пути Рассмотрим условия существования эйлерова цикла в обыкновенном графе. Ясно, что в несвязном графе эйлеров цикл может существовать только в том случае, когда все его ребра принадлежат одной компоненте связности, а все остальные компоненты - просто изолированные вершины. Поэтому достаточно рассматривать связные графы. Доказательство: Необходимость : при каждом прохождении цикла через какую либо вершину используются два ребра: по одному входим, по другому выходим из вершины. Таким образом у всех вершин степень четная. Доказывается и достаточность условия. Теорема Эйлеров цикл в связном графе существует тогда и только тогда, когда в нем степени всех вершин четны.

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

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