Решение задачи перечисления путей в графах
Пусть имеется некоторый ориентированный граф G = (XG, PG) и пусть требуется перечислить все пути графа G, состоящие ровно из k дуг. Данная задача решается при помощи следующей процедуры:
Шаг 1. Выписать матрицу смежности графа G.
Шаг 2. По матрице A(G) строится таблица Г1, у которой в каждой (i, j)-ой ячейке написано множество путей из вершины xi в вершину xj длиной в одну дугу.
Шаг 3. По матрице A(G) и таблице Г1 строится таблица Г2, у которой в каждой (i, j)-ой ячейке написано множество путей из вершины xi в вершину xj длиной в две дуги.
.
.
.
Шаг k. По матрице A(G) и таблице Гk-1 строится таблица Гk, у которой в каждой (i, j)-ой ячейке написано множество путей из вершины xi в вершину xj длиной ровно в k дуг.
Решение:
1.
A(G) =
2. По матрице смежности A(G) формируем таблицу Г1:
| Ø | {(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) и таблице Г1 строим таблицу Г2:
4. По матрице смежности A(G) и таблице Г2 строим таблицу Г3:
| Ø | {(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) и таблице Г3 строим таблицу Г4:
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | |
| Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø | Ø |
Таким образом мы получили таблицу Г4, в которой перечислены все пути в ориентированном графе G, состоящие из четырех дуг.
Задание 10.
Сформировать матрицу достижимости ориентированного графа G. Найти в ней строку, содержащую наименьшее число нулей. Вершину, соответствующую этой строке считать стартовой. Найти кратчайшие пути от стартовой вершины до всех вершин ориентированного графа G, достижимых из стартовой вершины.
Определение. Пусть дан граф G = (XG, PG). Матрицей достижимости называется матрица Т(G)[n x n], где n – мощность множества вершин, с элементами tij, которые определяются следующим условием:
tij = 