16α. Деревья

Два графа изоморфны, если вершины одного можно занумеровать вершинами другого так, что рёбра перейдут в рёбра. Сколько существует попарно неизоморфных деревьев на шести вершинах? Нарисуйте их.

Вершину степени 1 называют висячей, или листом. Докажите, что в дереве, у которого больше одной вершины, есть висячая вершина, и что таких вершин хотя бы две.

Докажите, что в дереве с n вершинами ровно n − 1 ребро.

Сколько рёбер в лесу — графе без циклов — с n вершинами и k компонентами связности?

Докажите, что из любого связного графа можно выкинуть часть рёбер так, чтобы получилось дерево с теми же вершинами. Такое дерево называют остовом, или остовным деревом, графа.

В графе n вершин и m рёбер. Докажите, что компонент связности в нём не меньше n − m.

Пусть граф связен и имеет n вершин. Докажите, что следующие свойства равносильны: • рёбер ровно n − 1; • при удалении любого ребра граф перестаёт быть связным; • в графе нет циклов; • любые две вершины соединены ровно одним путём. Таким образом, любое из этих свойств можно взять за определение дерева.

Даны n различных по весу камней и весы, позволяющие сравнить любые два из них. Какое наименьшее число взвешиваний нужно, чтобы наверняка найти самый тяжёлый камень?

Сколько рёбер может быть в несвязном графе с n вершинами?

Докажите, что из любого связного графа, в котором больше одной вершины, можно удалить вершину вместе со всеми выходящими из неё рёбрами так, что граф останется связным.

В связном графе 10 вершин и 19 рёбер. Докажите, что в нём найдётся цикл, после уничтожения всех рёбер которого граф не потеряет связность.

В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что из любого города можно долететь до любого другого, возможно с пересадками. Докажите, что можно побывать в каждом городе, совершив не более 198 перелётов.

Дано дерево с n вершинами. Сколькими способами можно раскрасить его вершины в k цветов так, чтобы концы любого ребра были разного цвета?

Выпуклый n-угольник разрезали на треугольники непересекающимися диагоналями. а)◦ Докажите, что треугольников получилось на один больше, чем проведённых диагоналей. б)◦ Докажите, что хотя бы у двух треугольников по две стороны лежат на границе многоугольника. в)⋆ Сколькими способами можно так разрезать многоугольник? Вершины занумерованы: разрезания, отличающиеся поворотом, считаются различными.

Хозяйка испекла пирог и знает, что придут либо ровно p, либо ровно q гостей, причём p и q взаимно просты. На какое наименьшее число не обязательно равных кусков можно разрезать пирог, чтобы в любом случае разделить его между гостями поровну?