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

Ñ  Множества вершин связных компонент образуют разбиение множества вершин графа.

3.2.4  Подграфы

Граф G’(V’,E’) называется подграфом графа G(V,E): G’(V’,E’) Í G(V,E), если V’Í V и E’Í E, и каждое из ребер E’ инцидентно только вершинам из V’.

Если G’Í G и множества вершин этих графов не равны, как и множества ребер, то подграф G’ является собственным подграфом графа G (Прим. 3.10, б).

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

Ñ  Очевидно, что остов существует в каждом графе. Для его получения нужно удалить «лишние» ребра, разрушив циклы в каждой связной компоненте.

Остовный подграф для графа G можно построить не единственным образом. В общем, если (n,m)-граф G имеет k компонент связности, то для получения его остова из графа необходимо удалить (m–n+k) ребер.

  Пример 3.10  (4,6)-граф G (а), его подграфы (б, в), причем б) – собственный подграф; 2 различных каркаса (г, д). Удаление ребер для получения остовного подграфа: (m–n+k) = 6 – 4 + 1 = 3. Þ из исходного графа требуется удалить 3 ребра (так, чтобы сохранились все вершины исходного графа и не стало циклов).

а) б) в) г) д)

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

1.  Что такое степень вершины? Чем висячая вершина отличается от изолированной?

2.  Какой граф называется регулярным?

3.  Как связаны степень вершины и полустепень исхода, полустепень захода?

4.  Что такое маршрут? Чем отличается замкнутый маршрут от открытого?

5.  Какой маршрут называется цепью? Какая цепь является простой?

6.  Чем цикл отличается от пути? А от контура?

7.  Как определить длину маршрута? В чем она выражается?

8.  Что такое расстояние между вершинами?

9.  Что такое геодезическая? Как определяется диаметр графа?

10.  Какой граф называется связным? Как называются классы эквивалентности вершин графа по отношению связности?

11.  Может ли граф состоять из одних изолированных вершин и не иметь ребер? Сколько компонент связности имеет такой граф?

12.  В чем различие между сильной и слабой связностью орграфа?

13.  Что такое собственный подграф?

14.  Какой подграф называется каркасом?

3.3  Виды графов и операции над ними

3.3.1  Тривиальные и полные графы

Наиболее простое строение имеют пустые и полные графы.

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

Граф, состоящий из простого цикла с k вершинами, обозначается Ck. Например, C3 – треугольник, C4 – квадрат.

Граф с n вершинами называется полным, если любые две его вершины смежны. Такой граф обозначается Kn, он имеет максимально возможное число ребер, равное n×(n–1)/2.

  Пример 3.11 

Ñ  Очевидно, что в пустом графе все вершины изолированные, а в полном степень каждой вершины на 1 меньше порядка графа: deg(v)=n–1 "vÎV.

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

Утверждение:

Всякий полный граф является регулярным; обратное же не верно. Для подтверждения достаточно рассмотреть квадрат, который является регулярным графом (степени всех вершин одинаковы и равны 2), но не является полным.

Полный граф G(V,E) соответствует универсальному бинарному отношению E на множестве вершин V (т. е. "u,vÎV (u,v)ÎE – любые два элемента (вершины) связаны этим отношением).

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

Двудольный граф (или биграф, или четный граф) – это граф G(V,E) такой, что множество вершин разбито на два непересекающихся подмножества V1 и V2: V1ÈV2=V, V1ÇV2=Æ так, что любое ребро соединяет вершину из V1 с вершиной из V2. Тогда множества V1 и V2 называются долями графа G.

Если граф содержит все ребра, соединяющие множества V1 и V2, то он называется полным двудольным графом. Если |V1|=m и |V2|=n, то полный двудольный граф обозначается Km,n.

  Пример 3.12  На рисунке показан полный двудольный граф K3,3.

Теорема 3.2  Граф является двудольным тогда и только тогда, когда все его простые циклы имеют четную длину.

Двудольные графы удобны для представления бинарных отношений между элементами двух разных типов, например: множества {исполнители} и {виды работ}. Тогда отношением E может быть «данный исполнитель может выполнять данную работу».

3.3.3  Плоский (планарный) граф

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

Говорят, что плоский граф допускает правильную укладку на плоскости.

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

Любая правильная укладка связного графа порождает разбиение плоскости на отдельные области (грани). Такое разбиение называется плоской картой.

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

Для любой плоской карты имеет место формула Эйлера: n – m + r = 2, где n – число вершин, m – число ребер, r – число областей карты (включая внешнюю область).

  Пример 3.13  Полный двудольный граф K3,3. и полный граф K5 не являются плоскими.
Граф K4 является планарным: см. рисунок. 1,2,3 – его внутренние грани, 4 – внешняя грань.

3.3.4  Направленные орграфы и сети

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

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

  Пример 3.14  Граф на рисунке является сетью, вершина 1 – источником, а вершина 5 – стоком.

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

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

1.  Дополнением графа G1(V1,E1) называется граф G2(V2,E2), у которого множество вершин такое же, как у исходного графа, а множество ребер представляет собой дополнение до множества E1: V2=V1, E=`E1 =V1´V1\E1. Вершины графа G2 смежны только в том случае, когда они не смежны в исходном графе. Обозначение: `G1(V1,E1). Дополнение графов есть дополнение отношений.

  Пример 3.15  Дополнение к полному графу – пустой граф. Другой пример показан на рисунке.

2.  Удаление вершины v из графа G1(V1,E1) (при условии vÎV1): вершина v удаляется из множества V1, а из множества ребер удаляются ребра, инцидентные этой вершине: V = V1\{v}, E= E1\{e = (v1,v2) | v1 = v или v2 = v}. Обозначение: G = G1(V1,E1)–v.

  Пример 3.16  C3 – v = K2.

3.  Добавление вершины v в граф G1(V1,E1) (при условии vÏV1): во множество вершин добавляется вершина v: V = V1È{v}, E = E1. Обозначение: G = G1(V1,E1) + v.

4.  Удаление ребра e из графа G1(V1,E1) (при условии eÎE1): из множества ребер удаляется ребро e: V = V1, E= E1 \ {e}; его вершины сохраняются. Обозначение: G = G1(V1,E1)–e.

  Пример 3.17  K2 – e =`K2.

5.  Добавление ребра e в граф G1(V1,E1) (при условии eÏE1): во множество ребер добавляется ребро e: V = V1, E = E1È{e}. Обозначение: G = G1(V1,E1)+e.