Составители:
Рубрика:
71
71.
На плоскости дано 100 окружностей, составляющих связную (то есть не распадающуюся на
части) фигуру. Докажите, что эту фигуру можно нарисовать, не отрывая карандаша от бумаги и
не проводя дважды одну и ту же линию.
72.
Для каких чисел m, n граф G является эйлеровым:
1) К
n
– полный граф с n вершинами?
2) K
mn
– полный двудольный граф с n, m вершинами?
3) W
n
– колесо с n вершинами?
73. Для каких чисел m, n граф является гамильтовым?
1) К
n
– полный граф с n вершинами?
2) W
n
– колесо с n вершинами?
74. Дана матрица смежности графа. Определить, является ли граф эйлеровым, гамильтоновым.
1 2 3 4 5
1 0 1 0 1 1
2 1 0 1 1 1
3 0 1 0 1 1
4 1 1 1 0 1
5 1 1 1 1 0
75. В стране некоторые пары городов соединены авиалиниями, причем каждый город соединен не
менее чем с половиной других городов. Докажите, что туристическая фирма может найти такой
маршрут облета городов, который начинается и заканчивается в одном и том же городе, причем
каждый город посещает ровно один раз.
76.
На пир при дворе короля Артура собралось четное число рыцарей, которые либо враждуют, либо
дружат. Оказалось, что у каждого рыцаря друзей больше, чем врагов. Докажите, что можно
рассадить рыцарей за круглым столом таким образом, что справа и слева от каждого из них будет
сидеть друг.
77.
Мышка грызет куб сыра с ребром 3, разбитый на 27 единичных кубиков. Когда мышка съедает
какой-либо кубик, она переходит к другому кубику, имеющему общую грань с предыдущим.
Может ли мышка съесть весь куб, кроме центрального кубика?
78.
Можно ли перевести шахматного коня с клетки а1 на клетку h8, побывав при этом на каждой
клетке шахматной доски ровно один раз?
Алгоритмы обхода связного графа.
79. Перечислить вершины графа в порядке обхода а) в глубину; в) в ширину.
1 2
3
4
6
7
8
Страницы
- « первая
- ‹ предыдущая
- …
- 69
- 70
- 71
- 72
- 73
- …
- следующая ›
- последняя »
