Решение задачи перечисления путей в графах

Пусть имеется некоторый ориентированный граф G = (X_G, P_G) и пусть требуется перечислить все пути графа G, состоящие ровно из k дуг. Данная задача решается при помощи следующей процедуры:

Шаг 1. Выписать матрицу смежности графа G.

Шаг 2. По матрице A(G) строится таблица Г₁, у которой в каждой (i, j)-ой ячейке написано множество путей из вершины x_i в вершину x_j длиной в одну дугу.

Шаг 3. По матрице A(G) и таблице Г₁ строится таблица Г₂, у которой в каждой (i, j)-ой ячейке написано множество путей из вершины x_i в вершину x_j длиной в две дуги.

.

.

.

Шаг k. По матрице A(G) и таблице Г_k-1 строится таблица Г_k, у которой в каждой (i, j)-ой ячейке написано множество путей из вершины x_i в вершину x_j длиной ровно в k дуг.

 

Решение:

1.

A(G) =

 

 

2. По матрице смежности A(G) формируем таблицу Г₁:

 

	Ø	{(1,2)}	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	{(2,6)}	Ø	Ø	{(2,9)}	Ø
	{(3,1)}	Ø	Ø	{(3,4)}	Ø	Ø	Ø	{(3,8)}	Ø	Ø
	Ø	{(4,2)}	Ø	Ø	Ø	Ø	Ø	Ø	Ø	{(4,10)}
	Ø	Ø	{(5,3)}	Ø	{(5,5)}	Ø	{(5,7)}	Ø	Ø	Ø
	Ø	Ø	Ø	{(6,4)}	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	{(7,5)}	Ø	Ø	{(7,8)}	Ø	Ø
	{(8,1)}	Ø	{(8,3)}	Ø	Ø	Ø	{(8,7)}	Ø	{(8,9)}	Ø
	Ø	{(9,2)}	Ø	Ø	{(9,5)}	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	{(10,6)}	Ø	{(10,8)}	Ø	{(10,10)}

 

	Ø	Ø	Ø	Ø	Ø	{(1,2,6)}	Ø	Ø	{(1,2,9)}	Ø
	Ø	{(2,9,2)}	Ø	{(2,6,4)}	{(2,9,5)}	Ø	Ø	Ø	Ø	Ø
	{(3,8,1)}	{(3,1,2), (3,4,2)}	{(3,8,3)}	Ø	Ø	Ø	{(3,8,7)}	Ø	{(3,8,9)}	{(3,4,10)}
	Ø	Ø	Ø	Ø	Ø	{(4,2,6), (4,10,6)}	Ø	{(4,10,8)}	{(4,2,9)}	{(4,10,10)}
	{(5,3,1)}	Ø	{(5,5,3)}	{(5,3,4)}	{(5,5,5) (5,7,5)}	Ø	{(5,5,7)}	{(5,3,8), (5,7,8)}	Ø	Ø
	Ø	{(6,4,2)}	Ø	Ø	Ø	Ø	Ø	Ø	Ø	{(6,4,10)}
	{(7,8,1)}	Ø	{(7,5,3), (7,8,3)}	Ø	{(7,5,5)}	Ø	{(7,5,7), (7,8,7)}	Ø	{(7,8,9)}	Ø
	{(8,3,1)}	{(8,1,2), (8,9,2)}	Ø	{(8,3,4)}	{(8,7,5), (8,9,5)}	Ø	Ø	{(8,3,8), (8,7,8)}	Ø	Ø
	Ø	Ø	{(9,5,3)}	Ø	{(9,5,5)}	{(9,2,6)}	{(9,5,7)}	Ø	{(9,2,9)}	Ø
	{(10,8,1)}	Ø	{(10,8,3)}	{(10,6,4)}	Ø	{(10,10,6)}	{(10,8,7)}	{(10,10,8)}	{(10,8,9)}	{(10,10,10)}

3. По матрице смежности A(G) и таблице Г₁ строим таблицу Г₂:

 

 

