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

рис. 3).012tРис. 3. ДеревоК остальным вершинам будем цеплять деревья из двух рёбер, изображённые на рис. 4 (первое будем кодировать нулём, второе — единицей).Рис. 4. ПоддеревьяК каждой из t вершин можно прицепить любое из этих двух деревьев, поэтому количество таких деревьевполучается равным 2t . Они, очевидно, неизоморфны между собой. Посчитаем количество рёбер у такой конструкции. Скелет дерева состоит из t рёбер, к каждой из t вершин добавляется по 2 ребра, и ещё 4 ребрадобавлено к особой вершине. Таким образом, q = 3t + 4. Отсюда t = q−43 , поэтому √ q13δ(q) > 26 √·2 ,32 2что и требовалось доказать. 7(11)Замечание.

На самом деле можно доказать (Otter, 1948), что основание степени не меньше, чем 2.98.Доказательство Оттера существенно использует ТФКП.Утверждение 1.12. Количество γ(q) неизоморфных связных графов с q рёбрами. оценивается сверху:γ(q) 6 (Cq)q ,(12)C = const . У каждого ребра два конца. Можно считать, что количество вершин равно 2q, потому что во всякийграф можно добавить нужное количество изолированных вершин (полученные графы тоже будут неизоморфны,потому что у каждого из них найдётся по связной компоненте, не изоморфной никакой связной компонентедругого графа). Занумеруем вершины, тогда каждое ребро — это пара чисел.

Посчитаем количество различныхсортов рёбер. С учётом петель, их ровно CC22q = C22q+1 = q(2q + 1) =: s штук. Теперь у нас есть s сортов рёбер,и из них нужно (возможно, с повторениями, потому что графы могут иметь кратные ребра) выбрать q штук.Значит,(s + q − 1)q(s + q − 1)qγ(q) 6 CCqs = Cqs+q−1 66.(13)q qq!8Имеем s + q − 1 6 2q 2 + q + q 6 4q 2 . Отсюда получаем оценкуγ(q) 6(4q 2 )qqq q = (32q) ,(14)8то есть в качестве константы C можно взять C = 32.

Через γ(p, q) будем обозначать количество связных графов с p вершинами и q рёбрами.Утверждение 1.13. Для количества графов справедлива оценка сверху:γ(p, q) 6 pq−p · Aq+p ,(15)A = const . Рассмотрим произвольное p-вершинное дерево. Чтобы из p-вершинного дерева сделать q-рёберный граф,нужно дополнительно провести ещё q−(p−1) = q−p+1 =: k ребро. Из каждой вершины дерева можно выпуститькуда-то ребро (так, чтобы второй конец болтался в воздухе). Это можно сделать, очевидно, CCkp способами.Теперь эти концы надо как-то подсоединить к имеющимся вершинам.

Это можно сделать pk способами. Значит,существует не более CCkp ·pk способов получить из дерева граф. А поскольку количество деревьев не превосходит4p−1 , то в итоге имеем оценку!γ(p, q) 6 4p−1 · CCkp · pk = 4p−1 · Ckp+k−1 · pk = 4p−1 · Ckq · pk 6 4p−1 · 2q · pq−p · p 6 8p · 8q · pq−p .(16)В последней оценке, отмеченной «!», мы очень сильно всё загрубили: 4p−1 6 4p , p 6 2p и, наконец, 2q 6 8q .Таким образом, достаточно взять A = 8. До сих пор мы рассматривали только связные графы.

Теперь получим оценки для графов с заданнымколичеством компонент связности r. Количество таких графов мы будем обозначать символом γ(p, q, r).Утверждение 1.14. Имеет место неравенствоγ(p, q, r) 6 pq−p · B q+p+r . Граф Γ(p, q, r) состоит из r связных графов Γ(p1 , q1 ), . . . , Γ(pr , qr ), причём p =при фиксированных наборах {pi } и {qi } количество оценивается произведениемrYi=1(17)Pγ(pi , qi ) 6 Aq1 +p1 · pq11 −p1 · . . . · Aqr +pr · pqrr −pr 6 Aq+p · pq−p .pi , q =Pqi . Ясно, что(18)Итак, оценено каждое слагаемое.

Теперь нам нужно оценить количество таких слагаемых, то есть посчитатьколичество возможных наборов {pi } и {qi }. Разбиения набора p не допускают нулевых слагаемых (потому что вкаждом графе должна быть хотя бы одна вершина), а разбиения числа q допускают нулевые слагаемые (рёберможет не быть вовсе). Посмотрим, что значит разбить число p на r слагаемых, среди которых не может бытьнулевых. Напишем подряд p единиц и будем между ними расставлять r − 1 знак «+», то есть для расстановкиесть p−1 позиция, при этом два знака не могут стоять рядом.

Значит, в первом случае имеем дело с сочетаниямиp−1без повторений, а их Cr−1.p−1 6 2Во втором случае надо разбить число q на r слагаемых, среди которых могут быть нулевые. Будем тожерасставлять знаки «+» среди q, но теперь их можно ставить в самом начале и в самом конце, то есть позицийq + 1 штука, и кроме того, можно два плюса ставить подряд, то есть это сочетания с повторениями.

