Реферат: Орграфы, теория и применение

Применение орграфов

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

Бинарные отношения

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

Глава 2. ТЕОРИЯ ГРАФОВ

Граф G – совокупность двух множеств: вершин V и ребер E, между которыми определено отношение инцидентности. Каждое ребро e из E инцидентно ровно двум вершинам v', v'', которые оно соединяет. При этом вершина v' и ребро e называются инцидентными друг другу, а вершины v' и v'' называются смежными. Часто пишут v', v'' из G и e из G. Если |V(G)|=n, |E(G)|=m, то граф G есть (n,m) граф, где n – порядок графа, m – размер графа.

Определения

Ребро (v',v'') может быть ориентированным и иметь начало (v') и конец (v'') (дуга в орграфе).

Ребро (v,v) называется петлей (концевые вершины совпадают).

Граф, содержащий ориентированные ребра (дуги), называется орграфом.

Граф, не содержащий ориентированные ребра (дуги), называется неографом.

Ребра, инцидентные одной паре вершин, называются параллельными или кратными.

Граф с кратными ребрами называется мультиграфом.

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

Конечный граф – число вершин и ребер конечно.

Пустой граф – множество ребер пусто (число вершин может быть произвольным).

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

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

Если любые две вершины двудольного графа, входящие в разные доли, смежны, то граф называется полным двудольным . Обозначение для полного двудольного графа с n и m вершинами – Kn,m.

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

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

Следствие 2 из леммы о рукопожатиях. Число ребер в полном графе n(n-1)/2.

В орграфе две локальных степени вершины v: deg(v)+ и deg(v) – (число ребер с началом и концом в v)

Графы равны, если множества вершин и инцидентных им ребер совпадают.

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

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

Способы задания графов

Матрица инцидентности A. По вертикали указываются вершины, по горизонтали – ребра. Aij=1 если вершина i инцидентна ребру j, в противном случае aij=0. Для орграфа aij=-1 если из вершины i исходит ребро j, aij=1 если в вершину i входит ребро j. Если ребро – петля, то aij=2. Список ребер. В первом столбце ребра, во втором вершины им инцидентные. Матрица смежности – квадратная симметричная матрица. По горизонтали и вертикали – все вершины. Dij= число ребер, соединяющее вершины i,j. Матрица Кирхгофа: bij=-1, если вершины i и j смежны, bij=0 если вершины i и j не смежны, bii=deg(i). Сумма элементов в каждой строке и каждом столбце матрицы Кирхгофа равна 0.

Связность

Отношение вершин графа «существует маршрут, связывающий вершины» является отношением эквивалентности, задающее разбиение графа на компоненты связности. Индекс разбиения – k.

МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ

Чередующаяся последовательность v1, e1, v2, e2, … , en, vn+1 вершин и ребер графа такая, что ei =vivi+1 (i=1, n ), называется маршрутом, соединяющим вершины 1 и vn+1 (или (v1vn+1)-маршрутом). Очевидно, что для задания маршрута в графе достаточно задать последовательность v1, v2, …, vn+1. его вершин, либо последовательность e1, e2,… , en его ребер.

Вершина v называется достижимой из вершины u, если существует (u, v)-маршрут. Любая вершина считается достижимой из себя самой.

Маршрут называется цепью, если все его ребра различны, и простой цепью, если все его вершины, кроме, возможно, крайних, различны. Маршрут (1) называется циклическим, если v1=vn+1. Циклическая цепь называется циклом, а циклическая простая цепь – простым циклом. Число ребер в маршруте называется его длиной. Цикл длины 3 часто называют треугольником. Длина всякого цикла не менее трех, если речь идет о простом графе, поскольку в таком графе нет петель и кратных ребер. Минимальная из длин циклов графа называется его обхватом.

Маршрут – последовательность ребер, в которых каждые два соседних ребра имеют общую вершину.

Маршрут, в котором начало и конец совпадают – циклический.

Маршрут в неографе, в котором все ребра разные – цепь.

Маршрут в орграфе, в котором все дуги разные – путь.

Путь, в котором начало и конец совпадают – контур.

Цепь с неповторяющимися вершинами – простая.

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

Вершины связанные, если существует маршрут из одной вершины в другую.

Связанный граф – если все его вершины связаны. Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)-маршрут.

