Дискретная математика (стр. 8 )

Теория графов

Глава 10. Графы: основные понятия

Граф – это совокупность не пустого множества точек V, называемых вершинами, и множества X отрезков прямых, соединяющих вершины и называемых рёбрами. Каждое ребро – это пара вида (v, w), где v и w – это вершины графа. Рёбра могут быть кратными и петлями:

Здесь две первых эквивалентных друг другу картинки показывают три кратных ребра между вершинами v и w, а третья – петлю у вершины u. Петли тоже могут быть кратными. Вершины v и w – это концы ребра, у петли концы совпадают.

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

В теории графов приняты следующие обозначения: n – число вершин графа (n > 0), m – число его рёбер, (v) – это степень вершины v. Для каждого псевдографа (мультиграфа, графа) сумма его степеней вершин равна удвоенному числу его рёбер, так как вклад каждого ребра в эту сумму равен двум:

= 2 m.

Обозначаем G(V, X) граф с вершинами из множества V и с рёбрами из множества X. Графы G1(V1,X1) и G2(V2,X2) изоморфны, если существует биективное (взаимно однозначное) отображение f, переводящее V1 в V2 и сохраняющее смежность. Другими словами, каждое ребро (v, w) переходит в ребро (f(v),f(w)). Изоморфные графы отличаются или лишь обозначением вершин, или даже они иначе нарисованы. Изоморфные графы – это одинаковые графы. Например, два изоморфных графа:

У изоморфных графов количества вершин, количества рёбер и наборы степеней вершин совпадают, но не наоборот. Например, существуют два не изоморфных друг другу графа с шестью вершинами (n

= 6), девятью рёбрами (m = 9) и набором степеней вершин: :

Здесь в каждом графе существует ровно две вершины степени два, но в левом графе они смежны, а в правом – нет. Поэтому эти два графа не изоморфны. Другой пример, существует два разных графа с n=5, m=6 и набором степеней вершин: , в левом графе вершины степени три смежны (имеют общее ребро), а в правом - нет:

При решении задач с графами лучше всего графы рисовать, чаще всего начиная с вершины большей степени. Некоторые примеры графов: N- это граф с n вершинами и без рёбер, или, другими словами, это n изолированных вершин. K- это полный граф на n вершинах (n > 1), в нём существуют все возможные рёбра. Число рёбер в полном графе равно (n (n-1))/2, так как существует n способов выбрать первый конец ребра и (n-1) способ выбрать второй его конец и при этом каждое ребро посчитано дважды. Полный граф на пяти вершинах с десятью рёбрами:

Граф называется регулярным (или однородным), если все вершины в нём имеют одну и ту же степень. Полный граф является регулярным. W - это колесо на n вершинах (n > 2), одна из которых – это центр колеса со степенью (n-1), а остальные вершины со степенью три находятся на его ободке. Колесо на семи вершинах:

C - цепь на n вершинах (n > 1), у которой две концевых вершины являются висячими, а все (n-2) промежуточные вершины имеют степень два.

В двудольном графе вершины разделяются на две доли (n=n1+n2 и n1>0, n2>0), а рёбра существуют только между вершинами из разных долей (в долях рёбер нет). Двудольный граф (как и обычный граф) может быть полным и не полным. В полном двудольном графе, который обозначается K, существуют все возможные ребра между вершинами из разных долей. Полный двудольный граф будет регулярным, если в нём n1 = n2. Число рёбер в полном двудольном графе равно n1n2. Полный двудольный граф (слева) и двудольный граф (справа) с долями, равными двум и трём вершинам:

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

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

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

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

Додекаэдр образован двенадцатью пятиугольниками и является платоновым регулярным графом степени три:

Маршрут в псевдографе – это последовательность, в которой чередуются вершины и рёбра, их соединяющие. Если в маршрут входят кратные рёбра, то они должны быть пронумерованы. Если в графе нет кратных рёбер, то маршрут можно составить из одних вершин. Число рёбер в маршруте называется его длиной. Незамкнутый маршрут, в котором все рёбра различны, называется цепью. Цепь, в которой все вершины различны, называется простой цепью. Ребро – это простая цепь длиной единица. Пример цепи (слева) и простой цепи (справа):

