Теорема Эйлера. Обозначим количество вершин буквой р, а количество ребер буквой q.

↑

▷ Содержание

⇐ ПредыдущаяСтр 12 из 15Следующая ⇒

Сумма степеней графа равна удвоенному числу ребер:

d (V ) = 2q.

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

Для двух смежных вершин в сумму их степеней каждое ребро входит дважды.

Что и требовалось доказать.

Изоморфизм.

Над графом можно производить различные действия: добавить / удалить ребро / вершину, изменить направление ребра ит.д.

Два графа называются изоморфными, если при преобразовании не нарушается смежность.

          Рис 5. Граф 1                                Рис. 6 Граф 2.

Пример изоморфных графов.

В самом деле, вершинам V_1, V₂, V₃  смежными в обоих графах являются вершины V₄, V_5,  V₆. Вершинам V₄, V_5,  V₆ смежными в обоих графах являются вершины V_1, V₂, V_{3  ,} что и доказывает их изоморфизм_.

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

 Рассмотрим граф

Рис. 7. Граф 3

Будет ли этот граф изоморфным графу 1? Количество вершин и ребер одинаково. Пусть V ₁   - в левом верхнем углу. Тогда смежные вершины V₄,  V₅, V ₆   расположатся по соседним углам и в левой внутренней точке. Например, так

                         V ₁                                                V₅

                                                            V ₆

                        V₄

Рис. 8. Граф 3₁

Если вершину V₂ разместить в углу, то ока не будет смежна с V ₆. Если вершину V₂ разместить в средине, то ока не будет смежна с V₄. Ничего нового не будет, если разместить V ₁ в любом углу. Разместим V₁ в средине. Тогда смежные вершины V₄,  V₅, V ₆   расположатся по углам

                          V ₆                                              V₅

                                    V ₁

                   V₄

Рис. 9. Граф 3₂

Если вершину V₂ разместить в средине, то ока не будет смежна с V₄. Если вершину V₂ разместить в углу, то ока не будет смежна с V ₆.

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

Инварианты.

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

Рассмотрим следующее утверждение:

Если при преобразовании количество вершин, ребер и степень вершины являются инвариантами, то преобразование - изоморфизм.

Однако наше предложение не является теоремой. В этом нас убеждает граф 3, у которого перечисленные характеристики совпадают с характеристиками графа 1, но эти графы не изоморфны.

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

Подграфы.

Пусть задан граф G(V,E). Граф G  (V ,E ) называется подграфом графа G, если

V  V  и/или Е Е .

 Если V= V , то подграф G  называется остовным.

Рис 10. Остовной подграф графа 1

Маршруты. Цепи. Циклы.

Пусть задан граф G(V,E). Последовательность вершин и ребер V l V l …l V , в которой каждые два соседних элемента инцидентны, называется маршрутом.

Замечание: маршрут может быть задан последовательностью вершин: V , V ,V ,…,V . Вершины V  и V  - концы маршрута.

Маршрут, в котором все ребра различны, называется цепью.

Цепь, в которой все вершины различны, называется простой цепью.

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

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

Граф, не имеющий циклов, называется ациклическим.

Задача. Выделить маршрут, связывающий V , V , цепь, простую цепь, цикл, простой цикл. Рис.111

Рис. 11. Маршруты, цепи, циклы.

Решение:

V , l , V , l , V , l , V , l , V  - маршрут, но не цепь.

V , V , V , V , V  - цепь.

V , V , V , V  - простая цепь.

V , V , V , V , V , V  - цикл.

V , V , V , V  - простой цикл.

Теорема. Если существует цепь, соединяющая две вершины, то существует и простая цепь.

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

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

Что и требовалось доказать.

Замечание:  в орграфах цепь называется путем, а цикл - контуром.

Расстояние.

Пусть имеется цепь, связывающая две вершины. Количество ребер, входящих в цепь, называется расстояниемd (U, V), где U и V – концы цепи.

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

Наибольшее из расстояний называется диаметром графа.

Вершины, находящиеся на одном и том же расстоянии от заданной вершины, образуют ярус.

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

Рис.12. Пример полного графа.

Связность.

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

Рис.0. Связный граф. Рис.14. граф с двумя компонентами связности.

Задание графа.

· Матрица смежности.

Пусть имеется граф G с n вершинами. Рассмотрим квадратную матрицу n, элементами которой являются 0 и 1.

а

                                        V V V         V

                                А =

Эта матрица называется матрицей смежности, и она симметрична относительно главной диагонали.

Пример Дан граф

матрица смежности

                     V V V V4

            А =

Рис. 15. Пример задания графа матрицей смежности

· Матрица инцидентности.

Матрица инцидентности устанавливает связь вершин и инцидентных с ней ребер.

b_ij =

Пример                 V      l ₂  V

                             l ₁               

                                                         l ₃                     

                   V1                                

                                                          V4

Матрица инцидентности 

       V V V V4                                            

        Рис.16. Задание графа матрицей инцидентности                                                                                                           

