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

Утверждение

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

Если 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

Теорема. Орграф является одностороннесвязным тогда и только тогда, когда в нем есть остовной маршрут.

Теорема. Орграф является слабосвязным тогда и только тогда, когда в его основание есть связный псевдограф.

Сильносвязной компонентой орграфа называется его максимальный относительно включения сильносвязный подграф.

Матричное представление графов

Орграфы и матрицы. Матрицей сложностей A (D) орграфа D называется (рхр)-матрица \\аи\\> У которой ai}=\, если vfl,— дуга орграфа D, и atj~Q в противном случае. Сумма по столбцу легко проверить, что суммы элементов по строкам матрицы A (D) равны полустепеням исхода вершин орграфа D, а суммы элементов по столбцам — полустепеням захода. Как и в случае графов, степени матрицы смежностей. А орграфа дают полную информацию о числе маршрутов, идущих из одной вершины в другую. Есть еще три матрицы, связанные с орграфом D — матрица достижимостей, матрица расстояний и матрица обходов. Матрицу достижимостей орграфа можно использовать для нахождения его сильных компонент. Формула для числа остовных входящих деревьев данного орграфа была найдена BOTTOM и Мейберри, а доказана Таттом. Чтобы сформулировать этот результат, известный как матричная теорема о деревьях для орграфов, введем еще матрицы, связанные с D. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента 1-й строки матрицы Mod равно числу остовных входящих деревьев, у которых вершина vt является стоком. Для каждого помеченного орграфа D алгебраическое дополнение любого элемента j-го столбца матрицы Mid равно числу остовных выходящих деревьев, у которых вершина Vj является источником. Эйлеров контур в орграфе D — это замкнутый остовный маршрут, в котором каждая дуга орграфа D встречается по одному разу. Орграф называется эйлеровым, если в нем есть эйлеров контур. Для графов, можно легко показать, что слабый орграф D эйлеров тогда и только тогда, когда у каждой его вершины полустепень захода равна полустепени исхода. Сформулируем теперь теорему, в которой дается формула для числа эйлеровых контуров в эйлеровых орграфах. Эту теорему можно доказать очень изящно с помощью матричной теоремы о деревьях для орграфов; В эйлеровом орграфе число эйлеровых контуров равно с \\ (d,-—1)! Заметим, что для эйлерова орграфа МоА=М\А и все суммы и по строкам, и по столбцам равны нулю, так что все алгебраические дополнения равны между собой. Первый орграф с тремя вершинами называется транзитивной тройкой, второй — циклической тройкой.

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