1сем Дагаев / mapks_type

МАПКС, 41 КС, Лекция 25. Типы графов

Типы графов

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

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

Это по сути граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке. Стоит отметить, что в данном примере не используется ни одной петли, то есть такого ребра, которое выходит из вершины и сразу же входит в нее, но петли могут встречаться в задачах.

Вот некоторые важные обозначения, используемые в теории графов:

G=(V, E), здесь G – граф, V – его вершины, а E – ребра;

|V| – порядок (число вершин);

|E| – размер графа (число рѐбер).

Внашем случае (рис. 1) |V|=5, |E|=10;

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

(рис. 2).

В ориентированных и неориентированных графах имеется понятие степени вершины. Степень вершины – это количество ребер, соединяющих ее с другими вершинами. Сумма всех степеней графа равна удвоенному количеству всех его ребер. Для рисунка 2 сумма всех степеней равна 20.

1

МАПКС, 41 КС, Лекция 25. Типы графов

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

Ориентированные графы имеют следующую форму записи: G=(V, A), где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G=(V, E, A), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

В графе на рисунке 3 одни дуги направленные [(e, a), (e, c), (a, b), (c, a), (d, b)],

другие – ненаправленные [(e, d), (e, b), (d, c)…].

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

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

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

Граф G = (X, A) называют полным, если для любой пары вершин хi и хj в X существует ребро (хi, хj) в неориентированном графе G=(X,A) т. е. для каждой пары вершин графа G должна существовать по крайней мере одна дуга, соединяющая их (рис.

1,а).

Граф G =(X, A) называется симметрическим, если в множестве дуг A для любой дуги (хi, хj) существует также противоположно ориентированная дуга (хj, хi) ( рис. 1,б).

2

МАПКС, 41 КС, Лекция 25. Типы графов

Рис. 1. а – полный граф; б – симметрический граф; в – антисимметрический граф; г

– полный симметрический;

Антисимметрическим называется такой граф, для которого справедливо следующее условие: если , то во множестве A нет противоположно

ориентированной дуги, т. е. ( (рис. 1,в). Очевидно, что в антисимметрическом графе нет петель.

В качестве примера можно рассмотреть граф, являющийся моделью некоторой группы людей: вершины графа интерпретируют людей, а дуги – их взаимоотношения. Так, если в графе дуга, нарисованная от вершины хi к вершине хj , означает, что хi является другом или родственником хj , тогда данный граф должен быть симметрическим. Если дуга, направленная от хi к хj , означает, что вершина хj подчинена вершине хi , то такой граф должен быть антисимметрическим.

Комбинируя определения полного и симметрического графов и полного и антисимметрического графов, получили следующие определения:

граф G =(X, A), в котором любая пара вершин (хi, хj) соединена двунаправленными дугами, называется полным симметрическим (рис. 1,г). Очевидно, что в полном симметрическом графе каждая вершина имеет петлю;

граф G =(X, A), имеющий для каждой пары вершин (хi, хj) только одну дугу, называется полным антисимметрическим или турниром.

Связный граф, не имеющий циклов, либо граф, в котором каждая пара вершин

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

котором полустепень захода каждой вершины, за исключением одной (например, вершины х1 ), равна 1, а полустепень захода вершины х1 (называют корнем этого дерева) равна 0 (рис. 2,б).

Граф G =(X, A), который может быть изображен на плоскости или сфере без пересечений называется планарным (рис. 3).

На рис. 4 показаны непланарные графы. Эти два графа играют важную роль в теории планарных графов и известны как графы Куратовского.

3

МАПКС, 41 КС, Лекция 25. Типы графов

Рис. 2. Граф типа “дерево”: а – неориентированное дерево, б – ориентированное дерево

Рис. 3. Планарный граф

Рис. 4. Непланарные графы

4

МАПКС, 41 КС, Лекция 25. Типы графов

Неориентированный граф G = (X, A) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Xа и Xb , что каждое ребро имеет один конец в Xа , а другой в Xb (рис. 5,а).

Ориентированный граф G называется двудольным, если его неориентированный двойник – двудольный граф (рис. 5,б,в).

Двудольный граф называют полным, если для любых двух вершин и существует ребро (хi,хj) в G=(X,A) (рис. 5,г).

Рис. 5. Двудольные графы: а, б, в – двудольные графы; г – полный двудольный граф

Для доказательства двудольности графа существует теорема.

Теорема о двудольности

Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство

1. Необходимость. Поскольку множество X разбивается на две части Xа и Xb , то

и .

Пусть существует цикл нечетной длины хi1 , хi2, ...,хi q , хi1 . Без потери общности

допустим, что . Согласно определению одна из двух следующих друг за другом вершин этого цикла должна принадлежать множеству Xа , а другая – множеству Xb

, тогда имеем: и т. д. Следовательно, , если k –

следует, что . Это противоречит исходному условию, поскольку

и вершина не может принадлежать одновременно как Xa , так и Xb . Для большей ясности можно рассмотреть цикл нечетной длины для графа,

изображенного на рис. 6:

5

МАПКС, 41 КС, Лекция 25. Типы графов

Рис. 6. Построение цикла

х1---х3--- х5--- х4--- х2--- х1 Xа Xb Xа Xb Xа Xb .

Поочередно помечая вершины, мы видим противоречие: вершина и согласно определению должна принадлежать Xb, следовательно, рассматриваемый граф не является двудольным.

2. Достаточность. Предположим, что в графе G не существует цикла нечетной длины. Выберем одну из вершин графа, например, хi, и пометим ее "+". Выполним итерационную процедуру.

Берем уже помеченную вершину хi и помечаем все вершины из множества Г+1(хi) знаком, противоположным тому, который присвоен вершине хi .

Будем продолжать эту операцию до тех пор, пока не будет сделано следующее:

1) все вершины не будут помечены, а знаки, приписанные им, согласованы (иными словами, любые две вершины, соединенные ребром, помечены противоположными знаками);

