О.Б. Лупанов - Курс лекций по дискретной математике, страница 2

А теперьсопоставим каждой расстановке перегородок набор из нулей и единиц: пусть нулю соответствует перегородка,а единице — шарик. Тогда всякая расстановка перегородок кодируется строкой из n − 1 + k нулей и единиц, вкоторой ровно k единиц. Осталось посчитать такие наборы. Это легко: достаточно расставить, например, единицы, а нули сами найдут своё место. Очевидно, что количество способов расставить единицы — это Ckn+k−1 .Второе равенство сразу следует из симметричности биномиальных коэффициентов. Замечание.

Из определения числа сочетаний с повторениями ясно, что количество монотонных функцийf : Mp → Mq — это в точности количество сочетаний с повторениями CCpq .1.1.2. ОценкиПолучим оценки для числа n! (они нам потребуются в дальнейшем). В качестве очень грубой верхней оценкиможно использовать оценкуn! 6 nn .(6)Утверждение 1.5. Справедливо неравенствоn! > n n8.(7) Для n 6 8 неравенство очевидно, потому что при таких nсправа стоит число, не превосходящее 1. Пустьтеперь n > 8. Будем доказывать по индукции. Положим k := n2 .

k kn n−k n k n n−knnn! = 1 · 2 · 3 · . . . · k · (k + 1) · . . . · n >·>·= 4k n−k .821622 ·2!Поясним переход, отмеченный знаком «!». Для оценки первой группы множителей пользуемся предположениеминдукции, а вторую группу множителей оцениваем снизу меньшим из сомножителей в соответствующей степени.Осталось оценить показатель степени: 3k + n 6 3n при n > 8, поэтому всё доказано. Что касается чисел сочетаний с повторениями и без повторений, то для них мы чаще всего будем использоватьтакие оценки:Ckn 6 2n , CCkn 6 2n+k−1 .(8)Они очевидным образом следуют из определения числа сочетаний.Надо сказать, что, хотя это оценки достаточно грубы, нам их вполне будет хватать.

Вообще в этом курсе нампридётся бороться за константы один-единственный раз — при доказательстве асимптотики сложности схем изфункциональных элементов.1.2. Теория графов1.2.1. Графы. Правильная реализация. Критерий Понтрягина – КуратовскогоОпределение. Пусть задано множество V = {v1 , . . . , vp , . . .} и множество E = {e1 , . . . , eq , . . .}. Пусть каждому элементу e ∈ E поставлена в соответствие неупорядоченная пара элементов {v, w} множества V (при этомможет быть так, что v = w).

В этом случае говорят, что задан граф с множеством вершин V и множествомрёбер E. Вершины v и w, соответствующие ребру e, называются концами ребра e. Этот факт удобно записывать,например, так: Ver(e) = {v, w} (от англ. vertex — вершина).Определение. Вершина называется изолированной, если в графе нет ребра с концом в этой вершине. Еслидва ребра соединяют одну и ту же пару вершин, то говорят, что это кратные (параллельные) рёбра. Вершинаназывается концевой, если из неё выходит только одно ребро.Замечание.

Если в определении графа мы потребуем, чтобы пара вершин, соответствующих ребру, былаупорядоченной, мы получим определение ориентированного графа.5Всякий граф можно реализовать в евклидовом пространстве. Отметим на плоскости столько различныхточек, сколько вершин в нашем графе, а потом соединим кривыми те вершины, которые соединены рёбрами(эти кривые тоже будем называть рёбрами).

При этом может получиться так, что некоторые рёбра пересекаются.Определение. Говорят, что граф допускает правильную реализацию, если можно так расставить вершиныи так провести рёбра, что любые два ребра не будут иметь общих точек (кроме, быть может, самих вершин).Утверждение 1.6. Всякий граф, у которого не более континуума вершин и не более континуума рёбер,допускает правильную трёхмерную реализацию. Рассмотрим произвольную прямую в R3 и отметим на ней все вершины графа.

Теперь рассмотримпучок плоскостей, проходящих через эту прямую. Их там много, поэтому для каждого ребра можно выбратьсвою плоскость. После этого всё тривиально — соединяем вершины дугой окружности, лежащей в плоскости,соответствующей данному ребру. Эти дуги не будут пересекаться, потому что разным рёбрам соответствуютразные плоскости. Определение. Подграфом графа (V, E) называется такая пара (V ′ , E ′ ), что V ′ ⊂ V , E ′ ⊂ E, и множествоконцов рёбер множества E ′ содержится в множестве V ′ .Определение.