Замкнутый маршрут, в котором все рёбра различны, называется циклом. Цикл, в котором все вершины различны, называется простым циклом. Петля – это простой цикл длины единица. Кратные рёбра образуют простой цикл длины два. Пример цикла (слева) и простого цикла (справа):

 

 

В псевдографах (с петлями) минимальная длина простого цикла равна единице, в мультиграфах (с кратными рёбрами) минимальная длина простого цикла равна двум, а в графах – трём.

Если степени всех вершин графа больше единицы, то в графе существует хотя бы один цикл. Берём любую вершину, из неё выходят как минимум два ребра, выходим из этой вершины по любому из рёбер и попадаем в следующую вершину. У этой новой вершины степень как минимум два, выходим из неё по ребру, не совпадающему с тем, по которому в неё попали. Опять попадаем в новую вершину и так же выходим из неё по новому ребру. Поскольку число вершин в графе конечно, то рано или поздно попадём в вершину, в которой уже были, не обязательно это будет вершина, из которой мы начали маршрут, и получим цикл. Номерами указаны последовательные вершины пройденного при поиске цикла маршрута8 4):

Утверждение: в псевдографе из всякого цикла можно выделить простой. Доказательство индукцией по числу k – количеству рёбер в цикле. При k = 1 всякий цикл является простым. Пусть при k > 1 утверждение справедливо для циклов с длиной, меньшей k. Покажем его справедливость для цикла длиной k.

Если в цикле длиной k есть одинаковые вершины, то цикл делится на два подцикла, длина которых меньше k и для них справедливо индуктивное предположение. Берём любой из них и получаем из него простой. На практике, если в рассматриваемом подцикле опять есть одинаковые вершины, то опять делим его в свою очередь на подциклы. И так до тех пор, пока не получим простой цикл.

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

Матрица смежности графов

В настоящее время графы хранятся в компьютере в виде матриц смежности. В теории графов квадратные симметричные матрицы смежности размера nn обозначаются буквой A. Элемент A(j, k) матрицы смежности равен единице, если вершины j и k смежны и равен нулю в противном случае. Пример графа и его матрицы смежности:

Матрица смежности любого графа является булевой, то есть состоит только из нулей и единиц. У каждого ребра графа, соединяющего вершины j и k, в матрице смежности графа имеются соответствующие ему две единицы: A(j, k) = A(k, j) = 1. Степень j-й вершины графа равна сумме элементов его матрицы смежности A по j-й строке или по j-у столбцу.

Матрица смежности существует и для псевдографов, только она в общем случае не будет булевой. Её элементы будут равны кратности соответствующих им рёбер и удвоенной кратности соответствующих им петель. Пример псевдографа и его матрицы смежности:

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

Утверждение: элемент A(j, k) t-й степени матрицы смежности A (A) равен числу всех маршрутов длины t из вершины j в вершину k. Без доказательства.

Дополнением графа называется граф с теми же вершинами, но с рёбрами, которых нет в самом графе. Это как бы дополнение графа до полного графа на тех же вершинах. Дополнением полного графа на n вершинах являются n изолированных вершин. Сумма рёбер связного графа и его дополнения равна числу рёбер полного графа на тех же вершинах.

Граф называется самодополнительным, если он изоморфен (равен) своему дополнению. Существует один самодополнительный граф на четырёх вершинах – это цепь C:

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

Связность графов

Псевдограф называется связным, если для каждой пары его вершин существует маршрут, их соединяющий. Вершина графа j достижима из вершины k, если или j = k (как бы маршрут длиной ноль), или в графе существует маршрут, их соединяющий. Если граф не является связным, то он называется несвязным.

Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа. Проще говоря, это его максимальный подграф. В теории графов число компонент связности графа обозначают буквой p. Для связного графа p = 1, а у N (графа с n изолированными вершинами) p=n. Граф с тремя компонентами связности (p = 3):

