16ℵ. Деревья

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

(Теорема Кэли)Докажите, что у полного графа сnвершинами nn−2 остовных деревьев. Далее в листке изложены два доказательства этого факта. Можете сначала попробовать доказать его самостоятельно, но не расстраивайтесь, если не получится.

Сколько есть ориентированных графов с множеством вершинV таким, что|V| = n, в которых из каждой вершины выходит ровно одна стрелка?

Опишите, как выглядят ориентированные графы, в которых из каждой вершины выхо- дит по одной стрелке.1

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

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

Зафиксируем множество вершинV, его подмножество∅̸= M⊂ V и ориентированный путь X, проходящий ровно по вершинам изM. Зафиксируем также графG с множеством вершинV, в котором из каждой вершины множестваM выходит и входит ровно одна стрелка, а из остальных вершин стрелок не выходит. Постройте биекцию между • позвоночными с множеством вершинV и позвоночником X; • ориентированными графами с множеством вершин V, в которых из каждой вершины выходит ровно одна стрелка, содержащимиG в качестве подграфа2, и такими, что в циклах лежат ровно вершины из M. 1Возможно, эта задача будет для вас слишком сложной и расплывчатой. В таком случае обсудите её с принимающим: расскажите про ваши идеи, попросите задать более конкретные вопросы, или решайте следующую задачу. Также можно прочитатьусловиеследующейзадачи,когдавырешитеэту,чтобыпроверить,чтовыустановилито,чтотребуется.Кстати, этот листок сложный, поэтому абсолютно нормально просить принимающего о помощи (этот листок сделал Даня, можно, в частности, спрашивать его). Впрочем, в любом листке абсолютно нормально просить принимающего о помощи. 2Подграф графа H здесь — граф, который получится, если стереть вH некоторые (возможно, ни одного) рёбра.

Докажите, что ориентированных графов, в которых из каждой вершины выходит по одной стрелке, с конечным множеством вершинV, столько же, сколько позвоночных с множеством вершин V.

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

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