Учебник по дискретной математики. Д. Ушинского Дискретная математика

Алгоритмы обхода связного графа.

70. 
    Перечислить вершины графа в порядке обхода а) в глубину; в) в ширину.
    

71. 
    Граф задан матрицей смежности. Найти
    

• 
  Какой-либо путь из вершины 2 в вершину 4;
  
• 
  кратчайший путь из вершины 2 в вершину 4;
  
• 
  кратчайшие пути из вершины 2 ко всем остальным вершинам.
  

	1	2	3	4	5	6	7	8	9	10
1	0	1	0	0	1	0	0	0	0	0
2	1	0	1	0	0	0	0	0	1	0
3	0	1	0	1	0	0	0	0	0	0
4	0	0	1	0	1	1	0	1	1	0
5	1	0	0	1	0	0	0	0	0	0
6	0	0	0	1	0	0	1	0	0	0
7	0	0	0	0	0	1	0	1	0	1
8	0	0	0	1	0	0	1	0	0	0
9	0	1	0	1	0	0	0	0	0	0
10	0	0	0	0	0	0	1	0	0	0

72. 
    На клетчатом листе бумаги размером 10 х 10 закрашены некоторые клетки. Разрешается ходить по не закрашенным клеткам, переходя на каждом шаге вверх, вниз, вправо или влево. Описать алгоритм, отвечающий на следующие вопросы:
    

73. 
    В двузначном числе за один ход разрешается заменить любую цифру суммой цифр по модулю 10. Заданы два двузначных числа a и b. Написать программу, которая определяет: можно ли построить цепочку ходов, которая переводит a в b; минимальную такую цепочку. В двузначном числе старшая цифра может быть и нулем.
    
74. 
    На шахматной доске N х N, несколько клеток, которой вырезано, заданы две клетки. Построить минимальный путь коня из одной данной клетки в другую.
    
75. 
    В таблице N x N, где N<13, клетки заполнены случайным образом цифрами от 0 до 9. Предложить алгоритм, позволяющий найти маршрут из клетки (1,1) в клетку (N,N) и удовлетворяющий следующим условиям:
    

• 
  любые две последовательные клетки в маршруте имеют общую сторону;
  
• 
  количество клеток маршрута минимально;
  
• 
  из всех маршрутов, удовлетворяющих условиям 1) и 2), искомый маршрут тот, сумма цифр в клетках которого максимальна.