Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день. Граф как математический объект оказался полезным во многих теоретических и практических задачах. Наверное, дело в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. Этот курс служит введением в современную теорию графов. Мы, конечно, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов. Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики. Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Доказательство формулы
Loading...
En provenance du cours de Moscow Institute of Physics and Technology
Теория графов
287 notes
À partir de la leçon
Формула Кэли. Унициклические графы. Эйлеровы циклы
На этой неделе мы перечислим все деревья. Для этого нам потребуется перенять опыт древних по подсчету баранов (или козлов). Не остановившись на этом, перечислим и все леса и унициклические графы. Затем мы вернемся к задаче о Кёнигсбергских мостах и получим полное решение этого вопроса.
Rencontrer les enseignants
Андрей Райгородскийпрофессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Андрей Купавскийкандидат физико-математических наук
Кафедра дискретной математики ФИВТ МФТИ
Давайте доказывать именно теорему, а не следствие из нее.
А тут доказательство простое на самом деле, не очень сложное.
Смотрите, как перечислить все унициклические графы на 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, ...,
r принадлежат все разным деревьям, разным компонентам.
[ШУМ] Иными словами,
если мы хотим в итоге все-таки сосчитать, сколько существует унициклических
графов на n вершинах, мы действительно должны просуммировать по
длине цикла количество способов зафиксировать этот цикл.
Давайте я это еще раз здесь напишу.
Значит, сумма по r от 3 до n, C из n по r × (r – 1)!/2.
И вот это количество надо еще умножить на количество вот таких вот лесов,
которые здесь описаны, на количество лесов,
каждый из которых состоит ровно из r компонент, из r деревьев,
который имеет n вершин, естественно, и который к тому же обладает тем свойством,
что вот эти конкретные выделенные вершины принадлежат разным деревьям.
Давайте это обозначим F (n, r).
И, собственно, лемма финальная в этом месте состоит в том,
о чём любой слушатель, без сомнения, догадался: F (n,
r) это и есть r*n в степени n − 1 − r.
Ну или n − r − 1.
Описался просто, не страшно.
Смотрите, вот что такое F (n, 1).
Ну это количество лесов, которые состоят из одного дерева.
Лес, состоящий из одного дерева — это просто дерево, то есть это количество
деревьев, ну все остальные условия совершенно понятны, на n вершинах.
Ну и понятно, что если дерево на n вершинах, то вершина 1 ему принадлежит.
То есть то, что F (n, 1) = n в степени n − 2,
это очевидный факт, который мы с вами доказали...
Ну очевидный, конечно, по модулю теоремы Кэли,
которую мы с вами аккуратно доказали с помощью кодов Прюфера.
И он прекрасно согласуется с этой формулой, потому что, смотрите,
если сюда подставить вместо r единицу, то, конечно,
вы получите n в степени n − 2 и будете в героях.
Так вот, эта лемма
в общем случает доказывается абсолютно также, как доказывается теорема Кэли.
Нужно рассматривать чуть-чуть модифицированное кодирование Прюфера.
С баранами, с камнями всё то же самое.
Вот. Всегда в этом месте очень прошу слушателей
самостоятельно разобраться в этом, потому что это очень хорошо помогает осознать,
как на самом деле устроено кодирование Прюфера.
То есть это некоторое упражнение,
которое предлагается слушателям ну вот в том числе для того,
чтобы они лучше осознали, как кодирование Прюфера доказало нам вот эту формулу.
То есть понять эту формулу, переосмыслить её ещё разок и применить очень
похожую процедуру для доказательства леммы.
И вот когда вы сами докажете эту лемму,
то в совокупности вы вот эту формулу и получите.
То есть вместо F (n, r) здесь будет стоять r на n в степени n − r − 1,
r загонится сюда, и теорема будет доказана.
Ну а я, наверное, на этом успокоюсь.
Единственное, что я скажу, последнее, это то, что, конечно,
человечество не остановилось на подсчёте деревьев, и унициклических графов.
Естественная следующая задача это посчитать формулу...
Давайте вот так обозначим.
Для количества графов связных, у которых n вершин и n + k рёбер.
То есть, если k = −1...
Минус единице, то C (n, n − 1)...
C (n, n − 1) — это в точности t с индексом n — количество деревьев.
Если k = 0, то C (n,
n) — это в точности количество унициклических графов на n вершинах.
Ну а дальше это какие-то более сложные конструкции, которые, тем не менее,
очень важны для самых разных приложений.
Ну я не буду вас грузить теми формулами, которые там были получены, но замечу так
вот просто для того, чтобы было интересно, что практически исчерпывающее
решение задачи при разных k было получено только в начале 90-х годов 20-го века.
Такой совершенно удивительный факт.
Вроде классическая задача Кэли, но вот в итоге она выросла в проблему,
которую более или менее закрыли только в начале 90-х.
То есть совсем недавно.
Ну так просто, если кому интересно, C (n, n + 1) асимптотически
равно 5/24 * n в степени n + 1.
Вот такая вот формула.
То есть их всё больше и больше, но вот коэффициенты по-прежнему загадочные.
Там какой-то корень из π на 8, здесь 5/24.
Ну и можно написать общую формулу асимптотическую,
но этого я уже делать не буду, чтоб просто не перегружать.
А так вообще вот, повторяю, очень красивая, очень интересная задача,
и ей занимаются до сих пор.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
