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

Доказывать будем индукцией по п.

Доказывать будем индукцией по п.

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

Решение. Доказывать будем индукцией по п. База индукции прове­ряется явно, докажем шаг. Выберем двух Петиных одноклассников, у которых число друзей, соответственно, наибольшее и наименьшее. Имеется две возможности — число друзей у этих одноклассников равно 0 и 27 или 1 и 28 соответственно. В обоих случаях можно убедиться, что если исключить их из класса, то у всех оставшихся Петиных одноклассников снова будет по различному числу друзей. Кроме того, число Петиных друзей уменьшится на 1. Теперь можно применить предположение индукции и свести все к случаю, когда число одноклассников равно двум (четный случай) или трем (нечет­ный).

Задача 8* (теорема Кэли). В графе с п вершинами каждая вершина соединена с каждой ребром (такой граф называется полным). Дока­жите, что существует ровно пп—2 способов выкинуть несколько ребер так, чтобы оставшийся граф являлся деревом.

Набросок решения. Опишем конструкцию, лежащую в основе дока­зательства. Занумеруем все вершины графа числами от 1 до п. Идея состоит в том, что нужно сопоставить каждому дереву в полном графе набор из п — 2 чисел.

Делается это следующим образом. Если имеется дерево в полном графе с п вершинами, то мы выбираем в нем лист (висячую вершину) с наименьшим номером, выкидываем его и записываем номер той вершины, с которой он был соединен. Это повторяется п — 2 раза, и утверждается, что полученные таким образом п — 2 числа, в свою очередь, однозначно задают исходное дерево. Кроме того, нужно еще показать, что любой набор из п — 2 чисел от 1 до п так получается.

Определение 1. Ориентированным графом называется граф, на реб­рах которого поставлены стрелки. Его ребра называются дугами. Более формально, ориентированный граф — это пара Г = (V, Е) из конечного множества вершин V и множества дуг Е, элементами которого являются упорядоченные пары вершин графа Г.