Поэтому8r−1q+r−1их количество равно CCq+1= Cr−1. Значит, количество разбиений заведомо не превосходит 2p−1 ·q+r−1 6 2q+r−1p+q+r262. Таким образом,γ(p, q, r) 6 Aq+p · pq−p · 2p+q+r 6 Ap+q+r · pq−p ,(19)поскольку A > 2. Таким образом, в качестве константы B можно взять A, но это не так важно.

1.2.3. Ориентированные графыОпределение. Назовём граф ориентированным, если каждому его ребру приписано направление.Определение. Ориентированный цикл — цикл, в которомвсе рёбра направлены в одну сторону, т. е. ко→, где первая вершина совпадает с последней.нечная последовательность ориентированных рёбер −vi−,−v−i+1Лемма 1.15. В любом конечном ориентированном графе без ориентированных циклов есть вершина, изкоторой рёбра не выходят.

От противного: выберем любую вершину и, выходя из неё, будем двигаться по рёбрам в направлении,приписанном данному ребру. Если из каждой вершины выходит хотя бы одно ребро, то рано или поздно мывернёмся туда, где уже были, поскольку граф конечен. Но это будет ориентированный цикл. Противоречие. Теорема 1.16. В любом конечном ориентированном графе без ориентированных циклов можно занумеровать вершины первыми натуральными числами так, что каждое ребро будет направлено от вершины сменьшим номером в вершину с большим номером.

Докажем индукцией по числу вершин p. При p = 1 утверждение очевидно. Пусть p > 1. Предположим,что это верно для всех графов с числом вершин, меньшим p. Рассмотрим граф с p вершинами. По лемме у негоесть вершина, из которой рёбра не выходят. Уберём из графа эту вершину и все входящие в неё рёбра, получимграф с числом вершин, меньшим p. По предположению индукции такой граф допускает искомую нумерациювершин числами 1, 2, . . . , p − 1.

Тогда присвоим выкинутой вершине номер p. 1.2.4. Двудольные графы. Критерий ХоллаОпределение. Пусть множество вершин графа разбито на два подмножества U и L. Граф называетсядвудольным, если концы любого ребра лежат в разных подмножествах.Пример 2.1. Примеры двудольных графов (рис.

5):[NO PICTURE AVAILABLE YET]Рис. 5. Двудольные и не двудольные графыУсловимся называть подмножество U верхним, а L — нижним. Будем рисовать двудольные графы в соответствии с этими названиями.Определение. Говорят, что задано паросочетание в двудольном графе, если для каждой верхней вершины зафиксировано по одному ребру (идущему в нижнее множество). Фактически это означает, что заданоотображение f : U → E. Паросочетание называется совершенным, если концы выпущенных рёбер при этом несклеиваются.Пусть A ⊂ U . Через R(A) будем обозначать образ бинарного отношения «соединён ребром» в L.Теорема 1.17 (Критерий Холла). Конечный двудольный граф обладает совершенным паросочетаниемтогда и только тогда, когда для любого (непустого) A ⊂ U имеем |R(A)| > |A|.

Необходимость этого условия очевидна: если совершенное паросочетание нашлось, то ясно, что образлюбого подмножества содержит не меньше вершин, чем само это подмножество (иначе какие-то два ребра,выходящие из множества A, упёрлись бы в одну вершину в образе).Докажем достаточность. Будем доказывать индукцией по числу n = |U |. База n = 1 очевидна: любое реброгодится. Пусть всё доказано для n, докажем для n + 1.

Возможны два случая.1◦ Для любого непустого A ⊂ U имеем |R(A)| > |A|, то есть по крайней мере |R(A)| > |A| + 1. Рассмотримa ∈ U . По крайней мере одно ребро из неё выходит, пусть оно приходит в вершину b ∈ L. Уберем вершины a и be с множествамииз нашего графа вместе со всеми рёбрами, которыев нихПолучим двудольный граф Γ входят.e и L.e Покажем, что R(A)e > Ae. Действительно, рассмотрим множество оставшихсяверхних и нижних вершин U«претендентов» на вершину b.

Для любого подмножества с их участием, но без участия вершины a, неравенствобыло строгим. Образ этого подмножества, конечно, захватывает вершину b, но когда мы её уберём, неравенстволишь превратится в нестрогое, ибо мы теряем всего одну вершину. Все остальные подмножества и вовсе сохранятe меньшестрогие равенства.

Итак, к новому графу уже применимо предположение индукции, потому что в Uвершин, чем в U .92◦ Пусть нашлось собственное непустое подмножество A0 ⊂ U , для которого |R(A0 )| = |A0 |. Посколькуоно собственное, то в нём уже по предположению индукции существует совершенное паросочетание. Теперьe в новомрассмотрим то, что останется от графа, если вырезать A0 и R(A0 ).