Версия для печати
Убрать все задачи

---

На шахматной доске 8×8 стоит кубик (нижняя грань совпадает с одной из клеток доски). Его прокатили по доске, перекатывая через рёбра, так, что кубик побывал на всех клетках (на некоторых, возможно, несколько раз). Могло ли случиться, что одна из его граней ни разу не лежала на доске?

   Решение

Темы:    [ Связность и разложение на связные компоненты ] [ Деревья ]

Сложность: 3 Классы: 6,7,8

Прислать комментарий

Условие

Доказать, что
  а) из связного графа можно выкинуть несколько рёбер так, чтобы осталось дерево;
  б) в дереве с n вершинами ровно  n – 1  ребро;
  в) в дереве не меньше двух висячих вершин;
  г) в связном графа из n вершин не меньше  n – 1  ребра;
  д) если в связном графе n вершин и  n – 1  ребро, то он – дерево.

Решение

  а) Если граф – не дерево, то в нём есть простой цикл. Любое ребро из этого цикла можно выкинуть без нарушения связности. Этот процесс остановится, когда граф станет деревом.

  б) У дерева есть висячая вершина (см. задачу 30786). Удалим её вместе с ребром, которое из нее выходит. Оставшийся граф также является деревом. Поэтому у него есть висячая вершина, которую мы также удалим вместе с выходящим из нее ребром. Проделав эту операцию  n – 1  раз, мы получим граф, состоящий из одной вершины (в котором, конечно, нет рёбер). Поскольку каждый раз удалялось ровно одно ребро, то сначала их было  n – 1.

  в) Выйдем из висячей вершины и пойдём по графу как в задаче 30786. Так же как и там этот путь закончится в другой висячей вершине.

  г) Удалим из графа несколько вершин, превратив его в дерево. В полученном дереве  n – 1  вершина, а в иcходном – не меньше.

  д) Если это не так, то, превратив его в дерево, мы получим противоречие с п. б).

Источники и прецеденты использования