🗊Презентация Графы. (Тема 1)

Тема 1. Графы

Граф – наглядное представление конечного антирефлексивного симметричного отношения Граф – конечное множество V, называемое множеством вершин, на котором задано симметричное антирефлексивное отношение R и выделено множество Е двухэлементных подмножеств V, определяемое как {a, b}  E тогда и только тогда, когда (a, b)  R и a  b. Множество Е называется множеством ребер. Всякий элемент Е называется ребром. Граф обозначается G(V, E). Элементы a и b графа V соединены или связаны ребром {a, b}, если {a, b}  E.

Конечный граф изображается при помощи диаграммы, в котором вершины представлены точками, ребра, соединяющее вершины, линиями между точками. Пример Граф, в котором множество вершин V= {a, b, c}, E={{a, b}, {b, c}} может иметь вид или

Пример Граф, в котором множество вершин V={a, b, c, d , e}, Е={{a, b}, {a, e}, {b, e}, {b, d}, {b, c}, {c, d}} имеет диаграмму

Определения Ориентированный граф, или орграф G состоит из множества V вершин и отношения E на V, называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован. Обозначается G(V, E) Элемент множества Е называется ориентированным ребром. Если (a, b)  E, тогда a называется начальной вершиной (a, b), b - его конечной вершиной.

В случае ориентированного графа допускается наличие петель. Пример Орграф с вершинами V={a, b, c} и ребрами E={(a, b), (b, c), (c, b), (c, a)} Порядок имеет значение. (a, b) может быть ребром диаграммы, (b, a) – нет.

Пример Орграф с вершинами V={a, b, c, d} и ребрами E={(a, b), (b, c), (c, c), (b, d), (c, d), (d, a)}

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

Пример (*) Пусть С = {1, 2, 3}, Х – множество всех подмножеств множества С: Определим отношение R на Х посредством (T, V)  R, если T  V. ({2}, {1, 2})  R, поскольку {2}  {1, 2} и ({1, 2}, {3})  R, поскольку {2, 3}  {3}. R – отношение частичного порядка, (A, R) – ЧУ-множество.

Пример Пусть S – множество действительных чисел, R1 – отношение, определенное условием (x, y)  R1, если х  у. R1 – отношение частичного порядка, (S, R1) – ЧУ-множество. Обозначение. Частично упорядочение принято обозначать через  а ЧУ-множество - через (S, ).  -частичный порядок на множестве S.

Определение Два элемента a и b ЧУ-множества (S, ) сравнимы, если a  b или b  a. Если каждые два элемента ЧУ-множества (S, ) сравнимы, то (S, ) называется вполне упорядоченным множеством, или цепью.

Примеры Пусть Т – множество положительных делителей числа 30 и 1 есть отношение m 1 n, если m делит n нацело. Целые числа 5 и 15 сравнимы, поскольку 5 делит 15 нацело, а 5 и 6 – нет. Пусть А – множество целых чисел и R= 2 – отношение х 2 у, если х меньшее или равно у. Упорядоченное множество (А, 2) является цепью.

Пример Пусть S – множество всех подмножеств множества {a,b,c} 3 есть отношение частичного порядка в примере (*). Множества {a, b} и {a,b,c} сравнимы, однако {a, b} и {b,c} таковыми не являются. ЧУ-множество (S, 3) цепью не является.

Диаграммы Гессе Для изображения ЧУ-множеств. Для заданного ЧУ-множества (А, 2) диаграмма Гессе состоит из совокупности точек и линий, в которой точки представляют элементы А, и если a  c для элементов a и с множества А, тогда а помещено ниже с, и они соединены линией, если не существует такое b  a, c, что a  b  c. Если рассмотрение отношений ограничено отношениями частичного порядка, для них диаграммы Гессе – просто ориентированный граф, в котором петли не указаны. Если a  b  c, тогда линия от a к с не указана.

Диаграмма Гессе, соответствующая множеству (Т, 1) Диаграмма Гессе, соответствующая множеству (Т, 1)

Диаграмма Гессе, соответствующая множеству (S, 3) Диаграмма Гессе, соответствующая множеству (S, 3)

Матрицы инцидентности и смежности Задание любой из этих матриц дает возможность восстановить граф

Пусть G - граф. Пусть В – матрица, строки которой обозначены вершинами графа, а столбцы обозначены ребрами графа. Считаем, что вершины и ребра графа пронумерованы. Элемент i –ой строки и j –го столбца матрицы В (Вij ) равен 1, если i-ая вершина инцидентна j-му ребру, и равен 0 в противном случае. Матрица В называется матрицей инцидентности графа G.

Пусть G - граф. Его матрица инцидентности:

Пусть G - граф. Его матрица инцидентности:

