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

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

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

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