Страница:
<< 1 2 3 4 5 6 7 >> [Всего задач: 36]
В графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом каждые два города соединяет ровно один путь.
Сколько в этой стране дорог?
Дима нарисовал на доске семь графов, каждый из которых является деревом с шестью вершинами. Докажите, что среди них есть два изоморфных.
|
|
|
Сложность: 3+
Классы: 7,8,9
|
В стране несколько городов (больше одного); некоторые пары городов соединены дорогами. Известно, что из каждого города можно попасть в любой другой, проезжая по нескольким дорогам. Кроме того, дороги не образуют циклов, то есть если выйти из некоторого города по какой-то дороге и далее двигаться так, чтобы не проходить по одной дороге дважды, то невозможно возвратиться в начальный город. Докажите, что в этой стране найдутся хотя бы два города, каждый из которых соединен дорогой ровно с одним городом.
Докажите, что связный граф, у которого число рёбер на единицу меньше числа вершин, является деревом.
Страница:
<< 1 2 3 4 5 6 7 >> [Всего задач: 36]
Фильтр
