\ListokName{16. Деревья}

\shapkaUstnoB

\vspace{.2cm}
 
\textit{Дерево} --- связный граф без циклов.
 
\zp Два графа \textit{изоморфны}, если вершины одного можно занумеровать вершинами другого так, что рёбра перейдут в рёбра. Сколько существует попарно неизоморфных деревьев на шести вершинах? Нарисуйте их.
 
\zp Вершину степени 1 называют \textit{висячей}, или \textit{листом}. Докажите, что в дереве, у которого больше одной вершины, есть висячая вершина, и что таких вершин хотя бы две.
 
\zp Докажите, что в дереве с $n$ вершинами ровно $n-1$ ребро.
 
\zp Сколько рёбер в \textit{лесу} --- графе без циклов --- с $n$ вершинами и $k$ компонентами связности?
 
\zp Докажите, что из любого связного графа можно выкинуть часть рёбер так, чтобы получилось дерево с теми же вершинами. Такое дерево называют \textit{остовом}, или \textit{остовным деревом}, графа.
 
\zp В графе $n$ вершин и $m$ рёбер. Докажите, что компонент связности в нём не меньше $n-m$.
 
\zp Пусть граф связен и имеет $n$ вершин. Докажите, что следующие свойства равносильны:
\begin{itemize}
\item рёбер ровно $n-1$;
\item при удалении любого ребра граф перестаёт быть связным;
\item в графе нет циклов;
\item любые две вершины соединены ровно одним путём.
\end{itemize}
Таким образом, любое из этих свойств можно взять за определение дерева.
 
\zp Даны $n$ различных по весу камней и весы, позволяющие сравнить любые два из них. Какое наименьшее число взвешиваний нужно, чтобы наверняка найти самый тяжёлый камень?
 
\zp Сколько рёбер может быть в несвязном графе с $n$ вершинами?
 
\zp Докажите, что из любого связного графа, в котором больше одной вершины, можно удалить вершину вместе со всеми выходящими из неё рёбрами так, что граф останется связным.
 
\zp В связном графе 10 вершин и 19 рёбер. Докажите, что в нём найдётся цикл, после уничтожения всех рёбер которого граф не потеряет связность.
 
\zp В стране 100 городов, некоторые из которых соединены авиалиниями. Известно, что из любого города можно долететь до любого другого, возможно с пересадками. Докажите, что можно побывать в каждом городе, совершив не более 198 перелётов.
 
\zp Дано дерево с $n$ вершинами. Сколькими способами можно раскрасить его вершины в $k$ цветов так, чтобы концы любого ребра были разного цвета?
 
\z Выпуклый $n$-угольник разрезали на треугольники непересекающимися диагоналями.
\lettcirc Докажите, что треугольников получилось на один больше, чем проведённых диагоналей.
\lettcirc Докажите, что хотя бы у двух треугольников по две стороны лежат на границе многоугольника.
\lettstar Сколькими способами можно так разрезать многоугольник? Вершины занумерованы: разрезания, отличающиеся поворотом, считаются различными.
 
\zpstar Хозяйка испекла пирог и знает, что придут либо ровно $p$, либо ровно $q$ гостей, причём $p$ и $q$ взаимно просты. На какое наименьшее число не обязательно равных кусков можно разрезать пирог, чтобы в любом случае разделить его между гостями поровну?