Смекни!
smekni.com

Орграфы, теория и применение (стр. 3 из 6)

Вершина 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 - ч–сло граней. Подразбиение ребра - у–аление ребра и добавление двух новых, инцидентных вершинам удаленного ребра и соединенных между собой новой вершиной. Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ребер.