Задание №65

Граф называется полным, если каждая его вершина непосредственно связана со всеми остальными. Найти максимальный полный подграф (клику) в неориентированном графе. Исходный граф задан матрицей смежности порядка N. (Матрица смежности состоит из 0 и 1. Элементв матрице смежности равен 1, есливершина графа связана с, иначе элементравен 0).

Задание №66

Задана система односторонних дорог. Найти минимальный путь, соединяющий города ии не проходящий через заданную совокупность городов. (Система дорог задана матрицей смежности, см. задание №65).

Задание №67

В системе двухсторонних дорог для каждой пары городов указать длину кратчайшего пути между ними. (Система дорог задана матрицей смежности, см. задание №65).

Задание №68

Задана система двухсторонних дорог. Найти два города и соединяющий их путь, который проходит через каждую из дорог системы ровно один раз.

(Система дорог задана матрицей смежности, см. задание №65).

Задание №69

В системе двухсторонних дорог за проезд каждой дороги взимается некоторая пошлина. Найти путь из города вс минимальной величиной, где- сумма длин дорог пути, а- сумма пошлин проезжаемых дорог. (Система дорог задана матрицей смежности, см. задание №65).

Задание №70

По системе двухсторонних дорог определить, можно ли закрыв какие-нибудь три дороги, добиться того, чтобы из города нельзя было попасть в город. (Система дорог задана матрицей смежности, см. задание №65).