· Список смежности.

В списке смежности указывается вершина и смежные с ней вершины.

V (V , V );

V (V , V );

V (V , V , V );

V (V , V );

V (V , V );

V (V , V , V );

V (V );

V (V );

Рис. 17. Задание графа списком смежности.

Задание графа в виде списка смежности полезно при решении задачи обхода всех вершин графа: обследовать все вершины графа, побывав в каждой 1 раз.

Различают два метода решения этой задачи:

1) Поиск в глубину.

2) Поиск в ширину.

При поиске в глубину некоторая вершина выбирается в качестве начальной и помечается. Затем рассматривается список смежности этой вершины и из него выбирается первая вершина и помечается (какая-то вершина U). Рассматривается список смежности для вершины U. Выбирается первая вершина и помечается (W).Рассматриваем список смежности для W, и так далее пока не столкнемся со случаем, что вершины списка помечены. Возвращаемся в вершину U и выбираем не помеченную вершину, если такая есть. Продвигаемся в этом направлении до тех пор, пока список вершины не оказывается помеченным. Опять возвращаемся назад и так далее. В итоге все вершины будут помечены.

Пример: Рис 17

Пусть начальная вершина V (метка 1).В списке смежности вершины V  числится V (метка 2). В списке смежности V  - вершина V (метка 3). В списке смежности вершины V  имеются вершины V ,V ,V . V  уже помечена. Из V  следуем в V (метка 5). V V (метка 6). Аналогично, V V (метка 7). Теперь возвращаемся в V . Все вершины помечены. Аналогично и в V ,V , V . В списке смежности V  имеется непомеченная вершина - V (метка 8). В списке V  все вершины помечены. Возвращаемся в V . Здесь тоже все помечены. Следовательно, обход графа завершен. См. рис. 18

Рис. 18. Граф с помеченными вершинами при обходе в глубину.

Приведенный нами алгоритм убеждает в справедливости теоремы:

 Если граф конечен и связан, то при обходе в глубину каждая вершина обходится по одному разу.

Замечание:

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

Поиск в ширину. Смысл поиска в ширину заключается в том, что некоторую вершину V мы объявляем начальной - V . Перебираем весь список смежности этой вершины. Когда список исчерпан, то есть все вершины, достижимые из V , помечены, мы переходим к 1 – ой вершине из помеченных. Затем, исчерпав список этой вершины, переходим ко 2 – ой вершине из 1 – ых помеченных и так далее до тех пор, пока не останется непомеченных вершин.

Пример: См. рис. 19.

Пусть V₇ (метка 1)- начальная вершина. В списке смежности у вершины V  вершина V₆ (метка 2). Больше нет вершин в списке смежности V . Переходим в V . V (V ,V ,V ). Назначаем метку вершине V (метка 3). V  - помечена, V (метка 4). Список вершины V  исчерпан, переходим в вершину V  (V ,V ,V ). Вершины V (метка 5), V (метка 6). Возвращаемся в список вершины V . Вершины V  и V  - помечены. Возвращаемся в V , затем в V (V ,V ). V (метка 7). Возвращаемся в V  и переходим в V . V (V ,V ). Переходим в V . Все вершины из списка V  помечены. Переходим в V . Список V  - помечен. Непомеченных вершин не осталось. Поиск в ширину закончен.

Рис 19. Пометки вершин графа при поиске в ширину.

Ясно, что последовательность поиска в глубину и в ширину зависит от выбора V .

 Метод математической индукции:

Мы заметили некоторую закономерность в значениях изучаемой последовательности. Проверяем эту закономерность для n=1. Предполагаем, что формула справедлива при некотором n и доказываем, что она справедлива для n=n+1. Подставляем в формулу n+1 и получаем формулу, которой соответствует (n+1) – ый член. Затем получаем (n+1) – ый член, исходя из общего принципа построения последовательности. Получим формулу для n+1. Если эти формулы совпадают, то закономерность считается доказанной.

Пример:

S , при n=1 эта формула справедлива: Пусть она справедлива при некотором n. Если она справедлива для n+1, то должно быть S .

 Получим эту формулу из общих соображений.

S_n+1 = S_n + n +1 = + n+1 = (n+1) ( +1) =

Что и требовалось доказать.

Двудольные графы.

Пусть задан граф G. Если вершины графа могут быть разбиты на два множества Х и У G(V,E), V= Х У, таких, что каждая вершина множества Х смежна со всеми вершинами множества У (следовательно, каждая вершина из У смежна со всеми вершинами из Х), и все вершины каждого из этих подмножеств между собой не смежены, то такой граф называется двудольным.

                           Рис. 20. Пример двудольного графа.

Граф Понтрягина – Куратоввского – тоже двудольный граф.

Познавательные статьи:



Техника прыжка в длину с разбега

Организация работы процедурного кабинета

Области применения синхронных машин

Оптимизация по Винеру и Калману