 |
Дополнительные определения
|
|
|
|
Направленный ациклический граф или гамак есть бесконтурный орграф. (Направленный ациклический граф — случай направленного графа, в котором отсутствуют направленные циклы, то есть пути, начинающиеся и кончающиеся в одной и той же вершине. Направленный ациклический граф является обобщением дерева (точнее, их объединения — леса)).
Ориентированный граф, полученный из заданного сменой направления ребер на противоположное, называется обратным.
Изображение и свойства всех орграфов с тремя узлами. Легенда: С – слабый, ОС – односторонний, СС – сильный, Н – является направленным графом, Г – является гамаком, Т – является турниром.
| 0 дуг | 1 дуга | 2 дуги | 3 дуги | 4 дуги | 5 дуг | 6 дуг |
пустой, Н, Г
| 
Н, Г
| 
| 
ОС
| 
CC
| 
CC
| 
полный, CC
|
ОС, Н, Г
| 
CC, Н, Т
| 
CC
| ||||
C, Н, Г
| 
ОС, Н, Г, Т
| 
ОС
| ||||
C, Н, Г
| 
ОС
| 
ОС
|
Применение орграфов
Орграфы широко применяются в программировании как способ описания систем со сложными связями. К примеру, одна из основных структур, используемых при разработке компиляторов и вообще для представления компьютерных программ — граф потоков данных.
Бинарные отношения
Бинарное отношение над конечным носителем может быть представлено в виде орграфа. Простым орграфом представимы антирефлексивные отношения, в общем случае требуется орграф с петлями. Если отношение симметрично, то его можно представить неориентированным графом, а орграф отношения делимости. Если антисимметрично, то направленным графом. (В математике бинарным отношением называется любое множество упорядоченных пар).
Глава 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.
Утверждение
Орграф является сильносвязным тогда и только тогда, когда в нем есть остовный циклический маршрут.
Если G=(V,E) – орграф, то можно разбить V путем определения отношения эквивалентности RO следующим образом: vROw, если v=w или существуют маршруты из v в w и обратно. Если {Vi: I in Np} – разбиение V и {Ei: I in Np, а Ei=(Vi*Vi) П E} являются соответствующими множествами дуг, то подграфы Gi=(Vi,Ei), I in Np называются СИЛЬНО СВЯЗНЫМИ КОМПОНЕНТАМИ G.
|
|
|
Очевидно, что RO<=R* и A(RO) может быть определено из A(R*) как A(RO)ij=A(R*)ij & A(R*)ji (& - символ операции конъюнкции); граф G связный тогда и только тогда, когда G имеет только одну сильно связную компоненту, т.е. если p=1.
### v1-----àv2 |1 1 1 1| |1 0 0 0|
| | |0 1 1 0| |0 1 0 0|
| | A(R*)=|0 0 1 0| A(RO)=|0 0 1 0|
v v |0 0 1 1| |0 0 0 1|
v4-----àv3 p=4
Таким образом, Gi=({vi}, Ф), I in N4, являются сильно связными компонентами заданного графа.
Путь (ориентированная цепь), содержащий все дуги орграфа, называется эйлеровым. Связный орграф называется ЭЙЛЕРОВЫМ, если в нем есть замкнутый эйлеров путь.
Теорема. Связный орграф G содержит открытый эйлеров путь тогда и только тогда, когда в нем есть две такие вершины v1, v2, что
delta+(v1)=delta-(v1)+1, delta+(v2)=delta-(v2)-1, и
delta+(v)=delta-(v) для любой вершины v, отличной от v1 и v2.
Контур (замкнутый путь) орграфа G называется ГАМИЛЬТОНОВЫМ, если он содержит все вершины орграфа G. ГАМИЛЬТОНОВ ГРАФ – это орграф, имеющий гамильтонов контур.
Распознавание гамильтоновости орграфов и построение гамильтоновых контуров так же сложны, как и для неориентированных графов. Рассмотрим одно из достаточных условий гамильтоновости орграфа.
Теорема (Мейниэл, 1973). Пусть G – сильносвязный орграф порядка n>1 без петель и параллельных дуг. Если для любой пары v и w его несовпадающих несмежных вершин справедливо неравенство
delta(v)+delta(w)>=2*n-1,
то в G есть гамильтонов контур.
Пусть G=(V,E) – АЦИКЛИЧЕСКИЙ ОРГРАФ. Вершину v in V называют ЛИСТОМ, если delta+(v)=0. Если (v,w) in E, то v является НЕПОСРЕДСТВЕННЫМ ПРЕДКОМ w, а w – НЕПОСРЕДСТВЕННЫМ ПОТОМКОМ v. Если существует маршрут из v в w, то говорят, что v является ПРЕДКОМ w, а w – ПОТОМКОМ v. Эти понятия не имеют смысла для графов, имеющих циклы, так как в этом случае вершины в цикле являлись бы потомками и предками самих себя!
+ß------v1-----à+ v4
v2<-----------------v3----------->v5<---------v6
Из вершин v2, v4, v5 дуги не выходят (листья графа), v1 является предком v5, v5 является потомком v1 и прямым потомком v3 и т.д.
Существует тесная связь между ациклическими графами и частично упорядоченными отношениями. Частичные порядки будут основаны скорее на отношении <, чем на отношении <=, и, следовательно, являются нерефлексивными и транзитивными.
Утверждения:
а) Пусть G=(V,E) - а–иклический орграф и отношение < определяется следующим образом: v<w, если v является предком w. Тогда отношение < является частичным отношением порядка на V.
б) Пусть отношение < является частичным отношением порядка на конечном множестве V. Тогда, если E={(v,w): v<w}, то пара G=(V,E) является ациклическим графом.
ОРИЕНТИРОВАННОЕ ДЕРЕВО T=(V,E) - э–о ациклический орграф, в котором одна вершина vr in V не имеет предков и называется КОРНЕМ, а каждая другая вершина имеет ровно одного непосредственного предка. Корень соединяется с любой другой вершиной единственным маршрутом. БИНАРНОЕ ДЕРЕВО - э–о ориентированное дерево, в котором каждая вершина имеет не более двух непосредственных потомков, т.е. delta+(v)<=2 для всех v in V. Бинарное дерево является ПОЛНЫМ, если каждая вершина, не являющаяся листом дерева, имеет ровно 2 непосредственных потомка. Очевидно обобщение на k-арное дерево.
УРОВЕНЬ ВЕРШИНЫ - м–ксимальная длина маршрута от этой вершины до листа дерева.
ГЛУБИНА ВЕРШИНЫ - д–ина пути от корня до этой вершины.
ГЛУБИНА ОРДЕРЕВА - д–ина самого длинного пути в Т.
Утверждение. Для полного k-арного ордерева, в котором все l листьев имеют одинаковую глубину d, справедливо следующее:
l<=k^d; d=log(k) l.
Планарность
Плоский граф - г–аф с вершинами, расположенными на плоскости и непересекающимися ребрами. Планарный граф изоморфен плоскому. Всякий подграф планарного графа планарен. Задача о трех домах и трех колодцах. Провести от каждого из трех домов дорожки ко всем трем колодцам так, чтобы дорожки не пересекались. Граф этой задачи не является планарным. Грань графа - м–ожество всех точек плоскости, каждая пара которых может быть соединена жордановой кривой. Граница грани - м–ожество вершин и ребер, принадлежащих грани. Всякий плоский граф имеет одну, и притом единственную, неограниченную грань. Эта грань является внешней гранью графа, остальные - в–утренние.
Теорема Эйлера. Для всякого связного плоского графа n-m+f=2, где n - ч–сло вершин,m - ч–сло ребер, f - ч–сло граней. Подразбиение ребра - у–аление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.
Теорема Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфов, гомеоморфных K5 и K3,3. Деревья и лес. Дерево - с–язный граф без циклов. Лес (или ациклический граф) - н–ограф без циклов (может быть и несвязным).
Теорема. Для неографа G с n вершинами без петель следующие условия эквивалентны:
G - д–рево;
G - с–язный граф, содержащий n-1 ребро;
G - а–иклический граф, содержащий n-1 ребро;
Любые две несовпадающие вершины графа G соединяет единственная цепь.
G - а–иклический граф, такой, что если в него добавить одно ребро, то в нем появится ровно один цикл.
Остов (каркас) связного графа - д–рево, содержащее все вершины графа. Определяется неоднозначно. Редукция графа - о–тов с наибольшим числом ребер. Цикломатическое (или циклический ранг) число графа ν=m-n+c, где n - ч–сло вершин,m - ч–сло ребер, c - ч–сло компонент связности графа. Коциклический ранг (или коранг) ν*=n-c.
Теорема. Число ребер неографа, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно цикломатическому числу графа.
Неограф G является лесом тогда и только тогда, когда ν(G)=0. Неограф G имеет единственный цикл тогда и только тогда, когда ν(G)=1. Остов неографа имеет ν* ребер. Ребра графа, не входящие в остов, называются хордами. Цикл, получающийся при добавлении к остову графа его хорды, называется фундаментальным относительно этой хорды.
Граф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Очевидно, что для связности графа необходимо и достаточно, чтобы в нем для какой-либо фиксированной вершины u и каждой другой вершины v существовал (u, v)- маршрут.
Теорема. Граф G=(V,E) связен тогда и только тогда, когда множество го вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы бе граничные точки каждого ребра находились в одном и том же множестве. Всякий максимальный связный подграф графа G называется связной компонентой (или компонентой) графа G. Слово "ма«симальный" о»начает максимальный относительно включения, т.е. не содержащийся в связном подграфе с большим числом элементов. Множество вершин связной компоненты называется областью связности. Для ориентированного графа вводится понятие ориентированного маршрута – это последовательность вида (1), в которой ei=(vi,vi+1). Аналогом цепи в этой итуации служить путь (ориентированная цепь). Аналогом цикла служит контур ориентированный цикл).
Орграф называется сильносвязным, если любые две его вершины достижимы руг из друга. Орграф называется одностороннесвязным, если для любой пары его вершин по меньшей мере одна достижима из другой. Орграф называется слабосвязным, если любые две вершины его основания соединены маршрутом. Орграф называется несвязным, если его основание несвязный псевдограф.
Теорема. Орграф является сильносвязным тогда и только тогда, когда в нем есть основной циклический маршрут.
Необходимость. Пусть G – сильносвязный орграф и T=(v0, x1, v1,..., xn, v0) – его циклический маршрут, проходящий через максимально возможное число вершин. Если этот маршрут не является остовным, то возьмем вне его вершину v. Так как G – сильносвязный орграф, то существуют маршруты T1=(v0, y1,..., v), T2=(v, z1,..., v0). Но тогда циклический маршрут T’=(v0, x1, v1,..., xn, v0, y1,..., v, z1,..., v0) содержит большее число вершин, чем T, что противоречит выбору маршрута T. Следовательно, T – остовной маршрут.
Достаточность. Пусть u и v – две произвольные вершины орграфа G, а T=(v0, x,..., v, y,..., u, z,..., v0) – циклический маршрут. Тогда u достижима из v с помощью маршрута (v, y,..., u) – части маршрута T, – а v из u – с помощью маршрута (u, z,..., v0, x,..., v).3
Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.
Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.
Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.
|
|
|
