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

\shapkaUstnoG

\vspace{-.9cm}


\begin{center}
  \Large  \textit{Теорема Кэли}
\end{center}

\textit{Лес} --- граф без циклов.

\textit{Дерево} --- связный лес.

\textit{Лист} --- вершина степени 1.

\textit{Ориентированный граф} --- граф, на каждом ребре которого нарисована стрелка в одну из двух сторон. В нашем листке разрешены петли и пары вершин, между которыми стрелки есть в обе стороны.

\textit{Полный граф} --- неориентированный граф, в котором каждые две вершины соединены ребром.

\textit{Остовное дерево} графа --- дерево, которое получится из этого графа, если стереть некоторые рёбра.

Ориентированный граф $G$ называется \textit{слабо связным}, если неориентированный граф, который получится из графа $G$, если стереть стрелки на рёбрах, связен.

\setcounter{z}{-2}

\zncirc Докажите, что в любом связном графе есть остовное дерево.
\lettcirc Докажите, что связный граф на $n$ вершинах является деревом тогда и только тогда, когда в нём $n-1$ ребро.
\lettcirc Докажите, что в связном графе на $n$ вершинах по крайней мере $n-1$ ребро.

\zpstar \textit{(Теорема Кэли)} Докажите, что у полного графа с $n$ вершинами $n^{n-2}$ остовных деревьев. Далее в листке изложены два доказательства этого факта. Можете сначала попробовать доказать его самостоятельно, но не расстраивайтесь, если не получится.

\zp Сколько есть ориентированных графов с множеством вершин $V$ таким, что $|V|=n$, в которых из каждой вершины выходит ровно одна стрелка?
\zp Опишите, как выглядят ориентированные графы, в которых из каждой вершины выходит по одной стрелке.  \footnote{Возможно, эта задача будет для вас слишком сложной и расплывчатой. В таком случае обсудите её с принимающим: расскажите про ваши идеи, попросите задать более конкретные вопросы, или решайте следующую задачу. Также можно прочитать условие следующей задачи, когда вы решите эту, чтобы проверить, что вы установили то, что требуется. Кстати, этот листок сложный, поэтому абсолютно нормально просить принимающего о помощи (этот листок сделал Даня, можно, в частности, спрашивать его). Впрочем, в любом листке абсолютно нормально просить принимающего о помощи.}

\z Рассмотрим слабо связный ориентированный граф, в котором из каждой вершины выходит ровно одна стрелка.
\lett Рассмотрим множество $M$ вершин $v$ таких, что из любой вершины графа можно попасть в $v$, двигаясь по стрелкам. Докажите, что все вершины из $M$ образуют один ориентированный цикл.
\lett Сотрём все рёбра из этого цикла. Докажите, что граф распадётся
на деревья, в каждом из которых ровно одна вершина из $M$ и все стрелки направлены в сторону этой вершины.

% \zp Рассмотрим ориентированный граф, в котором из каждой вершины выходит ровно одна стрелка. Пусть в нём $k$ вершин, лежащих в циклах. Сотрём все рёбра, выходящие из этих вершин. Сколько есть способов добавить рёбра в получившийся граф так, что опять получится ориентированный граф, в котором из каждой вершины выходит ровно одна стрелка, и в циклах лежат те же $k$ вершин?

% \zp Назовём \textit{хребтовым деревом} неориентированное дерево, в котором выделен ориентированный путь (\textit{хребет}), проходящий по рёбрам. Он может состоять из одной вершины (тогда ориентации нет). Сотрём все рёбра хребта в хребтовом дереве, в хребте которого $k$ вершин. Сколько есть способов дорисовать получившийся граф до хребтового дерева с тем же множеством вершин хребта, что и старое хребтовое дерево?
\zp Докажите, что ориентированных графов, в которых из всех вершин выходит и входит по одной стрелке с конечным множеством вершин $V$, столько же, сколько ориентированных путей с множеством вершин $V$.


Назовём \textit{позвоночным} неориентированное дерево, в котором выделен ориентированный путь (\textit{позвоночник}), проходящий по рёбрам. \textit{Ориентированный путь} --- путь, в которым на рёбрах стоят стрелки так, что в одном из двух направлений можно пройти по стрелкам. Позвоночник может состоять из одной вершины, тогда ориентации нет. 

\zp Зафиксируем множество вершин $V$, его подмножество $\varnothing\ne M\subset V$ и ориентированный путь $X$, проходящий ровно по вершинам из $M$. Зафиксируем также граф $G$ с множеством вершин $V$, в котором из каждой вершины множества $M$ выходит и входит ровно одна стрелка, а из остальных вершин стрелок не выходит. Постройте биекцию между
\vspace{-.2cm}
\begin{itemize}
\item позвоночными с множеством вершин $V$ и позвоночником $X$;
\vspace{-.2cm}
\item ориентированными графами с множеством вершин $V$, в которых из каждой вершины выходит ровно одна стрелка, содержащими $G$ в качестве подграфа\footnote{\textit{Подграф} графа $H$ здесь --- граф, который получится, если стереть в $H$ некоторые (возможно, ни одного) рёбра.}, и такими, что в циклах лежат ровно вершины из $M$.
\end{itemize}
\vspace{-.2cm}
\zp Докажите, что ориентированных графов, в которых из каждой вершины выходит по одной стрелке, с конечным множеством вершин $V$, столько же, сколько позвоночных с множеством вершин $V$.

\zpcirc Докажите, что у полного графа с $n$ вершинами $n^{n-2}$ остовных деревьев.

\textit{Код Прюфера} сопоставляет дереву, вершины которого пронумерованы числами 1 до 
$n$ последовательность из $n-2$ чисел. Будем последовательно удалять из дерева вершины, пока не останутся только две вершины. Каждый раз будем выбирать лист с наименьшим номером и записывать в код номер вершины, с которой он соединён.

\zp Докажите теорему Кэли с помощью кода Прюфера.