Будем называть графы Γ(V1 , E1 ) и Γ(V2 , E2 ) изоморфными, если существуют такие биекциимежду их рёбрами и между вершинами, что соответствующие рёбра соединяют соответствующие вершины.Иначе говоря, если ϕ : V1 → V2 , а ψ : E1 → E2 — биекции, то для всех e ∈ E1 должно быть выполнено ϕ(Ver(e)) == Ver(ψ(e)).Введём операцию подразбиения ребра: ставим где-нибудь на ребре (но не в концах) ещё одну вершину, и унас получается новый граф, у которого вершин на одну больше и рёбер на одно больше (то есть большое реброисчезает, остаётся две «половинки»).Если в графе подразбить несколько рёбер, то будем называть новый граф подразбиением исходного.Определение.

Будем говорить, что Γ1 и Γ2 гомеоморфны, если существуют их подразбиения, изоморфныемежду собой.Определение. Граф K5 — это полный граф, построенный на 5 вершинах (рис. 1).Рис. 1. Граф K5Определение. Граф K3,3 — это граф, показанный на рис. 2.Рис. 2. Граф K3,3Справедливо следующее утверждение, которое мы доказывать не будем.Теорема 1.7 (Критерий Понтрягина – Куратовского). Конечный граф допускает планарную правильную реализацию тогда и только тогда, когда не содержит в себе подграфов, гомеоморфных K3,3 и K5 .Следующие несколько определений интуитивно ясны, мы не будем давать их слишком формально.

Все и такпонимают, чего хочется от того или иного определения. Они здесь написаны скорее для того, чтобы знать, чтобыло на лекции.Определение. Путь в графе Γ(V, E) — это упорядоченный набор рёбер, в котором конец любого предыдущего ребра совпадает с началом следующего.Определение. Цикл — это путь, у которого начало и конец совпадают.Определение. Граф называется связным, если из любой вершины в любую существует путь.

По определению, граф из одной вершины считается связным.Определение. Дерево — это связный граф без циклов.Определение. Дерево с корнем — это дерево, у которого помечена одна вершина.Изоморфизм деревьев с корнями — это изоморфизм графов, при котором корень переходит в корень. Пустьδ(q) — количество неизоморфных деревьев с q рёбрами, а δ ∗ (q) — количество неизоморфных деревьев с корнямис q рёбрами.

Очевидно, что δ(q) 6 δ ∗ (q).6Утверждение 1.8. В любом конечном связном графе существует подграф, содержащий все вершины исходного графа и являющийся деревом. Будем разрезать циклы, пока их не останется. При разрезании цикла связность не нарушается. Поскольку рёбер конечное число, процесс когда-нибудь остановится. Следствие 1.1. Всякий связный граф можно получить из дерева достройкой рёбер.Утверждение 1.9. Если в дереве p вершин, то в нём p − 1 ребро. Докажем индукцией по числу вершин.

Найдём концевую вершину и удалим её. При этом пропадёт ровноодна вершина и ровно одно ребро. Оставшийся граф тоже будет деревом с меньшим количеством вершин. 1.2.2. Оценки количества деревьев и графовНапомним обозначение Mq = {1, . . . , q}.Теорема 1.10. Имеет место оценкаδ ∗ (q) 6 4q .(9) Возьмём дерево и расположим его листья строго по ярусам, чтобы корень был в самом низу. Далеепронумеруем вершины номерами от 0 до q, идя слева направо, сверху вниз, то есть заметая ярус за ярусомслева направо. Ясно, что при такой нумерации корень получит номер q.

Теперь поставим в соответствие каждомутакому пронумерованному дереву некоторую монотонную функцию. Возьмём любую вершину (кроме корня) сномером k. Спустимся по ней на один шаг к корню. Мы попадём в вершину, в которой будет написано какое-точисло m. Тогда пусть наша функция в точке k + 1 принимает значение m.

Это будет функция, у которойобласть определения — множество Mq , а область значений содержится в множестве Mq . Легко проверить, чтоесли нам дана какая-нибудь монотонная функция , то по ней можно либо однозначно вырастить дерево, котороеей соответствует (точнее говоря, если вообще можно, то уж единственным образом). Действительно, возьмёмполный прообраз точки q. Его мощность — это в точности количество рёбер, которые растут от корня. Нарисуемих.

Далее, возьмём самую правую вершину, она получит номер q − 1. Снова берем прообраз, и так далее (еслипрообраз пуст, то это значит, что данная вершина является концевой). Затем переходим к следующей вершинев том же яруса, двигаясь справа налево. В итоге мы раскодируем всё дерево.Итак, мы устроили инъективное отображение из множества деревьев с корнями в множество монотонныхфункций f : Mq → Mq . А их количество мы знаем — это CCqq = Cq2q−1 6 22q−1 6 4q . Стало быть, различныхдеревьев с корнем и того меньше. Утверждение 1.11. Количество δ(q) неизоморфных деревьев с q рёбрами оценивается снизу: √ q13δ(q) > √·2 .32 2(10) Возьмём цепочку из t рёбер, в ней будет t + 1 вершина. Расположим эту цепочку горизонтально, и ксамой левой вершине прицепим 4 ребра, чтобы сделать её особой (см.