1. Главная
  2. Математика
  3. Решение задачи перечисления путей в графах

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

Пусть имеется некоторый ориентированный граф 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 = Решение задачи перечисления путей в графах - student2.ru

Наши рекомендации

Многие задачи на графах состоят в определении частей графа с заданными свойствами.

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

Решение задачи поиска кратчайших путей (маршрутов)

Решение о размещении магазина. Решение о целевом рынке. Решение об ассортименте. Решение о ценах. Решение о методах стимулирования.

Задачи построения кратчайших путей

Решение задачи об оптимальной диете: симплекс-метод в случае задачи на минимум

Экстремальные задачи на графах

Решение задачи многоцелевой оптимизации при нечеткой постановке задачи

Для данной задачи составить двойственную, решить ее симплекс-методом и, используя первую теорему двойственности, найти решение исходной задачи

Решение транспортной задачи методом потенциалов. Найденное опорное решение проверяется на оптимальность методом потенциалов по следующему критерию: если опорное решение транспортной задачи является