Пути и маршруты

Метод Мальгранжа

Пусть дан граф G=(X, A), где X={ х_i }, i =1, 2,..., n – множество вершин, а A={ a_i }, i =1, 2,..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиения заключается в следующем [4].

1. Для произвольной вершины х_i X находим прямое T⁺(х_i) и обратное T^-(х_i) транзитивные замыкания.

2. Находим T⁺(х_i) T^-(х_i). Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G₁ = (Х₁, A₁).

3. Из исходного графа вычитаем подграф G₁:G '=G\G₁, Х'=X\Х₁.

4. Граф G 'принимаем за исходный граф и пока X ' Ø пункты 1, 2, 3 алгоритма повторяются.

Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на рис. 7.1,a, матрица смежности которого показана на рис. 7.1,б.

Рис. 7.1.

РАЗБИЕНИЕ – 1.

Таблица 7.1.
		X1	X7	X11
	X1
A7=	X7
	X11

1. Начальной вершиной первого разбиения выберем х₁. Построим прямое и обратное транзитивные замыкания. T⁺(х₁)– столбец, показанный справа от матрицы А, а T^-(х₁) – строка, находящаяся ниже матрицы смежности.

T⁺(х₁) = {х₁, х₄, х₅, х₆, х₇, х₈, х₁₁ },

T^-(х₁) = {х₁, х₂, х₃, х₇, х₉, х₁₀, х₁₁}.

2. Находим T⁺(х₁) T^-(х₁) = {х₁, х₇, х₁₁}. Эти вершины и составляют первый выделенный, максимальный сильно связный подграф G₁ = (Х₁, A₁), где Х₁ = {х₁, х₇, х₁₁}, а матрица смежности A₁ подграфа G₁ показана на таблица 7.1.

3. Из исходного графа G вычитаем подграф G₁ G ' = G \G₁;

G ' = (X ', A'), X ' = { х₂, х₃, х₄, х₅, х₆, х₈, х₉, х₁₀ }.

4. Так как X ' не пустое множество, то G' принимаем за G и переходим ко второму разбиению.

РАЗБИЕНИЕ – 2

Таблица 7.2.
		X2	X3	X4	X5	X6	X8	X9	X10		T+(x2)
	X2
	X3
	X4
	X5
A=	X6
	X8
	X9
	X10
	T-(x2)

1. Выбираем любую вершину, принадлежащую X, например, х₂, и находим T⁺(х₂) и T^-(х₂). Это показано в таблице 7.2. T⁺(х₂) = { х₂, х₈ }; T^-(х₂) = { х₂ }.

2. T⁺(х₂) T^-(х₂) = { х₂ }. Следовательно, второй выделенный подграф G₂ состоит из одной вершины х₂.

3. G ' = G \G₂; G ' = (X ', A'); X ' = { х₃, х₄, х₅, х₆, х₈, х₉, х₁₀ }.

4. Так как X ' не пустое множество, то G ' принимаем за G и процесс разбиения продолжается.

7. Лекция: Методы разбиения графа на максимальные сильно связные подграфы

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

Например, для графа на рис. 8.1 последовательности дуг

M₁: a₆, a₅, a₉, a₈, a₄,

M₂: a₁, a₆, a₅, a₉, a₇,

M₃: a₁, a₆, a₅, a₉, a₁₀, a₆, a₄

являются путями. Пути могут быть различными.

Рис. 8.1. Орграф

Орцепью (или простым путем) называется такой путь, в котором каждая дуга используется не более одного раза.

Так пути M₁ и M₂ являются орцепями, а M₃ нет, поскольку дуга a₆ используется дважды.

Простой орцепью (или элементарным путем) называется путь, в котором каждая вершина используется не более одного раза.

Простой орцепью является путь M₂.

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

Путь или маршрут можно изображать также последовательностью вершин. Так путь M₁ можно представить последовательностью вершин х₂, х₅, х₄, х₃, х₅, х₆, и такое представление часто оказывается более полезным.