Деревья

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

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

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

Доказать, что если в неориентированном дереве имеется ровно две висячих вершины, то оно является «линией».

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

Центром неориентированного графа $\mathfrak {G}$ называется вершина $v$, для которой длина максимального пути от неё до остальных вершин минимальна. Доказать, что в дереве

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

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

Доказать следующее утверждение двумя способами: если в неориентированном дереве $\mathfrak {T}=(V, E)$ имеется вершина $v$ степени $d>1$, то в нём имеется по крайней мере $d$ висячих вершин.

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

Пусть $\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\}$ входит ровно одно ребро.

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

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

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

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

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

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

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

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

Определить префиксный, суффиксный и инфиксный обходы дерева $\mathfrak {T}_{1}$, изображённого на рис. 12 на следующей странице, считая, что рёбра, исходящие из одной вершины, пронумерованы слева направо.

Рис. 12: Дерево \mathfrak {T}_{1}.

Определить префиксный и суффиксный обходы дерева $\mathfrak {T}_{2}$, изображённого на рис. 13 на противоположной странице, считая, что рёбра, исходящие из одной вершины, пронумерованы слева направо.

Рис. 13: Дерево \mathfrak {T}_{2}.

Пусть $(x, z, u, v, /,-, \times , y, z,-, x, y,+, \times ,+)$ — это суффиксный обход дерева арифметической формулы, составленной из переменных $x, y, z, u, v$ и знаков операций,,$+- \times , /$. Восстановить это дерево и формулу.