Давайте доказывать именно теорему, а не следствие из нее.
А тут доказательство простое на самом деле, не очень сложное.
Смотрите, как перечислить все унициклические графы на n вершинах?
Ну, наверное, прежде всего надо задать цикл.
Давайте прежде всего выберем тот цикл единственный,
который присутствует в будущем унициклическом графе.
Прежде всего
выберем цикл,
вокруг которого, повторяю, будет строится наш унициклический граф.
Тот единственный цикл, который в нем появится.
Хорошо.
Что значит выбрать цикл?
Сначала, наверное, надо выбрать его длину.
Ну давайте обозначим буквой r длину этого цикла.
Длина этого цикла.
Ну все ж понимают,
что у простого цикла меньше трех вершин быть никак не может.
Если цикл простой, то у него, конечно, хотя бы 3 вершины: треугольник, там,
четырехугольничек такой и так далее.
Поэтому ясно, что r — это число, которое меняется в пределах от 3 до n.
Буквально так же, как вот в этой формуле.
То есть фактически это суммирование, это просто суммирование по возможным
величинам длин цикла, который будет в нашем унициклическом графе.
Дальше, вот если мы зафиксировали длину цикла в нашем унициклическом графе,
то сколько существует способов выбрать сам этот цикл?
Ну смотрите: C из n по r,
вот эта самая C из n по r, которая тут написана,
— это число способов выбрать
r вершин для цикла.
То есть прежде чем мы зафиксируем цикл, мы сначала скажем,
что его длина — это число r, потом скажем, что C из n по r — это количество способов
зафиксировать r вершин из тех исходных n, которые есть в нашем распоряжении.
Но когда мы зафиксируем эти r вершин,
на самом деле мы ведь не выберем цикл однозначно.
Смотрите, пример: вот есть простой цикл 1,
2, 3, 4, а есть другой простой
цикл 1, 3, 2, 4.
Это разные простые циклы в том известном нам смысле,
в каком разными были деревья в только что рассказанной теореме Кэли.
Почему?
Потому что здесь, например, есть ребро 1, 3, а в этом цикле его нет.
То есть даже когда мы зафиксировали C из n по r способами какие-нибудь
r вершины для цикла, дальше упорядочить эти вершины так,
чтобы они образовали цикл, можно кучей различных способов.
Ну сколькими?
Ну про это есть известная школьная комбинаторная задача, вернее,
две задачи даже.
А именно — одна задача формулируется так: сколько существует хороводов,
которые можно составить из n девушек?
А другая задача спрашивает, сколько существует ожерелий,
которые можно составить из n различных драгоценных камней?
Оказывается, что это две немножко разные задачи,
потому что хоровод имеет некое направление, его переворачивать нельзя.
А ожерелье можно еще перевернуть.
Ну, короче, смысл такой.
Вот у нас есть числа от 1 до r, и мы эти числа хотим упорядочить в цикл.
Ясное дело, что r!
— это количество всех возможных перестановок.
Но если мы возьмем какую-нибудь перестановку, например, вот такую,
как здесь нарисована, а дальше то, что называется, начнем ее смещать по циклу,
то есть будем рассматривать перестановки 2, 3,
..., r, 1; 3, 4, ..., r, 1,
2; и так далее (всего таких перестановок, циклических сдвигов,
у нас будет r штук), то всякий раз мы будем получать один и тот же цикл.
Перестановки разные, а цикл,
который получается вот такими циклическими сдвигами, он, конечно, один и тот же.
Они в цикл замыкаются совершенно одинаково.
Ну и вот то, что я говорил про возможность перевернуть или невозможность перевернуть
— это как раз утверждение о том, что если мы еще вот так вот упорядочим...
Вот досюда у нас r.
Но если мы еще и вот так упорядочим и дальше снова начнем как вот
здесь сдвигать по циклу, то у нас получится еще r последовательностей,
каждое из которых задает один и тот же цикл длины r.
Поэтому r!
нужно поделить на 2r и получить тем самым (r – 1)!/2.
Помните, я сначала (вот здесь оно еще видно,
затерто) написал (r – 1)!/2, а тут отдельно умножил на r.
Ну вот сейчас увидите, это действительно так и будет.
То есть коль скоро мы зафиксировали r как длину нашего простого цикла,
вокруг которого строится унициклический граф, затем мы должны зафиксировать
C из n по r способами одним из C из n по r способов те самые r вершин,
на которых будет цикл, и для каждого такого способа существует (r –
1)!/2 вариантов как зациклить вот эти r вершин.
Итого, конечно, мы получим произведение числа C из n по r на (r – 1)!/2.
Что ж такое вот эта вот загадочная величина r × n в степени (n – r – 1),
которая вот здесь до затирания присутствовала?
И коль скоро поймем мы эту самую величину, мы, конечно,
завершим доказательство теоремы.
Все очень просто.
Смотрите: вот мы нашли какой-то цикл.
Всё, мы его зафиксировали одним из вот стольких
способов — C из n по r умножить на (r – 1)!/2.
Зафиксировали, ну и давайте просто не ограничивая общности, опять же, считать,
что его вершины — это числа 1, 2, 3, ..., r.
Вот такой вот цикл какой-то, в каком-то порядке вершины расставлены,
мы зафиксировали.
Как теперь достроить этот цикл до унициклического графа?
Что надо сделать, чтобы получился унициклический граф?
Понятно.
Надо сюда приляпать какое-нибудь дерево, сюда приляпать какое-нибудь дерево,
сюда какое-нибудь, сюда какое-нибудь и так далее, так в каждую вершину.
Ну, может быть, не надо ничего приляпывать.
Может быть, какая-то вершина не будет содержать на себе никакого дерева,
кроме себя самой, но это ведь тоже дерево — зародыш такой, одна вершинка, семечко.
Вот.
То есть понятно, что если граф унициклический, и мы удалим из этого
графа все ребра того самого цикла, который в нем единственный присутствует, то то,
что останется в результате удаления, будет лесом.
Давайте это зафиксируем.
Если удалить из унициклического
графа его единственный простой цикл,
его единственный простой цикл,
то останется просто лес,
останется лес.
Но, заметьте, не абы какой лес, а, конечно же,
лес, имеющий r компонент связности, то есть состоящий из r деревьев,
состоящий из r деревьев,
некоторые из которых могут быть из одной вершины, это не жалко.
Мало того что он состоит
из r деревьев, у него в общей сложности,
конечно, n вершин, потому что наш исходный унициклический граф имел n вершин.
...из r деревьев, имеющий n вершин,
n вершин и такой к тому же,
что вершины 1,
2, 3, ..., r принадлежат разным деревьям.
Вот у него всего r деревьев, и вершина 1 принадлежит одному дереву,
вершина 2 — совершенно другому, 3 — третьему и так далее.
Ну это вот все из картинки совершенно понятно.
И такой, что вершины 1, 2, ...,