Теоремы о степенях вершин и изоморфизм графов

Раздел 2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

Основные определения теории графов

Граф – математический объект, описываемый двумя множествами: G=( V, E ), где V – так называемое множество вершин, а E – множество дуг.

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

Обозначим вершины v1, v2, v3, ¼, а ребра e1, e2, e3, ¼. Вершины vi и vj, определяющие ребро ek, называются концевыми вершинами ребра ek=(vi, vj), а в случае орграфа – началом и концом дуги ek соответственно. Говорят также, что ребро ek (дуга) инцидентно вершинам vi, vj или, что вершины vi, vj инцидентны ребру (дуге) ek. Такие вершины называют смежными. Ребра называют смежными в случае, когда они имеют общую концевую вершину. Например, ek=(vi, vj) и em=(vi, vl) – смежные ребра.

В множестве ребер графа допускается более, чем одно ребро с одинаковыми концевыми вершинами. Такие ребра называются параллельными или кратными. Например: ek=(vi, vj) и em=(vi, vj) – кратные ребра.

Если обе концевые вершины ребра совпадают, то такое ребро называется петлей. Например: ek=(vi, vi) – петля.

Граф без петель и параллельных ребер называется простым, в противном случае – мультиграфом.

Граф, не имеющий ребер, называется пустым, а не имеющий вершин (а значит и ребер) – нуль‑графом.

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

Количество вершин в графе называется порядком графа.

Степенью или валентностью вершины называется число инцидентных ей ребер. Будем обозначать степень вершины vi – deg(vi). Вершина нулевой степени называется изолированной. Вершина степени 1 называется висячей, а ребро, инцидентное ей, называется висячим ребром. Заметим, что петля добавляет двойку к степени вершины.

Способы задания графов.

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

1) Графический способ.

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

Теоремы о степенях вершин и изоморфизм графов - student2.ru На рисунке 12 изображен смешанный граф с вершинами v1, v2,¼, v6, ребрами e1, e2, e3, e5 и дугой e4. Смежные вершины v1, v2, инциденты ребру e1. Вершины v1, v3, инциденты параллельным ребрам e2 и e3. Вершине v4 инциденты петля e5 и дуга e4, причем v4 является началом дуги e4, а v5 – концом этой дуги. Степень вершины v1 равна 3, вершины v2 – 1, вершины v3 – 2, вершины v4 – 3, вершины v5 – 1, вершины v6 – 0. Таким образом, вершины v2 и v5 – висячие, а вершина v6 – изолированная. В случае дуги e4 точнее было бы говорить о полустепенях исхода и захода вершин v4 и v5, а именно: полустепень исхода вершины v4 равна 3, вершины v5 – 0, полустепень захода вершины v4 равна 2, вершины v5 – 1.

2) Аналитический способ.

Граф задают перечислением элементов множества вершин и множества ребер. Для графа, изображенного на рисунке 12, эти множества: V={v1, v2, v3, v4, v5, v6} и Е={e1, e2, e3, e4, e5}, где e1=(v1, v2), e2=(v1, v3), e3=(v1, v3), e4=(v4, v5), и e5=(v4, v4).

3) Матричный способ.

Имеется несколько вариантов задать граф матрицей. Наиболее употребимыми являются матрица инциденций и матрица смежности.

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

Теоремы о степенях вершин и изоморфизм графов - student2.ru

Таким образом, для графа на рисунке 12 матрица инциденций такова:

    e1 e2 e3 e4 e5
v1
v2
I= v3
v4
v5 -1
v6

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

б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: Теоремы о степенях вершин и изоморфизм графов - student2.ru . Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:

    v1 v2 v3 v4 v5 v6
v1
v2
S= v3
v4
v5
v6

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

Теоремы о степенях вершин и изоморфизм графов.

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

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

Теорема 2:Число вершин нечетной степени в любом графе четно.

Два графа G1 и G2 называются изоморфными, если существует биективное отображение между множествами их вершин и ребер такое, что соответствующие друг другу по этому отображению ребра графов G1 и G2 инцидентны соответствующим друг другу по этому же отображению парам вершин этих графов.

Согласно определению, графы, изображенные на рисунке 13, изоморфны. Соответствие между множествами вершин и ребер таково:

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

для вершин: Теоремы о степенях вершин и изоморфизм графов - student2.ru

для ребер: Теоремы о степенях вершин и изоморфизм графов - student2.ru

Подграфы

Подграфом графа G=(V, E) называется граф G¢=(V¢, E¢), у которого множества вершин и ребер V¢ и E¢ являются такими подмножествами множеств V и E соответственно, что ребро (vi, vj)ÎE¢ тогда и только тогда, когда вершины vi и vjÎV¢. Граф G¢ называется собственным подграфом графа G, если V¢Ì V и E¢Ì E. Если все вершины графа G присутствуют в его подграфе G¢, т.е. V¢=V, то G¢ называется остовным подграфом G.

