Составители:
Рубрика:
37
24. Граф задан матрицей смежности. Написать программу, перечисляющую его
вершины в порядке обхода в глубину; в ширину.
25. Граф задан матрицей смежности. Написать программу, формирующую его
матрицу достижимостей.
26. Граф задан матрицей смежности. Написать программу, выделяющую компоненты
связности графа.
27. Граф задан матрицей смежности. Написать программу, которая определяет
является ли граф
эйлеровым и в случае, если является строит эйлеров цикл. В
противном случае, указывает минимальное семейство путей, которые в
совокупности содержат все ребра графа по одному разу.
28. Дан взвешенный граф, в котором нет циклов отрицательного веса. Найти путь
минимального веса из одной заданной вершины в другую. (Алг. Форда - Белмана)
29.
Дан взвешенный граф, в котором нет ребер отрицательного веса. Найти путь
минимального веса из одной заданной вершины в другую.
30. Дан взвешенный граф. Найти кратчайшие пути между всеми парами вершин. (Алг.
Флойда)
31. Пролетающие время от времени в опасной близости от нашего спутника Луны
астероиды захватываются ее гравитационным полем и
, будучи никем не
задерживаемы, врезаются с огромной скоростью в лунную поверхность, оставляя
в память о себе порядочных размеров кратеры приблизительно круглой формы.
Увлекающийся астрономией профессор З. В. Ездочетов занялся изучением
современной карты участка лунной поверхности. Он решил найти на ней
максимально длинную цепочку вложенных друг в друга кратеров. Зная о
Ваших
недюжинных способностях в области построения алгоритмов, за помощью в
решении этой непростой задачи он обратился к Вам.
32. Дан ориентированный граф с N вершинами (N<50). Вершины и дуги окрашены в
цвета с номерами от 1 до M (M≤6). Указаны две вершины, в которых находятся
фишки игрока и конечная вершина. Правило перемещения фишек: игрок может
передвигать фишку по дуге, если ее цвет совпадает с цветом вершины, в которой
находится другая фишка; ходы можно делать только в направлении дуг графа;
поочередность ходов необязательна. Игра заканчивается если одна из фишек
достигает конечной вершины. Написать программу поиска кратчайшего пути до
конечной вершины, если он существует.
33. Заданы два
числа N и M (20≤M≤N≤150), где N - количество точек на плоскости.
Требуется построить дерево из M точек так, чтобы оно было оптимальным.
Дерево называется оптимальным, если сумма всех его ребер минимальна. Все
ребра - это расстояния между вершинами, заданными координатами точек на
плоскости.
34. Даны два числа N и M. Построить граф из N вершин и M ребер
. Каждой вершине
ставится в соответствие число ребер, входящих в нее. Граф должен быть таким,
чтобы сумма квадратов этих чисел была минимальна.