4. По матрице смежности A(G) и таблице Г₂ строим таблицу Г₃:

	Ø	{(1,2,9,2)}	Ø	{(1,2,6,4)}	{(1,2,9,5)}	Ø	Ø	Ø	Ø	Ø
	Ø	{(2,6,4,2)}	{(2,9,5,3)}	Ø	{(2,9,5,5)}	{(2,9,2,6)}	{(2,9,5,7)}	Ø	{(2,9,2,9)}	{(2,6,4,10)}
	{(3,8,3,1)}	{(3,8,1,2), (3,8,9,2)}	Ø	{(3,8,3,4)}	{(3,8,7,5), (3,8,9,5)}	{(3,1,2,6), (3,4,2,6), (3,4,10,6)}	Ø	{(3,4,10,8), (3,8,3,8), (3,8,7,8)}	{(3,1,2,9), (3,4,2,9)}	{(3,4,10,10)}
	{(4,10,8,1)}	{(4,2,9,2)}	{(4,10,8,3)}	{(4,2,6,4), (4,10,6,4)}	{(4,2,9,5)}	{(4,10,10,6)}	{(4,10,8,7)}	{(4,10,10,8)}	{(4,10,8,9)}	{(4,10,10,10)}
	{(5,3,8,1), (5,5,3,1), (5,7,8,1)}	{(5,3,1,2), (5,3,4,2)}	{(5,3,8,3), (5,5,5,3), (5,7,5,3), (5,7,8,3)}	{(5,5,3,4)}	{(5,5,5,5), (5,5,7,5), (5,7,5,5)}	Ø	{(5,3,8,7), (5,5,5,7), (5,7,5,7), (5,7,8,7)}	{(5,5,3,8), (5,5,7,8)}	{(5,3,8,9), (5,7,8,9)}	{(5,3,4,10)}
	Ø	Ø	Ø	Ø	Ø	{(6,4,2,6), (6,4,10,6)}	Ø	{(6,4,10,8)}	{(6,4,2,9)}	{(6,4,10,10)}
	{(7,5,3,1), (7,8,3,1)}	{(7,8,1,2), (7,8,9,2)}	{(7,5,3,3)}	{(7,5,3,4), (7,8,3,4)}	{(7,5,5,5), (7,5,7,5), (7,8,7,5), (7,8,9,5)}	Ø	{(7,5,5,7)}	{(7,5,3,8), (7,5,7,8), (7,8,3,8), (7,8,7,8)}	Ø	Ø
	{(8,3,8,1), (8,7,8,1)}	{(8,3,1,2), (8,3,4,2)}	{(8,3,8,3), (8,7,5,3), (8,7,8,3), (8,9,5,3)}	Ø	{(8,7,5,5), (8,9,5,5)}	{(8,1,2,6), (8,9,2,6)}	{(8,3,8,7), (8,7,5,7), (8,7,8,7), (8,9,5,7)}	Ø	{(8,1,2,9), (8,3,8,9), (8,7,8,9), (8,9,2,9)}	{(8,3,4,10)}
	{(9,5,3,1)}	{(9,2,9,2)}	{(9,5,5,3)}	{(9,2,6,4), (9,5,3,4)}	{(9,2,9,5), (9,5,5,5), (9,5,7,5)}	Ø	{(9,5,5,7)}	{(9,5,3,8), (9,5,7,8)}	Ø	Ø
	{(10,8,3,1), (10,10,8,1)}	{(10,6,4,2), (10,8,1,2), (10,8,9,2)}	{(10,10,8,3)}	{(10,8,3,4), (10,10,6,4)}	{(10,8,7,5), (10,8,9,5)}	{(10,10,10,6)}	{(10,10,8,7)}	{(10,8,3,8), (10,8,7,8), (10,10,10,8)}	{(10,10,8,9)}	{(10,10,10,10)}

 

5. По матрице смежности A(G) и таблице Г₃ строим таблицу Г₄:

	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø
	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø	Ø

 

Таким образом мы получили таблицу Г₄, в которой перечислены все пути в ориентированном графе G, состоящие из четырех дуг.

 

Задание 10.

Сформировать матрицу достижимости ориентированного графа G. Найти в ней строку, содержащую наименьшее число нулей. Вершину, соответствующую этой строке считать стартовой. Найти кратчайшие пути от стартовой вершины до всех вершин ориентированного графа G, достижимых из стартовой вершины.

Определение. Пусть дан граф G = (X_G, P_G). Матрицей достижимости называется матрица Т(G)_{[ n x n]}, где n – мощность множества вершин, с элементами t_ij, которые определяются следующим условием:

t_ij =