2) для каждой помеченной вершины хi все вершины из множества Г+1(хi) помечены, но существуют другие, еще не помеченные вершины;

3) некоторая вершина, например хik , которая была уже помечена каким-то знаком ( "+" или "–" ), может быть помечена теперь (со стороны другой вершины) знаком, противоположным приписанному вершине хik .

В случае 1 все вершины , помеченные знаком "+", отнесем к множеству Xa , а помеченные знаком "–" – к множеству Xb . Поскольку все ребра соединяют вершины, помеченные противополож-ными знаками, то граф является двудольным.

Рассмотрим граф на рис. 5б. Пометим знаком "+", например, вершину х1 . Найдем

отображение Г+(х1) = { х4, х5 }. Вершины х4 и х5 пометим знаком "–". Отображение Г+(х4, х5) = = { х2, х3 }, помечаем вершины х2 и х3 знаком "+". Г+(х2, х3) = = { х4, х5, х6 }. Оставшуюся непомеченной вершину х6 помечаем знаком "–". Таким образом, получили

два подмножества вершин Xa = { х1, х2, х3 } и Xb = { х4, х5, х6 } и показали, что рассматриваемый граф является двудольным.

Случай 2 означает, что между помеченной и непомеченной вершинами не существует дуги. Перейдем к неориентированному графу и повторим процедуру пометок знаками "+" и "–". Если остались непомеченные вершины, то это означает, что граф распадается на две или больше частей, и каждая из них может тогда рассматриваться отдельно. Итак, в конце приходим к случаю 1.

В графе на рис. 5в, пометки были начаты знаком "+" с вершины х 2 . Г+(х2) = { х4 }. Вершина х4 помечается знаком "–". Г+(х4) = { х3 }. Вершина х3 помечается знаком "+".

.

В графе остались непомеченные вершины, но если перейти к неориентированному двойнику этого графа, то процедура пометок легко выполняется и множество вершин разбивается на два подмножества Хa= { х1, х2, х3 } и Хb= { х4, х5, х6 }, тем самым исходный граф является двудольным.

6

МАПКС, 41 КС, Лекция 25. Типы графов

В случае 3 вершина хik должна быть помечена знаком "+" на некотором маршруте (например, М1), состоящем из вершин хi1, хi2, ..., хik ; причем знаки "+" и "–", приписываемые этим вершинам при движении по маршруту М1, должны образовывать чередующуюся последовательность. Например, для графа на рис. 6 маршрут М1 можно выбрать таким:

М1: х1 -> х3 -> х5 -> х4 -> х2. "+" "-" "+" "-" "+"

Аналогично знаком "-" вершина хik помечается вдоль некоторого маршрута М2 . Например,

М2: х1 -> х4 -> х6 -> х2. "+" "-" "+" "-"

Пусть x* – предпоследняя (последней является хik ) общая вершина маршрутов М1 и М2 . Если вершина x* помечена знаком "+", то участок от x* до хik маршрута М1 должен быть четным, а участок от x* до хik маршрута М2 должен быть нечетным. Если же вершина x* помечена знаком "-", то участок маршрута М1 будет нечетным, а маршрута М2 – четным. Следовательно, цикл, состоящий из участка маршрута М1 , от x* до хik , и соответствующего участка маршрута М2 , от хik до x* , имеет нечетную длину. Это противоречит предположению, что граф не содержит циклов нечетной длины, и, значит, случай 3 невозможен.

В рассматриваемом примере x* = х4 . В маршруте М1 длина участка от х4 до х2 равна 1, а в маршруте М2 длина участка от х4 до х2 равна 2, что в сумме составляет нечетное число, следовательно, граф содержит цикл нечетной длины и не является двудольным.

Вопросы:

1.Что называется графом?

2.Что называется степенью вершины?

3.Перечислите типы графов.

4.Опишите неориентированные графы.

5.Опишите ориентированные графы.

7