Деревья

Определить, является ли неориентированное дерево плоским, эйлеровым, полуэйлеровым, гамильтоновым графом? Найти его хроматическое число.

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

Доказать, что в неориентированном дереве $\mathfrak {T}=(V, E)$, содержащем хотя бы одно ребро, количество висячих вершин равняется $2+\sum_{v \in V_{2}}(\operatorname {deg} v-2)$, где $V_{2}-$ множество невисячих вершин.

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

Доказать, что в неориентированном дереве существует вершина, через которую проходят все максимальные простые пути.

Доказать лемму 76 на стр. 221.

Доказать теорему 77 на стр. 223 в обратную сторону.

Пусть $\mathfrak {T}=(V, E)$ — это ориентированное дерево с корнем $v_{0} \in V$. Определим для каждой вершины $v \in V$ подграф $\mathfrak {T}_{v}=\left(V_{v}, E_{v}\right)$ следующим образом: $V_{v}$ — это множество вершин, достижимых из $v$ в $\mathfrak {T}$, а $E_{v}$ — это множество рёбер из $E$, оба конца которых входят в $V_{v}$. Доказать, что

Пусть $\leqslant$ — отношение частичного порядка на конечном множестве $V$, которое обладает следующими двумя свойствами:

Пусть $\mathfrak {T}=(V, E)$ — ориентированное дерево, а $x \leqslant y$ означает, что вершина $y$ достижима из вершины $x$. Доказать, что $\leqslant$ — отношение нестрогого частичного порядка на $V$, удовлетворяющее свойствам (а) и (б) из предыдущей задачи.

Пусть $\mathfrak {G}=(V, E)$ — это ориентированный граф с не менее чем двумя вершинами. Доказать, что граф $\mathfrak {G}$ является (ориентированным) деревом тогда и только тогда, когда в $\mathfrak {G}$ нет циклов, имеется один исток $r$, а в каждую из остальных вершин $v \in V \backslash \left\{ r\right\}$ входит ровно одно ребро.

Для множества вершин $V=\left\{ v_{1}, \ldots , v_{n}\right\}$ определить, сколько существует неориентированных деревьев, в которых

Пусть корень ориентированного дерева $\mathfrak {T}$ имеет пять сыновей, а каждая из остальных внутренних вершин имеет три или четыре сына, при этом количество вершин с тремя сыновьями вдвое больше количества вершин с четырьмя. Сколько всего вершин и рёбер в $\mathfrak {T}$, если известно, что количество его листьев равно $26? *$

Пусть $\mathfrak {F}=\left(\mathfrak {T}_{1}, \ldots , \mathfrak {T}_{n}\right)$ — лес деревьев. Доказать, что по последовательности $P=\left(\operatorname {PRF}\left(\mathfrak {T}_{1}\right), \ldots , \operatorname {PRF}\left(\mathfrak {T}_{k}\right)\right)$ можно однозначно восстановить лес $\mathfrak {F}$. Доказать аналогичное утверждение для суффиксного обхода.

Доказать по индукции, что в каждом бинарном дереве количество $n$ вершин с двумя сыновьями на единицу меньше количества $\ell$ листьев.

Сколько листьев и вершин есть в полном бинарном дереве высоты $h$?

Построить дерево и ациклический ориентированный граф, представляющие следующую арифметическую формулу

Сколько вершин удалось сократить?

Построить дерево, представляющее следующую логическую формулу

Для полученного дерева построить префиксный, суффиксный и инфиксный обходы (для вершин с отрицаниями единственного сына считать правым).