Свойства маршрутов, цепей и циклов:

1) Всякий незамкнутый (u, v)-маршрут, содержит в себе простую (u, v)-цепь. В частности, любая (u, v)-цепь, содержит в себе простую (u, v)-цепь. Причем, если (u, v)-маршрут содержит в себе вершину w (w?u и w?v), то в общем случае, простая (u, v)-цепь может не содержать в себе вершину w.

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

3) Всякая непростая (u, v)-цепь, может быть разбита на простую (u, v)-цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.

4) Для любых трех вершин u, w, v из существования (u, w)-цепи их и (w, v)-цепи, следует существование (u, v)-цепи. Причем может не существовать (u, v)-цепи, содержащей вершину w.

5) Объединение двух несовпадающих простых (u, v)-цепей содержит простой цикл.

6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.

Если два графа изоморфны:

1) то они одного порядка;

2) у них одинаковое количество ребер;

3) для произвольного i,0?i?n-1, (n – порядок графов) количество вершин степени i, у обоих графов одинаковое;

4) у них совпадают обхваты;

5) у них одинаковое количество простых циклов минимальной длины (по количеству ребер).

Число ребер маршрута – его длина. Эйлеров цикл – цикл графа, содержащий все его ребра. Эйлеров граф – граф, имеющий Эйлеров цикл.

Теорема. Мультиграф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин нечетной степени равно 0 или 2. Гамильтонов цикл – простой цикл, проходящий через все вершины.

ОРИЕНТИРОВАННЫЙ МАРШРУТ ДЛИНЫ k в орграфе из v в w в орграфе G=(V,E) – последовательность дуг вида (v,w1), (w1,w2), (w2,w3), …, (wk-1,w), т.е. конец каждой дуги, кроме последней, совпадает с началом следующей. Для упрощения маршрут удобно представлять последовательностью вершин, которые его представляют, однако следует помнить об одинаковом направлении дуг, входящих в маршрут: v, w1, w2, w3, …, wk-1,w.

ОРИЕНТИРОВАННАЯ ЦЕПЬ (ПУТЬ) – это ориентированный маршрут, в котором все дуги различны.

Маршрут называется ЦИКЛИЧЕСКИМ, если его начало и конец совпадают.

Циклический путь называется КОНТУРОМ.

Вершина w ДОСТИЖИМА из v, если существует (v,w) – путь. Орграф называется связным, если существуют пути для всех пар различных вершин графа. Матрица связи, связности, достижимости C=A(R*) определяется аналогично графам. Заметим, однако, что для орграфов отношение R* НЕ ЯВЛЯЕТСЯ ОТНОШЕНИЕМ ЭКВИВАЛЕНТНОСТИ на V и, следовательно, не осуществляет разбиения V!

Пусть «D – множество всех орграфов, а «G – множество всех графов.

Мы можем определить отображение «F: «D è «G следующим образом.

Пусть G=(V,E) in «D. Тогда множество вершин F(G) in «G совпадает с V, а множество дуг F(G) определяется применением следующих операций на E:

a) удаляются все петли из Е;

б) (v,w) заменяются на [v,w] для всех (v,w) in E.

Тогда F(G) является графом, СВЯЗАННЫМ с орграфом G.

Для орграфов понятие связности является более содержательным, чем для графов. Различают три важных типа связности орграфа:

а) G СИЛЬНО СВЯЗНЫЙ, если для каждой пары различных вершин v,w in V существует маршрут из v в w и обратно.

Б) G ОДНОСТОРОННЕ СВЯЗНЫЙ, если для каждой пары различных вершин v, w in V существует маршрут из v в w или обратно.

В) G СЛАБО СВЯЗНЫЙ, если граф F(G) связный;

Очевидно, что справедливо следование:

G сильно связный è G односторонне связный è G слабо связный.

В)+àv2ß+ б)+àv2à+ а)+àv2à+

 v1 v3 v1 v3 v1ß--- v3

В терминах матрицы связности C=A(R*) орграф G сильно связный тогда и только тогда, когда Cij=1 для всех I,j in Nn; G односторонне связный тогда и только тогда, когда Cij=1 или Cji=1 для всех I,j in Nn.

Страницы: 1, 2, 3, 4, 5, 6