Определение ориентированного графа.

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

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

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

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

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

Оля

Таня Наташа

чтобы всегда можно было сделать выбор, иначе необходимо пересмотреть систему предпочтений.

Одностороннее движение.

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

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

На языке теории графов формулируется следующим образом: при каком условии ребра графа G можно ориентировать так, чтобы для любой пары его вершин нашлась соединяющая их ориентированная цепь?

Ясно, что каждый такой граф должен быть связным, однако этого недостаточно.

Ребро Е = (А,В) будем называть связывающим ребром, или перешейком, если оно является единственным путем от А к В (или обратно).

Свюзывающее ребро делит все вершины графа на два множества: те, в которые можно прийти из А, не проходя по ребру Е, и те, в которые можно прийти из В, не проходя по Е. Граф в этом случае состоит из двух частей G₁ и G₂ соединенных только ребром Е ( рис. a и a+1).

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

Если ребро Е_i = (А_i, В_i) не является связывающим, то найдется другой путь, соединяющий А_i и В_i и не проходящий по Е_i. Поэтому такое ребро будем называть циклическим ребром.

рис.2 Связывающее рис. 2+1 Конечное (связывающее) рис.2+2 Циклическое

Ребро ребро

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

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

Мы можем доказать эту теорему, указав спосмоб соответствующего ориентирования графа. Выберем в G произвольное ребро Е = (А,В). Если Е - связывающее ребро, оно останется двухсторонним, и тогда можно будет перейти от А к В и обратно (рис.2+3).

рис.2+3 рис. 2+4

Если Е - циклическое ребро, то оно входит в некоторый цикл С, на котором можно установить циклическую ориентацию (рис.2+4).

Предположим, что мы уже ориентировали некоторую часть Н графа G , так, что из любой вершины графа Н можно пройти в любую другую его вершину с соблюдением правил одностороннего движения. Так как граф G является связным, то либо Н совпадает со всем графом G, либо найдется ребро Е= (А,В), которое не принадлежит Н, но одна из его вершин, скажем А, принадлежит Н.

Если Е - связывающее ребро АВ, то оно останется двухсторонним. Тогда для любой вершины X графа Н можно найти ориентированную цепь R, соединяющую Х с А, а значит (через ребро Е) , и с В. Обратно от вершины В через ребро Е можно перейти к А, а затем - по ориентировочной цепи Z - от А к Х(рис a+5). Присоединяя Е к H, мы получим уже большую часть графа G, обладающую требуемым свойствам. Если же ребро Е= (А,В) является циклическим, оно принадлежит некоторому циклу С. Мы установили направление на С от А до В и далее вдоль С до первой вершины D из С, принадлежащей Н (рис. a+6).

рис. a+5 рис. a+6

Все эти ребра присоединим к Н. Пусть Х - произвольная вершина из Н, а У - любая вершина из С; можно найти ориентированную цепь R, принадлежащую Н и соединяющую Х с А, а затем вдоль С пройти к вершине У из С. Обратно, от У можно пройти вдоль С к вершине D, а от нее - принадлежащей Н ориентированной цепью Z - от D к Х. Поэтому ориентированный граф, полученный добавлением к Н указанных ребер цикла С, также удовлетворяет требуемым условиям. Продолжая этот процесс, мы в конце концов ориентируем требуемым образом исходный граф G.

Степени вершин .

Для ориентированных графов мы имеем в каждой вершине число р(А) выходящих и число р^*(А) входящих ребер. Общее число ребер равно :

N = р(А₁) + р(А₂) +... + р(А_n) = p^*(A₁)+p^*(A₂)+...+p_*(A_n)

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

р(А) = р^*(А) = r

Упражнение

Постройте однородные ориентированные графы степени r = 2 с числом вершин n = 2,6,7,8.

ОТНОШЕНИЯ.

Отношения и графы.

Всякая математическая система имеет дело с множеством каких-то объектов, или элементов. (Приметы: алгебра, геометрия)

Для того чтобы построить математическую теорию, нам нужны не только сами эти элементы, но также и отношения между ними. ( Примеры: для чисел а > в; в геометрии -равенство треугольников, // прямых; в теории множеств - равенство и включения множеств.)

Все эти отношения касаются двух объектов, поэтому они называются бинарными отношениями, или просто отношениями, имеются и другие типы отношений, например тернарные отношения, касающиеся трех объектов. (Например, точка А лежит между точками В и С ).

Введем общее определение бинарного отношения R : аRв - в находится в отношении R к а.

Например, отношение а > в означает, что в принадлежит множеству всех чисел, меньших а

Фактически, каждый ориентированный граф G определяет некоторое отношение в множестве его вершин. Это отношение можно записать в виде : аGв. Оно означает, что на графе имеется ориентированное ребро, идущее от а к в.

Специальные условия.

Пусть дано некоторое отношение R. Если элемент а находится в отношении R сам с собой, то ему соответствует петля в графе

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

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

Для каждого отношения R можно определить обратное отношение R^*, считая, что аR^*в тогда и только тогда, когда аRв.

Из определения обратного отношения видно, что если на графе G, соответствующем R, имеется ребро (а,в), то на графе G^*, соответствующем R^*, должно быть ребро (в,а). Иными словами, граф G^* обратным для G, т.е. графом с теми же ребрами, что и G, но противоположно ориентированными.

Отношение называется симметрическим, если из аRв следует вRа.

Симметрическому отношению соответствует граф с неориентированными ребрами; обратно, граф с неориентированными ребрами определяет некоторое симметрическое отношение.

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

Отношение R транзитивно, если из двух условий аRв и вRс следует, что аRc.

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

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

Отношения эквивалентности.

Отношение эквивалентности, обычно обозначаемое символом ~ , характеризуется следующими тремя свойствами:

1). Рефлексивностью: а ~ а;

