Элементы дискретной математики - 68 стр.

UptoLike

ВУЗ: 

ЯГПУ им. Ушинского | Ярославль

Составители: 

Рубрика: 

68
43.
Дана матрица смежности графа. Найти все вершины, входящие в одну компоненту связности с
вершиной 7.
1 2 3 4 5 6 7 8 9 10
1 0 1 1 0 0 0 0 0 0 0
2 1 0 1 0 0 0 0 0 0 0
3 1 1 0 0 0 0 0 0 0 0
4 0 0 0 0 1 0 1 0 0 0
5 0 0 0 1 0 1 0 0 0 0
6 0 0 0 0 1 0 1 0 0 0
7 0 0 0 1 0 1 0 0 0 0
8 0 0 0 0 0 0 0 0 1 1
9 0 0 0 0 0 0 0 1 0 1
10 0 0 0 0 0 0 0 1 1 0
44. Выделите компоненты связности графа (3 балла)
0 1 1 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 1 0 1
0 0 0 0 1 1 0
0 1 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 1 0 1
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 0 0 0 1 1 0
0 0 0 1 0 0 1
0 0 1 0 0 0 1
1 1 0 0 0 0 0
1 1 0 0 0 0 0
0 0 1 0 0 0 0
45. Дана матрица смежности графа. Найдите матрицу достижимостей этого графа, не изображая его.
1 2 3 4 5 6 7 8 9
1 0 0 0 1 0 0 1 0 0
2 0 0 1 0 0 0 0 0 0
3 0 1 0 0 0 0 0 0 0
4 1 0 0 0 0 0 1 0 0
5 0 0 0 0 0 1 0 1 1
6 0 0 0 0 1 0 0 1 1
7 1 0 0 1 0 0 0 0 0
8 0 0 0 0 1 1 0 0 1
9 0 0 0 0 1 1 0 1 0
46. В стране Семерка 15 городов, каждый из которых соединен дорогами не менее чем с 7 другими.
Докажите, что из любого города можно добраться до любого другого (возможно, проезжая через
другие города).
47.
Докажите, что граф с n вершинами, степень каждой из которых не менее (n–1)/2- связен.
48.
В некотором государстве лишь один вид транспорта – автомобиль. Из столицы выходит 21
автомобильная дорога, из города Дальний - одна, а из всех остальных городов - по 20. Докажите,
что из столицы можно доехать в Дальний (возможно, с пересадками).

Страницы