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

UptoLike

ВУЗ: 

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

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

Рубрика: 

70
Циклы
60. На рисунке изображена карта Кенигсбергских мостов.
Определите, можно ли, начав с некоторой точки, совершить
прогулку и вернуться в исходную точку, пройдя по каждому мосту
ровно 1 раз.
61.
Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до
любого другого. Турист обошел все острова, пройдя по каждому мосту ровно один раз. На
острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист:
а) не с него начал и не на нем закончил?
б) с
него начал, но не на нем закончил?
в) с него начал и на нем закончил?
62.
Определите, является ли граф, заданный матрице смежности, эйлеровым. (1 балл)
0 1 1 1 1 1 1
1 0 1 0 0 0 0
1 1 0 1 1 0 0
1 0 1 0 0 0 0
1 0 1 0 0 0 0
1 0 0 0 0 0 1
1 0 0 0 0 1 0
0 1 0 0 0 0 0
1 0 1 0 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 1 0 1 1
0 0 1 1 0 0 0
0 1 1 0 0 0 0
0 1 1 1 0 0 0
0 0 0 0 1 0 0
0 0 0 1 0 1 0
0 0 1 0 1 0 0
1 0 0 0 0 1 0
1 0 0 0 0 0 1
1 0 0 0 0 0 0
63. Существует ли эйлеров граф, обладающий висячей вершиной?
64. Привести пример графа, все степени которого четны, но который не является эйлеровым.
65. Для каких графов можно найти цикл, проходящий по каждому ребру 1 раз?
66. Для каких графов можно найти маршрут, проходящий по каждому ребру 1 раз?
67.
Докажите, что на любом связном графе с 2k нечетными вершинами можно указать семейство из
k маршрутов, которые в совокупности содержат все ребра графа по одному разу.
68.
Имеется полный граф на 16 вершинах. Каково минимальное число маршрутов в графе, которые в
совокупности содержат все его ребра и все вершины?
69.
Дан кусок проволоки длиной 120 см. а) Можно ли, не ломая проволоки, изготовить каркас куба с
ребром 10 см? б) Какое наименьшее число раз придется ломать проволоку, чтобы все же
изготовить требуемый каркас?
70.
Можно ли нарисовать решетку, изображенную на рисунке, не отрывая карандаш от бумаги и не
проводя одну и ту же линию дважды? Какое наименьшее число раз придется оторвать карандаш
от бумаги?
А
В
D
С

Страницы