Связность в графах

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

Основные сведения о графах

Теоретическая часть

Произвольного орграфа

Определение компонент сильной связности

Цель работы: изучение методов разложения орграфа на компоненты сильной связности, раскраска графа.

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

Две вершины графа называются смежными, если они соединены ребром. Вершина инцидентна ребру, если ребро соединяет ее с другой какой-то вершиной. Петля – ребро, соединяющее вершину саму с собой. Степень вершины – это число инцидентных ей ребер. Цепью называется последовательность неповторяющихся ребер, соединяющих какие-либо две вершины графа. Замкнутая цепь в графе называется циклом.

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

Ребра графа могут иметь вес, который может интерпретироваться, например, как длинна ребра.

Графы являются одной из наиболее часто используемых математических структур, так как они удобны для задания связей между объектами.

Граф можно задать аналитически как совокупность множества вершин V и множества ребер U: G=<V,U>, где V={V1,V2,…,V_N}, U={U1, U2, …, U_R}. Однако более наглядными являются графические способы задания графов.

Матрица инцидентности – это прямоугольная матрица I размерностью N x R, имеющая N строк и R столбцов, и определяющая инцидентность вершин и ребер графа:

Элементы матрицы I определяются так:

1, если вершина Vi инцидентна ребру Uj,

I(i,j) =

0, в противном случае.

В каждом столбце матрицы инцидентности ровно две единицы. У ориентированного графа I(i,j)=±1, в зависимости от направления дуги. Для записи информации об инцидентности вершин и ребер графа используется также список концов ребер, т.е. для каждого ребра задается пара его конечных вершин. Для орграфа первой указывается вершина, из которой выходит дуга.

Матрица смежности – это квадратная матрица размерностью N x N, элементы которой определяются так:

1, если Vi и Vj смежны,

S(i,j) =

0, в противном случае.

Для неориентированного графа матрица смежности S симметрична, для орграфа S(i,j)=1, если есть дуга от Vi к Vj. В случае мультиграфа в качестве S(i,j) задается кратность соответствующего ребра или его вес.

Ели число ребер в графе мало, матрица смежности содержит много нулей, и более удобным является задание списка смежных вершин.

На рис.1 приведены примеры задания орграфа.

Орграф называется сильносвязанным, если для любых двух вершин V_i и V_j найдется путь из Vi в Vj, и наоборот путь из Vj в Vi. В противном случае граф называется несвязным.

На рис. 2 показаны сильносвязный и несильносвязный графы.

V3

V2

V1

Рис.2

Компонентой сильной связности орграфа G называется его подграф G`, удовлетворяющий следующим условиям:

1) подграф G` - сильносвязный;

2) добавление к G` любой вершины Vi из графа G c дугами инцидентности V нарушает условие сильной связности подграфа G`.

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

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

Прямым транзитивным замыканием вершины Vi орграфа называется выражение

где - множество вершин графа, в которые ведут дуги из вершины Vi;

- множество вершин графа, в которые ведут дуги из множества вершин ;

- множество вершин графа, в которые ведут дуги из множества вершин , т.д.

Таким образом, - это множество вершин графа, в которые ведут пути из Vi, включая и вершину Vi, или множество вершин графа, достижимых из Vi.

Обратным транзитивным замыканием вершины Vi орграфа называется выражение

где - множество вершин графа, из которых идут дуги в вершину Vi и т.д.

Если для вершины Vi найдены и , то компонента сильной связности, включая вершину Vi,может быть найдена так:

.

1.3.1 Алгоритм нахождения компонент сильной связности (алгоритм Мальгранжа-Томеску)

1) Граф задается матрицей смежности (рис.3).

			…

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

3) Если столбец заполнен, переходят к алгоритму заполнения строки .

Алгоритм заполнения строки аналогичен алгоритму заполнения столбца.

4) Находят

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

1.3.2 Алгоритм заполнения столбца .

1) В клетке столбца , являющейся продолжением строки Vi матрицы смежности, ставится нуль. Переход к п.2.

2) Если в клетках матрицы смежности на пересечении i-ой строки и столбцов Vj,…,Vk стоят единицы, то в клетках столбца , являющихся продолжением строк Vj,…,Vk ставятся единицы. Переход к п.3.

3) Если в клетках матрицы смежности на пересечении строк Vj,…,Vk со столбцами Vp,…,Vm стоят единицы, то в клетках столбца являющихся продолжением строк Vj,…,Vk ставится цифра 2. Переход к п.4.

4) Процесс заполнения столбца продолжается до тех пор, пока возможно. Переход к п.5.

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

Дата добавления: 2017-01-13