Таблицы Брадиса

Ясно, что степень этой вершины

Ясно, что степень этой вершины

Элементы математики в задачах - Г. А. Мерзон

/.

Решение. Допустим, что в связном графе, число вершин которого больше 1, нашлась вершина степени 0. Это означает, что из этой вершины не выходит ни одного ребра, а значит, ее нельзя соединить путем ни с одной другой вершиной графа.

Обратное утверждение неверно, например, для следующего графа:

Определение 7. Связный граф называется деревом, если в нем не существует цикла (т. е. пути, конец которого совпадает с началом), все ребра которого различны.

Задача 13. Докажите, что в любом дереве есть: а) хотя бы одна; б) хотя бы две вершины степени 1.

Решение. а) Рассмотрим произвольное дерево. Выйдем из одной из вершин этого дерева и будем идти по его ребрам, никогда не воз­вращаясь по ребру, по которому мы только что пришли в вершину. Поскольку в дереве нет циклов, мы никогда не вернемся в вершину, в которой уже были, а значит, не более чем через п ходов (п — число вершин дерева) попадем в вершину, из которой не сможем выйти. Ясно, что степень этой вершины должна быть равна 1.

б) Достаточно повторить рассуждения предыдущего пункта, вы­ходя из вершины степени 1.

Задача 14. Докажите, что в дереве число вершин на 1 больше числа ребер.

Решение. Докажем утверждение задачи индукцией по числу п вершин дерева.

База индукции очевидна.

Шаг индукции. Пусть утверждение задачи верно для деревьев с п вершинами. Докажем его для деревьев с п + 1 вершиной. Рассмотрим произвольное дерево с п + 1 вершиной. Найдем в нем вершину сте­пени 1 и выбросим вместе с выходящим из нее ребром. Очевидно, что получилось дерево с п вершинами. По предположению индукции в этом дереве п — 1 ребро. Следовательно, в исходном дереве было п — 1 +1 = п ребер.