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

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

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

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

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

Обозначим вершины v ₁, v ₂, v ₃, ¼, а ребра e ₁, e ₂, e ₃, ¼. Вершины v_i и v_j, определяющие ребро e_k, называются концевыми вершинами ребра e_k =(v_i, v_j), а в случае орграфа – началом и концом дуги e_k соответственно. Говорят также, что ребро e_k (дуга) инцидентно вершинам v_i, v_j или, что вершины v_i, v_j инцидентны ребру (дуге) e_k. Такие вершины называют смежными. Ребра называют смежными в случае, когда они имеют общую концевую вершину. Например, e_k =(v_i, v_j) и e_m =(v_i, v_l) – смежные ребра.

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

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

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

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

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

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

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

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

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

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

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

На рисунке 12 изображен смешанный граф с вершинами v ₁, v ₂,¼, v ₆, ребрами e ₁, e ₂, e ₃, e ₅ и дугой e ₄. Смежные вершины v ₁, v ₂, инциденты ребру e ₁. Вершины v ₁, v ₃, инциденты параллельным ребрам e ₂ и e ₃. Вершине v ₄ инциденты петля e ₅ и дуга e ₄, причем v ₄ является началом дуги e ₄, а v ₅ – концом этой дуги. Степень вершины v ₁ равна 3, вершины v ₂ – 1, вершины v ₃ – 2, вершины v ₄ – 3, вершины v ₅ – 1, вершины v ₆ – 0. Таким образом, вершины v ₂ и v ₅ – висячие, а вершина v ₆ – изолированная. В случае дуги e ₄ точнее было бы говорить о полустепенях исхода и захода вершин v ₄ и v ₅, а именно: полустепень исхода вершины v ₄ равна 3, вершины v ₅ – 0, полустепень захода вершины v ₄ равна 2, вершины v ₅ – 1.

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

Граф задают перечислением элементов множества вершин и множества ребер. Для графа, изображенного на рисунке 12, эти множества: V ={ v ₁, v ₂, v ₃, v ₄, v ₅, v ₆} и Е ={ e ₁, e ₂, e ₃, e ₄, e ₅}, где e ₁=(v ₁, v ₂), e ₂=(v ₁, v ₃), e ₃=(v ₁, v ₃), e ₄=(v ₄, v ₅), и e ₅=(v ₄, v ₄).

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

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

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

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

		e ₁	e ₂	e ₃	e ₄	e ₅
	v ₁
	v ₂
I=	v ₃
	v ₄
	v ₅				-1
	v ₆

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

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

		v ₁	v ₂	v ₃	v ₄	v ₅	v ₆
	v ₁
	v ₂
S=	v ₃
	v ₄
	v ₅
	v ₆

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

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

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

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

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

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

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

для вершин:

для ребер:

Подграфы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

9) Стягивание ребра – ребро удаляется, а его концевые вершины отождествляются. На рисунке 23 последовательно стягиваются ребра е ₁, е ₃, е ₂.