Глава 3 Элементы теории графов (стр. 4 )

6.  Отождествление вершин v1,v2 графа G1(V1,E1): замена этой пары новой вершиной v, причем все ребра, которые вели в удаленные вершины, заменяются ребрами, ведущими в v. Если эти вершины были смежными, то их отождествление называется стягиванием ребра.

  Пример 3.18  (4,4)-граф после стягивания ребра превратился в K2.

7.  Стягивание подграфа А графа G1(V1,E1) (при условии AÌV1): из множества вершин удаляется множество A и заменяется новой вершиной v, все ребра, которые вели в вершины из А, заменяются ребрами, ведущими в v. V = V1 \ A È {v}, E= E1 \ {e = (u,v) | uÎA или vΠA}È{e = (u,v) | uÎГ(A)\A}. Обозначение: G = G1(V1,E1)/A.

  Пример 3.19  K4 / C3 =K2.

8.  Подразбиение ребра графа G1(V1,E1): удаление ребра и добавление новой вершины, которая соединяется ребром с каждой вершиной удаленного ребра.

9.  Размножение вершины v графа G1(V1,E1) (при условии vÎV1, v’ÏV1): во множество вершин добавляется вершина v’, во множество ребер – ребра, соединяющие новую вершину v’ с вершиной v и со всеми смежными с ней вершинами. V = V1 È {v’}, E = E1 È {(v,v’)} È  {e = (u,v’) | uÎГ+(v)}. Обозначение: G = G1(V1,E1)­v.

  Пример 3.20  K2­v =C3; C3­v =K4 …

10.  Объединением графов G1(V1,E1) и G2(V2,E2) (при условии, что их множества вершин, как и множества ребер, не пересекались) называется граф G(V, E), в котором V = V1ÈV2, E = E1ÈE2. Обозначение: G = G1ÈG2.

  Пример 3.21  `K3,3.= C3ÈC3. Любой граф является объединением своих компонент связности.

11.  Соединением графов G1(V1,E1) и G2(V2,E2) (также при условии, что их множества вершин и множества ребер не пересекались) называется граф G(V, E), в котором V = V1ÈV2, E= E1ÈE2È{e=(v1,v2) | v1ΠV1, v2ΠV2}. Иными словами, строится объединение графов и добавляются ребра, соединяющие графы G1(V1,E1) и G2(V2,E2). Обозначение: G = G1+G2.

  Пример 3.22  Km, n.=`Km +`Kn.

12.  Произведением графов G1(V1,E1) и G2(V2,E2) (также при условии, что их множества вершин и множества ребер не пересекались) называется граф G(V, E). В нем V = V1×V2, и вершины (u1,u2) и (v1,v2) смежны только в том случае, если либо u1=v1 и u2 смежна с v2, либо u2=v2 и u1 смежна с v1. Обозначение: G = G1×G2.

  Пример 3.23 

 

Операции над графами могут использоваться для построения графов с заданными свойствами.

3.3.6  Деревья

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

Дерево – это связный граф без циклов. Несколько деревьев (или несвязный граф без циклов) составляют лес. Таким образом, дерево является компонентой связности леса.

Свойства дерева:

1.  Любые две вершины в дереве связаны единственной простой цепью.

2.  При удалении любого ребра дерева нарушается его связность.

3.  Число вершин в дереве на единицу больше числа ребер.

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

1.  Существует единственный узел, у которого полустепень захода равна нулю – корень дерева.

2.  Полустепень захода всех остальных узлов равна 1.

3.  Каждый узел достижим из корня.

4.  Узлы дерева с нулевой полустепенью исхода принято называть листьями.

  Пример 3.24  Свободные (а) и ориентированные (б) деревья с 4 узлами.
а) б)

3.3.7  Контрольные вопросы

1.  Какой граф является пустым? Чем он отличается от тривиального?

2.  Что означает обозначение C3? Чем этот граф отличается от K3? А чем различаются C4 и K4?

3.  Верно ли, что любой полный граф является регулярным?

4.  Какой граф является двудольным? Чем отличается полный двудольный граф? Какой граф обозначается K2,4.?

5.  Дайте определение планарного графа.

6.  Как определить число граней планарного графа?

7.  Какой орграф является направленным графом?

8.  Какой граф называется сетью?

9.  Какой граф является дополнением к пустому графу?

10.  Чем отличается удаление вершины от удаления ребра?

11.  В чем различие операций стягивания ребра и отождествления вершин?

12.  Чем отличается соединение графов от их объединения?

13.  В каких деревьях существуют корень и листья?

14.  Сколько существует различных неизоморфных деревьев с 5 вершинами?

3.4  Представление графов в ЭВМ

3.4.1  Требования к представлению графов

Чтобы задать граф, нужно каким-либо способом описать множество его вершин, множество его ребер, а также указать, какие вершины и ребра инцидентны (или смежны), т. е. задать отношение инцидентности (смежности).

Рассмотрим несколько способов представления графа в ЭВМ. Они различаются объемом занимаемой памяти и скоростью выполнения операций над графами. Представление выбирается по потребностям конкретной задачи.

Напоминание: число вершин графа обозначаем через n, а число ребер – через m. Характеристика M(n,m), приведенная для каждого представления, означает требуемый для него объем памяти.

Ñ  Указанные представления пригодны для графов и орграфов, а после некоторой модификации – для псевдографов, мультиграфов и гиперграфов.

Все представления будем иллюстрировать на конкретных примерах графа G и орграфа D (см. рисунок.).

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

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

Матрица смежности A(G’) графа (орграфа) – это квадратная матрица размера n´n, у которой для любых i,j Î{1,2,…,n} элемент в i-й строке и j-м столбце равен 1, если i-я и j-я вершины соединены ребром (дугой с началом в вершине i), и равен 0 в противном случае.

Память M(n,m)=O(n2).

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

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

  Пример 3.25  Матрицы смежности для заданных графа G и орграфа D

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

  Пример 3.26  Псевдограф, изображенный на рисунке, имеет матрицу смежности следующего вида:

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

Другой способ задать граф – определить матрицу инцидентности (или инциденций) I(G), имеющую n строк и m столбцов, элементы которой задаются следующим образом:

Для ориентированного графа:

  Пример 3.27  Матрицы инцидентности для заданных графа G и орграфа D