Подграф без изолированных вершин называется реберно-порожденным подграфом. Множество вершин реберно-порожденного подграфа полностью определяется множеством его ребер.

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

На рисунке 14 изображены: (а) исходный граф; (б) собственный подграф; (в) остовный подграф; (г) реберно-порожденный подграф; (д) вершинно-порожденный подграф.

Теоремы о степенях вершин и изоморфизм графов - student2.ru

Операции над графами.

1) Объединение двух графов G=(V, E) и G¢=(V¢, E¢) есть граф S=(V∪V¢,E∪E¢).

На рисунке 15 показано объединение двух графов.

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

2) Пересечение двух графов G=(V, E) и G¢=(V¢, E¢) есть граф S=(V∩V¢,E∩E¢). См. рис.16.

Теоремы о степенях вершин и изоморфизм графов - student2.ru
4) Относительное дополнение подграфа до графа – это граф, в который входят те ребра основного графа, которых не было в подграфе, а множество вершин совпадает с множеством вершин основного графа. См. рис.18.

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

3) Кольцевая сумма двух графов GÅG¢ есть граф, не имеющий изолированных вершин и состоящий только из ребер, присутствующих либо в G, либо в G¢, но не в обоих графах одновременно. Т.о. это ЕÅЕ¢ реберно-порожденный граф. См. рис.17.

Теоремы о степенях вершин и изоморфизм графов - student2.ru 5) Абсолютное дополнение – это дополнение до полного графа на том же множестве вершин. Так для графа, изображенного в правой части равенства на рис.18, абсолютное дополнение будет изображаться так, как показано на рис.19.

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

6) Удаление ребра – ребро удаляется из графа, а инцидентные ему вершины остаются. См.рис.20.

7) Удаление вершины – вершина удаляется из графа вместе со всеми инцидентными ей ребрами. См. рис.21.

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

 
  Теоремы о степенях вершин и изоморфизм графов - student2.ru

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

Теоремы о степенях вершин и изоморфизм графов - student2.ru
9) Стягивание ребра – ребро удаляется, а его концевые вершины отождествляются. На рисунке 23 последовательно стягиваются ребра е1, е3, е2.

Примеры решения задач.

Заданы графы Теоремы о степенях вершин и изоморфизм графов - student2.ru и Теоремы о степенях вершин и изоморфизм графов - student2.ru . Теоремы о степенях вершин и изоморфизм графов - student2.ru , Теоремы о степенях вершин и изоморфизм графов - student2.ru .

1. По заданным Теоремы о степенях вершин и изоморфизм графов - student2.ru и Теоремы о степенях вершин и изоморфизм графов - student2.ru изобразите графы Теоремы о степенях вершин и изоморфизм графов - student2.ru и Теоремы о степенях вершин и изоморфизм графов - student2.ru .

2. Найдите Теоремы о степенях вершин и изоморфизм графов - student2.ru , Теоремы о степенях вершин и изоморфизм графов - student2.ru , Теоремы о степенях вершин и изоморфизм графов - student2.ru , Теоремы о степенях вершин и изоморфизм графов - student2.ru .

3. Для графа Теоремы о степенях вершин и изоморфизм графов - student2.ru найдите маршруты смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.

Теоремы о степенях вершин и изоморфизм графов - student2.ru ={(1,1), (1,4), (2,2), (2,3), (3,3), (3,4), (4,1), (4,2), (4,3)}

Теоремы о степенях вершин и изоморфизм графов - student2.ru ={(1,3), (2,1), (3,1), (3,3)}

                     
    Теоремы о степенях вершин и изоморфизм графов - student2.ru
  Теоремы о степенях вершин и изоморфизм графов - student2.ru
      Теоремы о степенях вершин и изоморфизм графов - student2.ru
 
   
Теоремы о степенях вершин и изоморфизм графов - student2.ru
 
 
 
    Теоремы о степенях вершин и изоморфизм графов - student2.ru   Теоремы о степенях вершин и изоморфизм графов - student2.ru
 

Теоремы о степенях вершин и изоморфизм графов - student2.ru Теоремы о степенях вершин и изоморфизм графов - student2.ru соответствует орграф Матрица смежности

Теоремы о степенях вершин и изоморфизм графов - student2.ru .

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

I II III IV V VI VII VIII IX X XI XII

Теоремы о степенях вершин и изоморфизм графов - student2.ru .

Матрица достижимости Матрица контрдостижимости

Теоремы о степенях вершин и изоморфизм графов - student2.ru Теоремы о степенях вершин и изоморфизм графов - student2.ru .

Матрица сильных компонент Теоремы о степенях вершин и изоморфизм графов - student2.ru .

Матрица маршрутов длины 2:

Теоремы о степенях вершин и изоморфизм графов - student2.ru .

Все маршруты, длины 2, исходящие из вершины 1 (соответствует 1 строка матрицы А2):

(1,1,1); (1,4,1); (1,3,2); (1,4,2); (1,1,3); (1,3,3); (1,4,3); (1,1,4); (1,3,4).

Наши рекомендации