В этом графе с тремя компонентами связности в первой компоненте три вершины: 1, 2 и 6; во второй – две: 3 и 7; в третьей три: 4, 5 и 8. Подграф этого графа, состоящий из вершин 1 и 2 и соединяющего их ребра, не является компонентой связности графа, так как является собственным подграфом его первой компоненты связности. Аналогично, если из третей компоненты связности графа убрать любое ребро, то полученный подграф не будет компонентой связности графа, несмотря на то, что вершины третьей компоненты остались все в полученном подграфе.

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

Пусть псевдограф G(V, X) имеет p компонент связности: G1(V1,X1), G2(V2,X2), …, Gp(Vp, Xp). Тогда:

1) множество вершин графа G – это объединение множеств вершин его компонент связности: V = V1V2…Vp, а множество рёбер графа G – это объединение множеств рёбер его компонент связности: X = X1X2…Xp;

2) любые две различные компоненты связности графа не имеют общих вершин и общих рёбер: VjVk = и XjXk = при jk;

3) число вершин графа равно сумме чисел вершин его компонент связности: n = n1 + n2 + … +np, а число рёбер графа равно сумме чисел рёбер его компонент связности: m = m1 + m2 + … + mp.

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

Лес – это граф без циклов. Дерево – это связный граф без циклов. Лес, таким образом, состоит из p деревьев. Простейшим деревом является цепь на n вершинах (n > 1). В дереве m=n-1, а в лесе m=n-p, так как каждое дерево леса отнимает единицу от числа вершин n. Лес является двудольным графом. Это видно, если рисовать лес по уровням:

Матрицей связности S графа называется квадратная симметричная матрица размера nn, в которой каждый элемент S= 1, если j-а вершина достижима из i-й вершины, и S=0 в противном случае. S = Esign(AA…A), где E – единичная квадратная матрица порядка n. Для любого графа главная диагональ его матрицы связности состоит из одних единиц.

Существует и другой метод получения матрицы связности графа. Это метод Уоршелла. В нём рассматривается последовательность булевых квадратных матриц B0, … , Bn порядка n. B0 = AE, а элемент Bt(j, k) матрицы Bt равен Bt`(j, k) (Bt`(j, t) & Bt`(t, k)), где t` = t-1. Тогда S = Bn.

Покажем, как работает метод на конкретном графе:

Матрицы B0, B2 и B4 для этого графа имеют вид:

Матрица B1 = B0, B3 = B2 и B5 = B4 = S. Матрица B1 получается из матрицы B0 добавлением маршрутов через первую вершину графа, но она является висячей вершиной и, значит, промежуточной вершиной маршрута быть не может. Матрица B2 получается из матрицы B1 добавлением маршрутов через вторую вершину графа. Маршруты из первой вершины в четвёртую и пятую идут через вторую вершину, что добавляет в матрицу B2 четыре единицы: B2(1,5), B2(5,1), B2(4,1) и B2(1,4), которых в матрице B1 не было. Аналогично маршрут из четвёртой вершины в пятую идёт через вторую вершину графа, что добавляет в матрицу B2 ещё две единицы: B2(4,5) и B2(5,4), которых в матрице B1 не было.

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

Маршрут из первой вершины в третью идёт через четвёртую вершину графа (маршрут: 1, 2, 4, 3), что добавляет в матрицу B4 по сравнению с матрицей B3 ещё две единицы: B4(1,3) и B4(3,1). Матрица B4 состоит из одних единиц, и пятая вершина графа никаких новых маршрутов прибавить не может. Как и для всякого связного графа, матрица S рассматриваемого графа состоит из одних единиц.

При построении матрицы B1 во внутренние вершины маршрутов добавляется первая вершина, при построении B2 – вторая, … , при построении Bn – последняя n-я вершина графа. В матрице B0 отражены только маршруты длиной ноль и единица, не имеющие промежуточных вершин. В матрице B1 появляется одна промежуточная вершина – это первая вершина графа. Отсюда в B1 отражены ещё по сравнению с матрицей B0 и маршруты длиной два через первую вершину.

В матрице B2 появляется ещё одна промежуточная вершина – это вторая вершина графа. Отсюда в B2 отражены ещё по сравнению с матрицей B1 и маршруты длиной два через вторую вершину, и маршруты длиной три через вторую и первую промежуточные вершины. В матрице B3 появляется ещё одна промежуточная вершина – это третья вершина графа. И так далее, пока на последнем n-м этапе при построении Bn промежуточными уже могут быть любые вершины графа.