2). Симметричностью: из а ~ в Þ в ~ а;

3). Транзитивностью: из а ~ в и в ~ с Þ а ~ с.

Фактически отношение эквивалентности - обобщение свойства равенства.

Отношение эквивалентности вводит в множестве вершин разбиение на непересекающиеся классы эквивалентности.

Пусть В_i - множество вершин графа эквивалентности G, эквивалентных вершине i. Тогда все вершины, принадлежащие В_i, соединены между собой ребрами, т.е. В_i - полный граф G_i. В каждой вершине такого графа-петля.Граф G распадается на множество связных компонент G_i.

Пример:

Частичная упорядоченность.

Отношение частичной упорядоченности - это (на примере множеств):

1). Рефлексивность: А Ê А

2). Транзитивность: если А Ê В и В Ê С Þ А Ê С

3). Тождественность: если А Ê В и В Ê АÞ А = В

Отношения строгого включения -

1). Антирефлексивность: А ÉА никогда не имеет места;

2). Транзитивность: если А É В и В É С , то А É С

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

Условие полноты. Для любых двух несовпадающих элементов в и а всегда выполнено одно из двух соотношений а>в или в>а.

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

ПЛОСКИЕ ГРАФЫ.

Условия для плоских графов.

Граф Куратовского К_3,3

Граф задача о трех домах и трех колодцах

Граф Куратовского К₅

Эти два графа - НЕ ПЛОСКИЕ !

Расширение графа - на некоторые ребра поставили новые вершины, так что эти ребра

стали элементарными цепями, состоящими из нескольких ребер.

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

Теорема Куратовсого

Для того чтобы граф был плоским, необходимо и достаточно, чтобы он не содержал внутри себя никакого графа, который можно было сжать до графа К_3,3 или графа К₅.

ФОРМУЛА ЭЙЛЕРА

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

Из определения многоугольных графов следует, что они связны. Потребуем также, чтобы ни один многоугольник не лежал внутри другого. Граничные ребра каждого такого многоугольника образуют цикл, иногда называемый минимальным циклом. Часть плоскости, заключенная внутри многоугольника, называется гранью графа. На графе имеется и максимальный цикл С₁, окружающий весь граф со всеми его гранями. Будем рассматривать часть плоскости, лежащую вне С₁, тоже как грань графа с границей С₁ - бесконечная грань F_¥.

Обозначим через

в, р, г

число вершин, ребер и граней пространственного многоугольника..

Теорема Эйлера

в - р + г = 2

Доказательство: Формула очевидна для многоугольника, имеющего n ребер. Действительно, n вершин и n ребер, а также две грани F₁ F_¥

Предположим, что формула верна для графа с г гранями. Докажем, что она будет верна и для графа с (г + 1) гранью (метод математической индукции).

Добавим новую грань к графу с г гранями, проводя по грани F_¥ некоторую элементарную цепь, соединяющую две вершины максимальног графа G. Если эта дуга имеет г ребер, то нам придется бобавить г - 1 новую вершину и одну новую грань. Но тогда

в’ - р’ + г’ = (в + г - 1) - (р + г) + (г + 1) = в - р + г (=2!)

по предположению индукции.

Матричные представления.

1. Матрица инциденций А.

а). Для неориентированного графа матрица инциденций представляет собой матрицу, строки которой соответствуют вершинам, а столбцы - ребрам. Элемент матрицы равен 1, если вершина инцидентна ребру. В противном случае элемент матрицы принимает значение 0.

б). Для ориентированного графа элемент матрицы инциденций равен +1, когда вершина, инцидентная дуге, является начальной вершиной дуги (т.е. дуга исходит из этой вершины). Элемент равен -1, когда дуга входит в вершину. Если вершина не инцидентна дуге, то элемент матрицы равен 0.

2. Матрица циклов С.

а). Для неориентированного графа строки матрицы циклов соответствуют простым циклам графа, а столбцы - его ребрам. Элемент матрицы a_ij=1, если цикл С_i содержит ребро e_j. В противном случае a_ij=0.

б). Для ориентированного графа a_ij=1, -1 или 0 в зависимости от того, одинакова или противоположна ориентация цикла С_i и дуги e_j или же данный цикл вообще не содержит дуги e_j.

3. Матрица смежности вершин (или просто матрица смежности) V представляет собой матрицу, строки и столбцы которой соответствуют вершинам, а элемент матрицы a_ij в случае неориентированного графа равен числу ребер, соединяющих вершины i и j. Для ориентированного графа элемент a_ij равен числу ребер, направленных от вершины i к вершине j.

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

1).Ранг (максимальное число линейно-независимых столбцов) матрицы инциденций А связного графа (ориентированного и неориентированного) с n вершинами равен (n-1).

2). Ранг матрицы циклов С связного графа с m ребрами и n вершинами равен (m-n+1).

Пример использования матрицы смежности.

Следующее отображение показывает, что графы G₁ и G₂ изоморфны

G1 G2

1 -> 1

2 -> 3

3 -> 2

4 -> 5

5 -> 4

6 -> 6

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

A₂=PA₁P', где

Р = , или p_ij=d_p(i),j (символ Кронекера)

и Р' - транспонированная матрица.

Нахождение матрицы Р может быть нелегким делом.

Изоморфность G₁ и G₂ означает, что А₁ и А₂ имеют одинаковые собственные значения. Однако это условие не является достаточным (пример внизу).

l=±2, 0, 0, 0