Пусть G – граф (ориентированный граф). Пусть В – матрица, строки которой обозначены вершинами графа и столбцы обозначены теми же вершинами в том же самом порядке. Элемент i-ой строки и j-го столбца матрицы В, обозначаемый Вij , равен 1, если имеется ребро (ориентированное ребро) из i-ой вершины в j-ю вершину, и равен 0 в противоположном случае. Матрица В называется матрицей смежности графа G.

Пусть G - граф. Его матрица смежности:

Пусть G – ориентированный граф . Его матрица смежности:

Матрица смежности для ориентированного графа, у которого четыре и восемь ребер :

представляет собой матрицу смежности графа G с вершинами v1, v2, v4, v4. Матрица

представляет собой матрицу смежности графа G с вершинами v1, v2, v4, v4.

Пусть G – (ориентированный) граф с вершинами v1, v2, v3, …, vn и матрицей смежности А. Путь длины k, или k-путь из vi в vj для 1kn существует тогда и только тогда, когда Теорема Пусть G – (ориентированный) граф с вершинами v1, v2, v3, …, vn и матрицей смежности А. Из вершины vi в vj имеется m путей длины k, где 1kn тогда и только тогда, когда

Алгебраические свойства графов

Определение. Функция f из графа G(V, E) в граф G'(V ', E ') называется гомоморфизмом из G в G' и обозначается f :G  G' , если обладает следующими свойствами: Если e  E , то f(e)E ' . (f(E)  E '). Если v  V , то f(v)V ' . (f(V)  V '). Если вершины u и v инцидентны ребру e графа G, то вершины f(u) и f(v) инцидентны ребру f(e) графа G'.

Теорема. Если функция f – гомоморфизм из G в G' , то f(G) - подграф (f(V), f(E)) графа G‘. Теорема. Если граф G связный и f – гомоморфизм, то граф f(G) связный. Теорема. Если граф G полный и f – гомоморфизм, то граф f(G) полный. Замечание. Многие свойства графа G не являются инвариантными относительно f.

Определение. Гомоморфизм f :G  G' , является изоморфизмом, если f :V  V' и f :E  E' представляют собой взаимно однозначные соответствия. Если f :G  G' - изоморфизм, то G и G' называются изоморфными. Изоморфизм является переименованием вершин и ребер графа V, которое сохраняет свойство гомоморфности, так что если вершины u и v инцидентны ребру e графа G, то вершины f(u) и f(v) инцидентны ребру f(e) графа G' . Практически все свойства графов инвариантны относительно изоморфизма. Простейший способ показать неизоморфизм двух графов – установить свойство, которым обладает один граф и не обладает другой.

Определение. Если граф G(V, E) содержит ребро e={v1, v2} и граф G'(V ', E ') получен из графа G(V, E) добавлением новой вершины v в множество V и заменой ребра {v1, v2} ребрами ={v1, v} и ={v, v2} , то граф G'(V ', E ') называется расширением графа G(V, E). Если графы G1 , G2 , G3 , …, Gn таковы, что Gi+1 является расширением графа Gi , то граф Gn называют производными от графа G1 . Если граф G'(V ', E ') расширение графа G(V, E) , то посредине одного из ребер множества V появляется вершина, а исходное ребро делится на два новых ребра, которые соединяют вершины, инцидентные исходному ребру, и новую вершину.

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

Пример. Граф является производным от графа

Пример. Граф является производным от графа

Пример. Граф является гомеоморфным графу

Теорема. Если графы G и G' – гомеоморфны, то у них одинаковое количество вершин нечетной степени. Доказательство: Если граф G'(V ', E ') – расширение графа G(V , E ), то новая добавленная вершина имеет степень 2. Степени других вершин не изменились. Теорема Если графы G и G' гомеоморфны, то граф G имеет эйлеров цикл (собственный путь) тогда и только тогда, когда граф G' имеет эйлеров цикл (собственный путь). Если G' - подграф графа G , то обозначается

Определение. Пусть G(V, E) - граф и G1 , G2 , G3 , …, Gn - подграфы графа G. Подграф G' графа G называется объединением графов G1 , G2 , G3 , …, Gn и обозначается если 1. Вершина v G' тогда и только тогда, когда v Gi для некоторого 1in. 2. Ребро e G' тогда и только тогда, когда e Gi для некоторого 1in.

Определение. Пусть G(V, E) - граф и G1 , G2 , G3 , …, Gn - подграфы графа G. Подграф G' графа G называется пересечением графов G1 , G2 , G3 , …, Gn и обозначается если 1. Вершина v G' тогда и только тогда, когда v Gi для некоторого 1in. 2. Ребро e G' тогда и только тогда, когда e Gi для некоторого 1in.

Определение. Пусть G(V, E) - граф G1 , G2 , G3 , …, Gn - подграфы графа G. Подграфы G1 , G2 , G3 , …, Gn являются попарно непересекающимися, если Gi  GJ =  для всех 1i<jn. Теорема. Если G1 и G2 – различные компоненты графа G, то G1 и G2 - попарно непересекающиеся. Теорема. Граф G является объединением попарно непересекающихся компонент.

Определение. Пусть G(V, E) - граф. Дополнением графа G называется граф такой, что для всех вершин u, v V ребро между вершинами u и v в графе GC существует тогда и только тогда, когда в графе G отсутствует ребро, соединяющее u и v . Определение. Подграф G'(V ', E ') является остовным графом для графа G(V, E) , если V' = V.

Пример. Для графа остовные графы

Пример. Для графа остовными не являются графы

Определение. Дерево называется остовным деревом графа G, если оно является остовным графом графа G. Теорема. Если T(V, E ') - остовное дерево графа G(V, E), то для любого цикла v0v1v2v3v4 … v0 , по крайней мере, одно из ребер принадлежит E – E '. Определение. Множество ребер С графа G(V, E) называется разрезающим множеством, если удаление ребер из множества С нарушает связность графа, а удаление собственного подмножества множества С оставляет граф связным. Если множество С состоит из одного ребра, то это ребро называется разрезающим ребром.

Пример. Для графа e5 и e6 – разрезающие ребра

Пример. Для графа {{v1, v2}, {v5, v6}} и {{v2, v3}, {v6, v7}} – разрезающие множества

Теорема. Если T(V, E ') - остовное дерево графа G(V, E) и С – разрезающее множество графа G, то С  Е '  . Теорема. Ребро e графа G является разрезающим ребром графа G тогда и только тогда, когда оно не входит в цикл графа G.

Задача Сколько городов лишится связи, если коммутационная сеть выйдет из строя в определенном городе (вершине графа). Вопрос: Что произойдет, если удалить вершину графа? Определение. Вершина a  V связного графа G=(V, E) является разрезающей вершиной, или точкой сочленения, если удаление этой вершины и инцидентных ей ребер к нарушению связности графа. Определение. Граф G=(V, E) называется двусвязным, если не содержит точек сочленения.

Теорема Вершина a графа G=(V, E) является точкой сочленения тогда и только тогда, когда существуют различные вершины u и v такие, что каждый путь из v в w проходит через a . Доказательство: Достаточность. Предположим, каждый путь из вершины v в w проходит через вершину a. Если a удалена  не существует более одного пути из v в w , граф G становится несвязным.  Вершина a – точка сочленения. Необходимость. Доказательство от противного. Пусть для каждой пары вершин v и w существует путь, который не проходит через a. При удалении вершины a для всех v , w  V всегда остается путь из вершины v в w  граф G остается связным  Вершина a не является точкой сочленения.

Пример. Вершины v3, v4, v6 – разрезающие вершины

Теорема Для связного графа G=(V, E) определим отношение R на E: e1 R e2 , если e1 = e2 или в графе G существует простой цикл, содержащий e1 и e2 в качестве ребер. Тогда отношение R является отношением эквивалентности. Определение. Пусть для каждого класса эквивалентности Ei и отношения эквивалентности R Vi - множество вершин, инцидентных ребрам из множества Ei и Gi =(Vi, Ei ) - подграф графа G=(V, E) с вершинами Vi и ребрами Ei . Подграф Gi =(Vi, Ei ) называется компонентой двусвязности графа G=(V, E). Теорема. Если (a, b) и (с, d) - различные ребра из компоненты двусвязности Gi =(Vi, Ei ) , то в графе Gi =(Vi, Ei ) существует простой цикл, содержащий в качестве ребер (a, b) и (с, d).

Теорема. Если компонента двусвязности Gi =(Vi, Ei ) состоит из единственного ребра ei , то ei - разрезающее ребро графа G. Теорема. Если каждые два различных ребра входят в общий простой цикл графа G=(V, E) , то граф G=(V, E) - двусвязный. Следствие. Подграф G=(V, E) - двусвязный. Теорема. Если Gi =(Vi, Ei ) и GJ =(VJ, EJ ) - компоненты двусвязности графа G=(V, E) , то Vi  VJ содержит не более одной вершины.

Теорема. Вершина a является точкой сочленения тогда и только тогда, когда для некоторого i  j эта вершина принадлежи Vi  VJ для компонент двусвязности Gi =(Vi, Ei ) и GJ =(VJ, EJ ) . Теорема. Граф G=(V, E) является двусвязным тогда и только тогда, когда любые два различных ребра входят в один и тот же простой цикл графа G=(V, E). Теорема. Если Gi =(Vi, Ei ) - компонента двусвязности графа G=(V, E) и Gi =(Vi, Ei )  G =(V, E ), то существует, по крайней мере, одна несовпадающая компонента дусвязности GJ =(VJ, EJ ) такая, что Vi  VJ содержит ровно одну вершину.

Последний слайд лекции