Покажем на примере, как надо выделять компоненты связности не связного графа. Сначала надо получить матрицу связности графа. Пусть матрица связности имеет вид:

Возьмём первую вершину и рассмотрим соответствующую ей первую строку. В этой строке три единицы, что значит, что первая компонента связности содержит три вершины: первую, вторую и шестую, что соответствует единицам в первой строке. Заметим, что вторая и шестая строки этой матрицы связности S совпадают с первой строкой.

Возьмём теперь не попавшую в первую компоненту связности третью вершину и рассмотрим третью строку матрицы S. Рассматривать можно и столбцы симметричной матрицы S. В третьей строке две единицы, что значит, что вторая компонента связности содержит две вершины: третью и седьмую, что соответствует единицам в третьей строке. Соответственно третья и седьмая строки (и столбцы) этой матрицы S совпадают.

Оставшиеся три вершины (четвертая, пятая и восьмая) образуют третью компоненту связности графа, так как четвёртая, пятая и восьмая строки матрицы связности S имеют ровно по три единицы на соответствующих позициях. Выделим теперь из матрицы смежности A рассмотренного не связного графа матрицы смежности его трёх компонент связности (A1, A2 и A3 соответственно номерам компонент):

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

Глава 11. Орграфы: основные понятия

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

Симметричные пары дуг могут быть и кратными.

Аналогично графам, в орпсевдографе могут быть и кратные дуги, и петли. В ормультиграфе могут быть только кратные дуги. В орграфе, если это не оговаривается особо, нет ни петель, ни кратных дуг.

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

Стоком называется вершина орграфа, у которой нет исходящих из неё дуг, а у истока нет заходящих в него дуг:

Для орграфов приняты те же обозначения, что и для графов: n – это число вершин в орграфе (n0), а m – это число дуг в нём. В каждом орграфе суммы полустепеней исхода и захода всех вершин в нём равны m, так как вклад каждой дуги в каждую из сумм равен единице. Каждая дуга откуда-то исходит и куда-то заходит:

= = m.

Обозначаем D(V, X) орграф с вершинами из множества V и с дугами из множества X. Графы D1(V1,X1) и D2(V2,X2) изоморфны, если существует биективное (взаимно однозначное) отображение f, переводящее V1 в V2 и сохраняющее смежность. Другими словами, каждая дуга (v, w) переходит в дугу (f(v),f(w)).

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

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

Турнир может быть транзитивным. В транзитивном турнире для каждой тройки вершин v, u и w из того, что существуют дуги, направленные из вершины v в вершину u и из вершины u в вершину w, следует, что существует и дуга, направленная из вершины v в вершину w:

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

Число дуг в турнире равно числу рёбер в полном графе – n(n-1)/2. Число дуг в полном орграфе не меньше, чем число дуг в турнире, и может достигать удвоенного числа рёбер в полном графе - n(n-1). Если число дуг в полном орграфе равно n(n-1), то в нём каждая пара вершин связана симметричной парой дуг.

Путь в орграфе – это последовательность, в которой чередуются вершины и дуги, их соединяющие. Путь может идти только от начала дуги к её концу, против направления дуги путь идти не может. Если нет кратных дуг, то путь можно составить из одних вершин. Число дуг в пути называется его длиной. Незамкнутый путь, в котором все дуги различны, называется цепью. Цепь, в которой все вершины различны, называется простой цепью. Дуга – это простая орцепь длиной единица.

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

Если полустепени исхода всех вершин орграфа больше нуля, то в орграфе существует хотя бы один контур. Берём любую вершину, из неё выходит как минимум одна дуга, по этой дуге попадает в следующую вершину пути. Из этой новой вершины тоже исходит как минимум одна дуга, выходим по ней в следующую вершину пути. Опять попадаем в новую вершину и так же выходим из неё по новой дуге. Поскольку число вершин в орграфе конечно, то рано или поздно попадём в вершину, в которой уже были, не обязательно это будет вершина, из которой мы начали путь, и получим контур. Аналогичное рассуждение справедливо и в случае, если полустепени захода всех вершин орграфа больше нуля.