Деревья

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

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

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

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

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

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

Лемма 76: Пусть в неориентированном дереве $\mathfrak {T}=(V, E)$ выбрана произвольная вершина $v \in V$. Для каждой вершины $u$ обозначим с помощью $n(u)$ минимальную длину пути из $v$ в $u$. Для каждого неориентированного ребра $(u, w)$ определим его направление от $u$ к $w$, если $n(u)<n(w)$. Тогда полученный граф будет ориентированным деревом с корнем $v$.

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

Теорема 77: Определения ориентированных деревьев 93 (стр. 221) и 94 (стр. 222) эквивалентны.

Определение 93 (Ориентированное дерево): ориентированный граф $\mathfrak {T}=(V, E)$ называется (ориентированным) деревом, если 1) в нём есть ровно один исток $r \in V$, он называется корнем дерева; 2) в каждую из остальных вершин входит ровно по одному ребру; 3) все вершины достижимы из корня.

Определение 94 (Ориентированное дерево, индуктивное определение): ориентированный граф является деревом в следующих случаях. 1) Любой граф $\mathfrak {T}_{0}=(V, E)$ с единственной вершиной $V=\left\{ v\right\}$ и пустым множеством рёбер $E=\emptyset$ является деревом; вершина $v$ называется корнем этого дерева. 2) Пусть графы $\mathfrak {T}_{1}=\left(V_{1}, E_{1}\right), \ldots , \mathfrak {T}_{k}=\left(V_{k}, E_{k}\right)$ являются деревьями с корнями $r_{1} \in V_{1}, \ldots , r_{k} \in V_{k}$ соответственно, множества вершин $V_{i}$, $i=1, \ldots , k$, попарно не пересекаются, $r_{0}$ — новая вершина: $r_{0} \notin V_{i}$, $i=1, \ldots , k$. Тогда следующий граф $\mathfrak {T}=(V, E)$ тоже будет деревом с корнем $r_{0}$: $V=\left\{ r_{0}\right\} \cup \bigcup_{i=1}^{k} V_{i}$, $E=\left\{ (r_{0}, r_{i}): i=1, \ldots , k\right\} \cup \bigcup_{i=1}^{k} E_{i}$.

«В обратную сторону» означает: если граф $\mathfrak {T}$ удовлетворяет определению 94, то для него выполняются условия 1)-3) определения 93 — доказывается индукцией по построению из определения 94.

Пусть $\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$?

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

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

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

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