Самостоятельная работа «Пересчет путей в орграфе»

Задание по теме «Пересчет путей в орграфе».

Для графа, данного на рисунке, найти и записать

a) все пути длиной 3 из вершин А и В;

b) между какими вершинами наибольшее число путей длины 3;

c) орцепь максимальной длины;

d) между какой парой вершин A и F или C и G больше число путей длиной 4.

Ответ: a). все пути длиной 3 из вершин А и В : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

b). наибольшее число путей длины 3 между вершинами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

c). орцепь максимальной длины -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

d). между парой вершин . . . . . . . . . . . . . . . . . . . больше число путей длиной 4 чем между

парой. . . . . . . . . . . . . . . .