2 2 2 2 2 1 1 2
2 2 2 2 2 1 1 2 2 1 1
M0= 3 3 3 3 M1= 3 3 3 3 M2=M1 M3=M2 M4= 4 1 3 3
4 4 4 4 4 1 1 4 4 1 1 4
Например, необходимо вывести кратчайший путь из 3-й вершины во 2-ю. Элемент M[3,2] равен 1, поэтому смотрим на элемент M[3,1]. Он равен четырем. Сравниваем M[3,4] c 3-й. Есть совпадение, мы получили кратчайший путь: 3?4?1? 2.
procedure All_Way(i,j:integer);{вывод пути между вершинами i и j}
begin
if M[i,j]=i then if i=j write(i) else write(i,’-’,j)
else begin All_Way(i,M[i,j]);All_Way(M[i,j],j);end;
end;
3.7. Независимые и доминирующие множества
Задача поиска подмножеств множества вершин V графа G, удовлетворяющих определенным условиям, свойствам, возникает достаточно часто.
3.7.1. Независимые множества
Дан неориентированный граф G=(V,E). Независимое множество вершин есть множество вершин графа G, такое, что любые две вершины в нем не смежны, то есть никакая пара вершин не соединена ребром. Следовательно, любое подмножество S, содержащееся
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
