Если область определения предиката конечна, то иногда удобно заменить навешивание кванторов высказываниями, в которых переменным приданы конкретные значения.

Пусть A = {1, 2, 3} и на A задан одноместный предикат P (x), тогда xP (x) эквивалентно P (1)&P (2)&P (3);

xP (x) эквивалентно P (1) P (2) P (3).

При использовании нескольких кванторов существен их порядок.

Из предикатов, используя логические связки, кванторы, и скобки, можно строить сложные предикаты (с учетом области определения).

1.8 Синтез схем (-схемы, контактные схемы, схемы из функциональных элементов) Речь пойдет о моделях, вычисляющих булевы функции. Интерес к построению этих моделей, изучению их свойств и функционированию диктуется практическими вычислительными задачами. Для многих задач важно не просто составить программу или построить устройство, но еще и добиться экономичности и надежности этих объектов. Например, необходимо решить задачу экономного построения отдельных блоков ЭВМ. При этом возникают такие естественные меры сложности, как число элементов в схеме, число букв в формуле, число контактов в контактной схеме, число конъюнкций в д. н. ф., глубина схемы (максимальная длина цепочки, по которой сигнал проходит от входа до выхода схемы) и т. д.

Важно также при этом удачно выбрать язык описания алгоритмов и схем. Имеющиеся языки программирования удобны при разработке алгоритмов, но для доказательства существования или несуществования экономных алгоритмов они малопригодны. Поэтому желательно иметь дело с простейшими моделями алгоритмов, позволяющими анализировать алгоритмы.

В качестве таких моделей можно указать булевы формулы, д. н. ф., с которыми мы уже познакомились, а также контактные схемы, -схемы, схемы из функциональных элементов и т. д.

Одни модели удобнее при исследовании объема вычислительного устройства, например число элементов в сумматоре ЭВМ. Другие модели лучше приспособлены для изучения сложности программных вычислений (времени работы программы или требуемой его рабочей памяти).

Модель вычислений, или управляющая система, состоит из схемы и вычисляемой ею функции. Схема – это объект, построенный по определенным правилам и служащий для вычисления функции. Будем рассматривать схемы, вычисляющие булевы функции (далее б. ф.), поскольку эти функции сочетают предельную простоту с универсальностью.

Достаточно заметить, что любая программа современной ЭВМ фактически вычисляет совокупность б. ф.

• 1. С формулами, реализующими б. ф. в некотором базисе, мы уже познакомились. Мы узнали, что существует очень много различных базисов, познакомились с критерием полноты систем функций, научились выражать одни базисы через другие.

• 2. Вторая модель вычислений – это реализация б. ф. с помощью д. н. ф., т. е. частный случай реализации б. ф. в базисе {&,, ¬}. Этот базис очень удобен в исследованиях и изучениях б. ф., так как с помощью принципа двойственности позволяет в формуле "спустить" отрицания до переменных, произведя эквивалентные преобразования. Язык формул является весьма естественным для аналитического задания б. ф.

Как для любой б. ф. построить формулу, ее реализующую? Ответ на этот вопрос дает теорема 1.2 о представлении любой б. ф., не равной тождественно 0, с помощью с. д. н. ф. Б. ф., тождественно равную 0, можно представить формулой x&x 0. Если же стремиться построить экономную формулу, то этот вопрос становится очень сложным.

Данному вопросу посвящено множество статей, монографий.

• 3. Следующая модель вычисления или управляющая система, которую мы рассмотрим, – это наиболее "древний" класс управляющих систем, введенный К.Шенноном в 1938 г.

Контактная схема – это устройство из контактов и проводов, связывающих полюсы схемы (вход и выход).

Рабочему состоянию контакта ставим в соответствие 1, нерабочему – 0, наличию тока – 1, отсутствию тока – 0.

Контакты различают замыкающие и размыкающие: контакт замыкающий, если в рабочем состоянии (кнопка нажата), он замыкает цепь.

Замыкающему контакту естественным образом отвечает булева функция (x) = x.

Контакт размыкающий, если он замыкает цепь в нерабочем состоянии. Размыкающему контакту отвечает булева функция (x) = x.

Последовательно соединенные контакты реализуют конъюнкцию: x1 &x2, параллельно соединенные контакты реализуют дизъюнкцию: x1 x2.

Если произвольная цепь C без самопересечений, соединяющая вход и выход схемы (полюсы схемы), содержит контакты x11,..., xkk и тольi i ко их, то этой цепи сопоставляется конъюнкция Kc = x11... xkk. Конi i тактная схема S реализует по определению б. ф.

где берется по всем цепям без самопересечений, соединяющим полюсы контактной схемы.

Функция, реализуемая контактной схемой, является функцией проводимости схемы. Функция равна 1 тогда и только тогда, когда есть проводящая цепь между полюсами схемы.

• 4. Самостоятельный интерес представляет подкласс контактных схем – параллельно-последовательные контактные схемы (-схемы).

Приведем их индуктивное определение:

а) один контакт (a, b) есть -схема с полюсами a и b;

б) если S1 (a1, b1 ) и S2 (a2, b2 ) – -схемы, то схема S(a, b), полученная отождествлением (склеиванием) полюсов a1 с a2 и b1 с b2, есть -схема (параллельное соединение -схем S1 и S2 ) с полюсами a = a1 = a2, b = b1 = b2 ;

в) схема S(a, b), полученная склеиванием полюса a2 с b1, есть -схема (последовательное соединение -схем) с полюсами a1 и b2 ;

г) других -схем нет.

-Схеме естественным образом отвечает д. н. ф. Отметим, что схемы изоморфны формулам д. н. ф., так как функция, реализуемая схемой и соответствующая ей д. н. ф., совпадают. Однако -схемы весьма наглядны, что часто позволяет эффективно исследовать именно их, а не д. н. ф. Существуют разные алгоритмы минимизации -схем, контактных схем.

Как правило, контактные схемы содержат меньше контактов, чем эквивалентные им -схемы, поэтому бывает удобнее иногда рассматривать реализацию б. ф. именно контактной схемой.

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

Для определения (с. ф. э.) нам потребуется определение графа, а также ориентированного графа.

Пусть V – произвольное множество, U – множество некоторых его пар элементов. Совокупность G = (V, U ) называется графом с множеством вершин V и множеством ребер U. Граф ориентированный, если каждая пара (x, y) U упорядочена.

Пусть G – произвольный конечный ориентированный граф без ориентированных циклов, в каждую вершину которого входит не более двух дуг.

Вершины, в которые не входят дуги, называются входами (полюсами), остальные вершины внутренние, некоторые вершины пометим как выходные.

Каждому полюсу припишем букву алфавита {x1,..., xn }, каждой внутренней вершине с одной входящей дугой – ¬, вершине с двумя входящими дугами – & или. Булева операция, приписанная вершине a, вместе с этой вершиной называется функциональным элементом: если ¬, то инвертор; если &, то конъюнктор; если, то дизъюнктор.

Ориентированный граф такого специального вида с помеченными описанным образом вершинами называется схемой из функциональных элементов.

Каждой вершине схемы можно приписать булеву функцию, которую она реализует. Каждому полюсу xi приписываем функцию xi. Пусть некоторой вершине a схемы предшествуют вершины b и c, которым приписаны функции fb (x1,..., xn ) и fc (x1,..., xn ). Если a помечена в схеме & (), то ей приписываем функцию fb & fc (fb fc ). Если в a входит только дуга из b, то приписываем ¬ fb. Про эту функцию будем говорить, что она вычисляется (реализуется) схемой S в вершине a.

Важнейшие ресурсы при программировании – это время и память ЭВМ, и часто на практике остро встает вопрос о вычислительных ресурсах, т. е. возникает задача оптимизации программ. Оптимизировать ее можно по времени, по памяти и т. д.

При схемных вычислениях сложность характеризуется числом (и, возможно, качеством) элементов.

Пусть L(F ) – число вхождений символов переменных и констант в формулу F.

Формула (схема), имеющая минимальную сложность среди всех эквивалентных ей формул (схем), называется минимальной.

Сложностью б. ф. f в классе формул (схем) (обозначим L(f ) ) называется сложность минимальной формулы (схемы), реализующей f.

Положим Функция L(n) называется функцией Шеннона. Она равна сложности самой сложной функции от n переменных.

Аналогично определяется сложность функции и функция Шеннона для других классов схем.

Оценкам сложности б. ф. и построению экономных схем, реализующих б. ф., посвящен большой раздел дискретной математики – синтез схем.

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

В 1949 г. Клодом Шенноном было предложено найти метод синтеза схем, позволяющий для любой функции от n переменных строить формулу (схему), для которой L(F ) была бы близка к L(n), например, L(F ) C L(n), где C – некоторая константа.

2 ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

Для любого натурального n через n! (читается n–факториал) обозначается произведение 1 · 2 · 3 · · · n. По определению полагается 0! = 1.

Для любого действительного x и для любого натурального k убывающим факториалом [x]k называется произведение При натуральном x это произведение называется также числом размещений из x элементов по k элементов и обозначается Ak.

Для действительного x и натурального k положим При натуральном x это называется числом сочетаний из x элеменk тов по k элементов и обозначается также Cx.

Ряд комбинаторных задач о числе перестановок, размещений, сочетаний и т. п. можно интерпретировать как задачи о числе различного вида отображений конечных множеств в конечные множества.

В дальнейшем X = {x1,..., xm }, Y = {y1,..., yn }. Если пишем X (соответственно Y ), это значит, что элементы X (соответственно Y ) неразличимы.

Утверждение 2.1. Число всех отображений f : X Y равно nm.

ДОКАЗАТЕЛЬСТВО. Рассмотрим построение f как поэтапный процесс. На первом шаге выбираем f (x1 ), на втором – f (x2 ) и т. д. На каждом из m шагов имеется n возможностей. Таким образом, общее количество разных последовательностей выборов равно nm. Но разным последовательностям выборов соответствуют разные функции.

Примеры 1. Удобно представлять отображение f : X Y как раскладывание m помеченных шаров в n различных ящиков.

2. Пусть требуется подсчитать число m-мерных векторов, каждая координата которых может принимать любое значение из Y = {y1,..., yn }. Очевидно, эта задача эквивалентна предыдущей.

3. Пусть производится m опытов (называемых упорядоченными выборками с возвращениями), состоящих в том, что из генеральной совокупности Y наудачу выбирается какой-нибудь элемент yi, результат опыта фиксируется, а затем элемент возвращается в генеральную совокупность. Понятно, что, поставив последовательности {yi1,..., yim } исходов этих опытов в соответствие вектор {yi1,..., yim }, получим взаимно однозначное соответствие между множеством различных последовательностей исходов наших опытов и множеством m-мерных векторов с координатами из Y. Таким образом, число упорядоченных выборок с возвращениями подсчитывается по той же схеме.

Утверждение 2.2. Число всех инъективных (т.е. таких, при которых образы разных элементов различны) отображений f : X Y равно [n]m.

ДОКАЗАТЕЛЬСТВО. Как и при доказательстве утверждения 2.1, для выбора f (x1 ) имеется n возможностей. Но после этого для выбора f (x2 ) в Y \{f (x1 )} имеется уже не n, а n 1 возможностей, для выбора f (x3 ) имеется n 2 возможностей, и т. д. Следовательно, общее число различных инъективных отображений f : X Y равно Примеры 1. Инъективное отображение f : X Y удобно представлять как раскладывание m помеченных шаров в n различных ящиков таким образом, чтобы в каждом ящике было не более одного шара.

2. Пусть производятся опыты (называемые упорядоченными выборками без возвращений объема m), состоящие в том, что из генеральной совокупности Y наудачу выбирается какой-нибудь элемент yi, из оставшегося множества Y \{yi } наудачу выбирается другой элемент, и т. д. (всего m раз). Нетрудно усмотреть соответствие множества исходов этих опытов с раскладыванием m шаров в n разных ящиков.

Следствие 2.3. Число всех биективных отображений f : X Y равно n! при m = n и равно 0 при m = n.

Пример Число перестановок чисел 1,..., n равно n!.

Утверждение 2.4. Число m-элементных подмножеств n-элементn ного множества Y равно m.

ДОКАЗАТЕЛЬСТВО. Поставим в соответствие каждому инъективному отображению f : X Y множество f (X). Тогда каждому отображению будет соответствовать одно m-элементное подмножество Z множества Y и по следствию 2.3 каждое такое Z соответствует m! различным отображениям. Следовательно, искомое число равно [n]m /m! = Утверждение 2.5. А. Число сюръективных отображений f :

X Y (X означает, что элементы X неразличимы) равно m1 ;

|Y | = n.

ДОКАЗАТЕЛЬСТВО. Поставим в соответствие каждому сюръективному отображению f : X Y набор из n 1 перегородок в промежутках между m элементами X, расположенными на одной прямой, по следующим правилам. Если |f 1 (yi )| = ai, то i-я перегородка размещается между элементами с номерами a1 +...+ai и a1 +...+ai +1. При этом соответствии каждому отображению f сопоставлена одна расстановка перегородок, и наоборот, каждая расстановка сопоставлена какому-то f. Наконец, если f1 и f2 различные отображения X на Y, то для некоторого i числа |f1 (yi )| и |f2 (yi )| должны различаться. Но тогда отображениям f1 и f2 соответствуют различные расстановки перегородок.

Следовательно, число таких расстановок равно числу сюръективных отображений f : X Y. Поскольку имеется m 1 мест, куда можно ставить n 1 перегородок и в каждое место можно ставить лишь одну перегородку, это число равно m1.

Для доказательства части Б нашего утверждения заметим, что аналогично случаю А имеется взаимно однозначное соответствие между множеством всех отображений f : X Y и множеством таких расстановок n 1 перегородок в m 1 промежутков, что в любой промежуток разрешается ставить любое количество перегородок. Число таких расстановок можно подсчитать следующим образом. Имеется m+n1 мест для элементов X и перегородок. Ставим на любые n 1 из них перегородки, а на оставшиеся места – элементы X. Число способов сделать это равно n+m1.

Примеры 1. Число способов раскладывания m одинаковых шаров в n различных ящиков равно n+m1.

2. Допустим, мы бросаем m одинаковых игральных костей. Тогда можно различить m+5 разных исходов бросания.

3. Число векторов (y1,..., yn ) в Rn с целочисленными неотрицательными координатами, удовлетворяющими уравнению y1 +... + yn = m, равно n+m1.

4. Число способов раскладывания m одинаковых шаров в n различных ящиков так, чтобы не было пустых ящиков, равно m1. n 2.2 Разбиения конечных множеств и числа Стирлинга второго рода Число разбиений m-элементного множества на k непустых подмножеств обозначим через S(m, k) и будем называть его числом Стирлинга второго рода.

Утверждение 2.6. А. Число сюръективных отображений f :

X Y (элементы Y неразличимы) равно S(m, n).

Б. Число сюръективных отображений f : X Y равно n!S(m, n).

В. Число всех отображений f : X Y равно k=1 S(m, k).

ДОКАЗАТЕЛЬСТВО. Каждое отображение f множества X на множество Y порождает разбиение Если два отображения f1 и f2 порождают одно и то же разбиение, значит существует такая перестановка (i1,..., in ) чисел 1,..., n, что Это как раз и означает, что если элементы Y неразличимы, то f1 и f совпадают. Тем самым А доказано.

Любое сюръективное отображение f : X Y можно построить в два этапа: сначала разбить X на n непустых частей X1,..., Xn (имея в виду, что элементы из одной части будут отображаться в один и тот же элемент множества Y ), а затем для каждого такого разбиения (X1,..., Xn ) выбрать в качестве f (X1 ),..., f (Xn ) различные элементы Y. Согласно А имеется S(m, n) разных исходов первого этапа. Для любого исхода первого этапа имеется n! разных исходов второго этапа. Итого имеется n!S(m, n) возможностей.

Утверждение В следует из А, поскольку при неразличимых элементах Y отображения X на разные подмножества Y, состоящие из одинакового количества элементов, одинаковы.

Утверждение 2.7. А. S(m, m) = 1 при m 0.

Б. S(m, 0) = 0 при m > 0.

В. S(m, k) = S(m 1, k 1) + kS(m 1, k) при 0 < k < m.

ДОКАЗАТЕЛЬСТВО. Утверждения А и Б очевидны. Для доказательства В заметим, что множество R всех разбиений множества X = {x1,..., xm } на n частей распадается на множества R1 = { R | одноэлементное множество{xm } является элементом разбиения} и R2 = R\R1.

Очевидно, |R1 | = S(m 1, k 1). Поставим в соответствие каждому разбиению R2 разбиение множества X\{xm }, полученное из удалением элемента xm из той части, которой он принадлежал.

Поскольку каждое разбиение множества X\{xm } будет поставлено в соответствие ровно k разбиениям множества X (образованным из путем добавления xm к какой-нибудь из k частей), то |R2 | = kS(m 1, k).

Доказанные равенства позволяют вычислять значения S(m, k) по треугольнику Стирлинга:

Утверждение 2.8. Для любого k ДОКАЗАТЕЛЬСТВО. Пусть (X1,..., Xk ) – произвольное разбиение X на k непустых подмножеств, xm Xk. Имеется m1 возможностей выбрать Xk с |Xk | = r и xm Xk. После этого останется S(m r, k 1) возможностей разбить оставшееся множество на k 1 непустых подмножеств. Следовательно, Числом Белла Bn называется число всех разбиений n-элементного множества на непустые подмножества. Ясно, что Bn = i=1 S(n, i).

Упражнение Теорема 2.9. Для каждого m ДОКАЗАТЕЛЬСТВО. Пусть n – натуральное число. По утверждению 2.1 число отображений f : X Y, где |X| = m, |Y | = n, равно nm.

Подсчитаем это число другим способом. Для каждого A Y, A =, пусть XA – множество отображений f : X Y с f (X) = A. Если |A| = k, то |XA | = k!S(m, k). Следовательно, по утверждению 2.6 Б Таким образом, значения многочленов xm и k=1 S(m, k)[x]k совпадают при x = 1, 2, 3,.... Значит, это один и тот же многочлен.

2.3 Разбиения чисел на слагаемые. Диаграммы Рассмотрим теперь отображения X в Y. В этом случае для того, чтобы отображения f1 и f2 различались, необходимо, чтобы различались наборы чисел {|f1 (y1 )|, |f1 (y2 )|,..., |f1 (yn )|} и {|f2 (y1 )|, |f2 (y2 )|,..., |f2 (yn )|} (без учета порядка этих чисел). Таким образом, задача нахождения числа Ч(m, n) отображений X в Y эквивалентна нахождению числа разложений натурального числа m в сумму n неотрицательных целых слагаемых (порядок слагаемых не учитывается).

Обозначим через P (m, k) число разбиений m на k натуральных слагаемых, а через P (m) – число разбиений m на натуральные слагаемые.

Понятно, что Изучать некоторые свойства P (m, k) помогают диаграммы Ферре.

Диаграмма Ферре для разложения m = a1 + a2 +... + ak (для единообразия считаем, что a1 a2... ak ) состоит из k строк, где строка i содержит ai точек, расположенных в столбцах 1,..., ai. В примере изображена диаграмма Ферре для разложения 16 = 6 + 5 + 2 + 2 + 1.

Нетрудно убедиться, что каждая диаграмма соответствует в точности одному разложению числа в сумму натуральных слагаемых.

Утверждение 2.10. А. Число разложений числа m в сумму ровно k слагаемых равно числу представлений m в виде суммы натуральных слагаемых, наибольшее из которых равно k.

Б. Число представлений m в виде суммы попарно различных (натуральных) слагаемых равно числу представлений m в виде суммы нечетных слагаемых.

ДОКАЗАТЕЛЬСТВО. Докажем А. Поставим в соответствие каждой диаграмме (Ферре) D для разбиения m на k слагаемых двойственную ей диаграмму, полученную "транспонированием" D. Очевидно, "транспонированная" диаграмма отвечает некоторому разложению m = + a2 +... + as c a1 = k. Легко убедиться, что указанное соответствие взаимно однозначно отображает множество диаграмм с k строками на множество диаграмм с k столбцами. Тем самым А доказано.

Докажем Б. Пусть Q – множество разложений m в сумму различных слагаемых, а P – множество разложений m в сумму нечетных слагаемых. Построим отображение F : Q P по следующим правилам. Пусть m = a1 +a2 +...+ak и a1 > a2 >... > ak. Каждое из ai представим в виде ai = 2ci bi, где bi нечетно. Такое представление однозначно. Поставим в соответствие разложению m = a1 + a2 +... + ak разложение Это соответствие обозначим через F.

Теперь построим отображение G : P Q по следующим правилам.

Пусть дано разложение числа m на нечетные слагаемые (из них s различных). Каждое из di -х однозначно представимо в виде суммы степеней двойки:

Тогда разложение представляет m в виде суммы различных слагаемых. Действительно, при одном и том же i слагаемые различны, поскольку различны ei,j, а при разных i различны наибольшие нечетные делители чисел. Пусть отображение G сопоставляет каждому разложению вида (1) разложение вида (3).

Из определений следует, что если на некоторое разложение вида (1) подействовать отображением G, а затем на полученное разложение числа m в сумму различных слагаемых подействовать отображением F, то снова получится исходное разложение. В силу однозначности представления (2) из двух несовпадающих разложений числа m на различные слагаемые после действия на них отображения F нельзя получить одно и то же разложение вида (1).

Значит, F и G – взаимно однозначные отображения и |P| = |Q|.

Утверждение 2.11. Справедливо равенство P (m, n) = P (mn, 1)+ ДОКАЗАТЕЛЬСТВО. Пусть R(m, n) – множество разложений числа m в сумму n натуральных слагаемых, R(m, n, k) – множество тех разложений из R(m, n), в которых ровно k слагаемых равны 1. Поставим в соответствие каждому разложению m n = a1 + a2 +... + ak из R(m n, k) разложение из R(m, n, n k). Ясно, что это соответствие взаимно однозначно отображает R(m n, k) на R(m, n, n k).

Часть изложенных выше результатов суммируется в таблице (напомним, что |X| = m, |Y | = n).

2.4 Возвратные последовательности Как мы видели в предыдущих параграфах, в ряде случаев удается вывести рекуррентные соотношения для вычисления членов различных последовательностей. К сожалению, не всегда из таких соотношений удается получить малотрудоемкие явные формулы. Разберем один случай, когда это можно сделать.

Последовательность {an } назовем возвратной, если для некотоn= рого натурального k найдутся такие p1,..., pk (pk = 0), что Пример Фибоначчи сформулировал следующую задачу. Некто получил пару новорожденных кроликов 1 января. Кролики месяц растут, а затем каждый месяц дают приплод – одну пару. В свою очередь, каждая новая пара месяц растет, а затем каждый месяц дает приплод. Требуется узнать, сколько кроликов будет к концу года. Обозначив через Fn число пар кроликов к концу n-го месяца, имеем Требуется найти F12. Последовательность {Fn } является возвратn= ной, так как удовлетворяет уравнениям К соотношениям вида (5) приводят совершенно разные задачи.

Утверждение 2.12. Множество U последовательностей {an }, удовлетворяющих (4), является линейным пространством размерности k.

ДОКАЗАТЕЛЬСТВО. Множество всех бесконечных числовых последовательностей с операциями сложения (покомпонентно) и умножения на число (покомпонентно) является линейным пространством. Чтобы показать, что последовательности {an }, удовлетворяющие (4), образуют его линейное подпространство, достаточно убедиться в замкнутости множества таких последовательностей относительно операций сложения и умножения на число. Если {an } и {bn } удовлеn=0 n= творяют (4), и – любые действительные числа, а n – произвольное неотрицательное целое, то (an+k + bn+k ) + p1 (an+k1 + bn+k1 ) +... + pk (an + bn ) = = (an+k + p1 an+k1 +... + pk an ) + (bn+k + p1 bn+k1 +... + pk bn ) = 0.

Следовательно, U – линейное пространство.

Если последовательность {an } удовлетворяет (4) и заданы чисn= ла a0,..., ak1, то все остальные ai определяются из (4) однозначно.

Значит, размерность U не превосходит k. С другой стороны, для j = 0, 1,..., k1 последовательность Aj пусть строится так: aj = 1, ai = 0 для i {0, 1,..., k 1}\{j}; остальные an+k для n 0 определяются из (4).

Тогда последовательности Aj (j = 0, 1,..., k 1) линейно независимы в совокупности.

Многочлен называется характеристическим многочленом для последовательности {an }. Характеристическим многочленом для последовательноn= сти {Fn } будет x2 x 1.

Утверждение 2.13. Пусть – корень многочлена (6) кратности s (s 1). Тогда для любого t, 1 t s, последовательность {bn (t)}, где bn = nt1 n, удовлетворяет (4).

ДОКАЗАТЕЛЬСТВО.

Поскольку = 0, получаем Но последнее равенство как раз и требовалось доказать.

Таким образом, если 1,..., m – корни многочлена (6) и i – корень кратности si (1 i m, s1 +... + sm = k), то любая последовательность {an } вида где i,j – произвольные константы, удовлетворяет (4).

Можно показать, что все построенные выше k последовательностей будут линейно независимы. В общем случае доказательство громоздко.

Сейчас мы разберем два случая, используя следующий простой факт.

Упражнение Случай 1. Все корни (6) имеют кратность 1. Для доказательства висимы, достаточно убедиться, что линейно независимы векторы (1, i, 2,..., k1 ) (i = 1, 2,..., k), т. е. векторы, составленные из их первых k координат. Последнее эквивалентно утверждению упражнения.

Случай 2. Корень имеет кратность k. Тогда достаточно показать, что Dk = 0, где Пример Характеристическим многочленом для последовательности {Fn является P (x) = x2 x 1. Корнями P (x) являются 1 = 1+2 5 и 2 = 12 5. Следовательно, для некоторых 1 и 2 имеем Найдем 1 и 2, зная, что F0 = F1 = 1:

2.5 Числа Каталана Числа Каталана {cn } определяются по следующим правилам: c0 = и для любого n > Начало последовательности: 1, 1, 2, 5, 14, 42, 132, 429,...

Пример Плоское корневое дерево – это дерево с выделенной вершиной (называемой корнем), где непосредственные потомки каждой вершины упорядочены каким-нибудь образом. Каждому плоскому корневому дереву T с корнем r можно сопоставить пару деревьев (T1, T2 ), полученную после удаления из T ребра (r, s), соединяющего r со старшим потомком s.

При этом считаем, что T1 содержит r, а T2 – s. По построению суммарное число вершин в T1 и T2 равно числу вершин в T. С другой стороны, из каждой пары (T1, T2 ) плоских корневых деревьев добавление ребра, соединяющего их корни, и выбор корня T1 в качестве корня дает новое плоское корневое дерево. Следовательно, для числа tn плоских корневых деревьев с количеством ребер n справедливы соотношения t0 = 1 и для любого n > Другими словами, tn есть n-е число Каталана.

Пример Пусть плоское корневое дерево T расположено на плоскости так, что потомки каждой вершины лежат выше ее и расположены по убыванию их старшинства (в выбранном порядке) слева направо. Тогда обходу этого дерева вдоль ребер, начиная с корня так, что дерево остается всегда справа, соответствует последовательность из чисел 1 и (1) по следующим правилам: если мы переходим от какой-либо вершины к ее потомку, то добавляем к последовательности 1, а если к предку, то добавляем 1.

В полученной последовательности будет n единиц и n минус-единиц, причем для любого 1 i 2n сумма первых i членов последовательности неотрицательна. С другой стороны, по каждой последовательности с такими свойствами можно однозначно построить плоское корневое дерево. Следовательно, число pn последовательностей из n единиц и n минус-единиц таких, что для любого 1 i 2n сумма первых i членов последовательности неотрицательна, тоже равна cn.

Для нахождения явной формулы cn представим pn в виде pn = wn vn, где wn – число всех последовательностей из n единиц и n минус-единиц, а vn – число таких последовательностей из n единиц и n минус-единиц, что Очевидно, wn = 2n. n Чтобы подсчитать vn, сопоставим каждой последовательности A = {aj }2n из множества Vn последовательностей из n единиц и n минус-единиц, удовлетворяющих (8), последовательность F (A) по следующим правилам. Пусть i(A) – наименьшее натуральное i, для которого a1 +... + ai = 1. Тогда F (A) получается из A переменой знаков всех первых i(A) членов последовательности. По построению, F (A) имеет n + 1 единиц и n 1 минус-единиц.

Покажем, что так определенное F взаимно-однозначно отображает Vn на множество Zn всех последовательностей из n + 1 единиц и n 1 минус-единиц. Действительно, пусть B = {bj }2n Zn, а k(B) – наименьшее натуральное k, для которого b1 +... + bk = 1. Обозначим через G(B) последовательность, которая получается из B переменой знаков всех первых k(B) членов. Нетрудно видеть, что G(B) Vn, i(G(B)) = k(B) и F (G(B)) = B. Следовательно, |Vn | = |Zn | = n1.

Таким образом, Пример Дано произведение a1 a2... an+1 из n + 1 сомножителей. Пусть R(n) – множество таких расстановок n пар скобок между этими сомножителями, что внутри каждой пары скобок ровно два сомножителя.

Чему равно rn := |R(n)|?

Если n = 0, т. е. имеется лишь один множитель, то скобок не надо совсем. Значит, единственный способ расстановки скобок – не ставить их, и r0 = 1.

Если имеется два сомножителя a1 a2, то снова один способ расстановки скобок : (a1 a2 ) и r1 = 1.

Если имеются три сомножителя a1 a2 a3, то имеем два способа расстановки скобок: ((a1 a2 )a3 ) и (a1 (a2 a3 )), откуда r2 = 2.

При n 1 всегда имеется "внешняя" пара скобок: самая левая открывающая с самой правой закрывающей. Назовем "второй" пару скобок, в которой открывающая является самой левой, не считая "внешней". Пусть R(n, k) – множество таких расстановок R R(n), в которых закрывающая "вторую" пару скобка стоит после ak. Тогда при k n а условие k = n + 1 означает, что "вторая" открывающая скобка в R стоит после a1 и R имеет вид (a1 (a2... an+1 )). Расстановок такого вида, по определению, rnk. Следовательно, Значит, rn удовлетворяет рекуррентному соотношению (7) и совпадает с cn для любого n.

2.6 Производящие функции С каждой последовательностью {an } можно связать формальный степенной ряд A(t) = a0 + a1 t + a2 t2 + a3 t3 +..., называемый производящей функцией для последовательности {an }. Если |an | растет не слишком быстро, то в некоторой окрестности нуля этот ряд абсолютно сходится и A(t) можно отождествить с получающейся аналитической функцией.

Примеры Зная производящую функцию A(t), можно найти любое an, испольA(0)(n) Примеры 1. A(t) = 1/(1 2t). Тогда A(n) (t) = (1)(2)... (n)(2)n ( 2. A(t) = (1 + t)m, где число m не является натуральным. Тогда Формальные ряды можно складывать и умножать: если A(t) = Это свойство можно использовать при выводе ряда тождеств.

Пример Распишем очевидное равенство (1 + t)k (1 + t)m = (1 + t)km через ряды:

Следовательно, Используя определение (7) чисел Каталана, найдем производящую функцию C(t) этой последовательности и тем самым выведем их явную формулу еще одним способом. Имеем Разрешив квадратное уравнение относительно C(t), получим Поскольку C(0) = 1, в формуле годится только знак "минус".

Подсчитаем n-ю производную от 1 4t:

Следовательно, Заметим, что 2.7 Некоторые вероятностные задачи с конечным пространством элементарных событий Изложенные ниже факты приобретают ценность и наглядный смысл в связи с действительными или мысленными опытами. Результаты опытов будем называть событиями.

Пространство элементарных событий (, P) – это конечное множество = {E1,..., En } (элементы которого называются элементарными событиями), где каждому Ei сопоставлено число P{Ei }, называемое вероятностью элементарного события Ei. Эти числа должны быть неотрицательны и таковы, что Каждый раз, когда строится воображаемое пространство, которое должно моделировать реальную ситуацию, надо, во-первых, выбрать {E1,..., En }, а затем определить P{Ei }, i = 1,..., n.

Примеры 1. Пусть опыт состоит в бросании двух различимых игральных костей. Обычно рассматривают = {Eij | i = 1, 2; j = 1,..., 6}, где элементарное событие Eij состоит в том, что на первой кости выпало i очков, а на второй – j очков. При этом, как правило, полагают P{Eij } = = 1/36. В некоторых задачах, однако, удобно выбрать = {E2,..., E12 }, где событие Ei состоит в том, что сумма очков на костях равна i. Из соображений здравого смысла полагают P{Ei } = min{i 1, 13 i}/36.

2. Рассмотрим механическую систему, состоящую из r неразличимых частиц. В статистической механике обычно разбивают фазовое пространство на большое число n малых областей и полагают, что каждая из частиц находится в какой-то одной из этих ячеек. В результате состояние всей системы описывается как случайное размещение r частиц в n ячейках. Если все nr размещений равновероятны, то физики говорят о статистике Максвелла – Больцмана. Однако поведение реальных частиц не удается аппроксимировать этой моделью. В статистической механике показано, что для фотонов и атомных ядер годится статистика Бозе – Эйнштейна, где каждому из n+r1 размещений r неразличимых частиц по n ячейкам приписана вероятность n+r1.

К электронам, нейтронам и протонам применима статистика Ферми – Дирака, которая запрещает находиться в любой ячейке более чем одной частице и приписывает вероятность n каждому из размещений частиц, удовлетворяющих этому условию.

В ряде комбинаторных задач из соображений симметрии полагают вероятности всех элементарных событий равными между собой. В этом случае говорят о классическом определении вероятности.

Любое подмножество множества будем называть событием. Вероятность P{A} любого события A есть сумма вероятностей элементарных событий, из которых состоит A:

Пример Предположим, что Вы играете в спортлото "5 из 36", и вероятность любого из 36 исходов одна и та же. Тогда вероятность того, что в Вашем билете угадано пять номеров, равна 0, 0000026526, четыре Теорема 2.14. Для любых событий A1 и A2 вероятность P{A1 A2 } того, что имеет место как минимум одно из этих событий, равна P{A1 } + P{A2 } P{A1 A2 }.

ДОКАЗАТЕЛЬСТВО.

Пусть H – событие с P{H} > 0. Для любого события A положим Таким образом определенная величина будет называться условной вероятностью события A при условии H.

Пример Рассмотрим семьи с двумя детьми. Обозначим буквами м и д соответственно мальчика и девочку и на первом месте будем указывать старшего ребенка. Имеем 4 возможности: мм, мд, дм, дд. Припишем каждому из этих элементарных событий вероятность 1/4. Пусть событие H1 состоит в том, что в семье есть мальчик, событие H2 в том, что старший ребенок в семье – мальчик, а событие A – в том, что оба ребенка в семье – мальчики. Тогда Пример Пусть – множество всех упорядоченных пар карт колоды из листов, и вероятность выбрать любую упорядоченную пару одинакова и равна 1/(51·52). Обозначим через A событие, состоящее в том, что обе карты из пары являются тузами, через H1 – что первая из выбранных карт является тузом, через H2 – что первая из выбранных карт является тузом треф. Сравним P{A | H1 } и P{A | H2 }:

откуда Пусть теперь – множество всех неупорядоченных пар карт колоды из 52 листов, и вероятность вытянуть любую пару одинакова и равна. Обозначим через A событие, состоящее в том, что обе карты из пары являются тузами, через H1 – что хотя бы одна из выбранных карт является тузом, через H2 – что одна из выбранных карт является тузом треф. В отличие от предыдущего примера получим, что P{A | H1 } < < P{A | H2 }:

откуда Формулу (10) иногда используют в виде Теорема 2.16. (формула полной вероятности) Пусть H1,..., Hk – взаимно исключающие события, объединение которых есть, и вероятность каждого из Hi положительна. Тогда для любого A ДОКАЗАТЕЛЬСТВО. По условию Согласно утверждению 2. Пример Предположим, что в урне имеется M шаров, из которых n счастливых. Выбираем наугад какой-то шар, а затем, не возвращая его, – второй. Какова вероятность, что второй шар счастливый? Обозначим через H1 событие, что первый шар счастливый, через H2 – событие, что первый шар несчастливый, через A – событие, что второй шар счастливый. Тогда P{H1 } = n/M, P{H2 } = 1 n/M, P{A | H1 } = = (n 1)/(M 1), P{A | H2 } = n/(M 1), и по теореме 2. Пример Предположим, что вы k раз играете в игру, где i-й раз вероятность вашего выигрыша равна pi. Какова вероятность Pk того, что вы выиграете хотя бы один раз из k? Покажем индукцией по k, что она равна 1 (1 p1 ) · (1 p2 ) ·... · (1 pk ). Для k = 1 это тривиально. Пусть формула доказана для всех k < k. Обозначим через H1 (i) событие, что вы выиграли хотя бы раз из первых i розыгрышей, а через H2 (i) событие, что этого не произошло. Тогда по теореме 2. +P{H1 (k) | H2 (k1)}·P{H2 (k1)} = 1·P{H1 (k1)}+pk ·P{H2 (k1)}.

По индукционному предположению, P{H1 (k 1)} = 1 (1 p1 ) · ( p2 ) ·... · (1 pk1 ). Значит, Pk = 1(1p1 )·(1p2 )·...·(1pk1 )+pk (1p1 )·(1p2 )·...·(1pk1 ) = Это утверждение можно трактовать и так: если вероятность успеха Вашего соперника в i-м розыгрыше равна qi = 1 pi, то вероятность того, что он выиграет все k раз, равна q1 ·... · qk.

Пусть P{A} > 0, P{B} > 0. Согласно (11), P{A | B} · P{B} = = P{A B} = P{B | A} · P{A}, откуда следует формула Байеса Теорема 2.17. (Теорема Байеса.) Пусть H1,..., Hk – взаимно исключающие события, объединение которых есть, и вероятности событий H1,..., Hk, A положительны. Тогда ДОКАЗАТЕЛЬСТВО. По формуле Байеса P{Hi | A} = P{A | Hi } · P{Hi }/P{A}. Подставив в это равенство вместо P{A} его выражение из теоремы 2.16, получим требуемое.

Пример В урне имеются две монеты: первая – симметричная с вероятностью выпадения герба 1/2, вторая – кривая с вероятностью выпадения герба 1/3. Выбираем наугад монету и подбрасываем: выпал герб. Какова вероятность того, что выбрана симметричная монета?

Имеем четыре элементарных исхода: M1 G, M1 C, M2 G, M2 C, где Mi – событие, что достали i-ю монету, G что выпал герб, а C – что выпала цифра. Нам требуется узнать P{M1 | G}. По теореме Байеса События A и B называются независимыми, если Упражнение. Доказать, что если события A и B независимы, то события A и B = \ B тоже независимы.

События A1,..., Am называются независимыми в совокупности, если для любого k, 2 k m и для любых Ai1,..., Aik справедливо равенство 2.8 Случайные величины. Схема Бернулли Функция, определенная на пространстве элементарных событий, называется случайной величиной. Если f – случайная величина, то функция hf (x) = P{f = x} называется распределением (вероятностей) случайной величины f.

Вы играете в "поле чудес", ваша очередь хода, вы знаете, какое слово загадано и все-таки вы крутите колесо. Тогда сумма ваших очков после хода есть случайная величина, зависяшая от того, где остановится колесо.

Случайная величина, которая принимает лишь значения 0 и 1, называется бернуллиевской.

Пусть f – случайная величина (принимающая значения x1,..., xt с вероятностями hf (x1 ),..., hf (xt )). Математическим ожиданием M(f ) случайной величины f называется сумма Для бернуллиевской случайной величины f, принимающей значение 1 с вероятностью p, имеем M(f ) = 0 · (1 p) + 1 · p = p.

Непосредственно из определений получаем, что для любых случайных величин f и g и любой константы c 1) M(f + g) = M(f ) + M(g);

2) M(c · f ) = c · M(f );

3) если f g, то M(f ) M(g);

4) |M(f )| M(|f |).

(Докажите эти свойства в качестве упражнения.) Для суммы Sn = f1 +... + fn бернуллиевских случайных величин, каждая из которых принимает значение 1 с вероятностью p, по свойству 1 имеем M(Sn ) = M(f1 ) +... + M(fn ) = pn.

Дисперсией D(f ) случайной величины f называется величина Непосредственно из определения получаем, что для любой случайной величины f и любых констант c и d Для бернуллиевской случайной величины f, принимающей значение 1 с вероятностью p, имеем D(f ) = M((f p)2 ) = p(1p)2 +(1p)(p)2 = = p(1 p).

Случайные величины f1,..., fm называются независимыми в совокупности, если для любого k, 2 k m и для любых xi1,..., xik справедливо равенство Свойства независимых случайных величин 1. Пусть f, g – независимые случайные величины, c, d – произвольные константы. Тогда f c, g d – тоже независимые случайные величины.

ДОКАЗАТЕЛЬСТВО. Для произвольных действительных x и y имеем 2. Пусть f, g – независимые случайные величины. Тогда M(f g) = = M(f ) · M(g).

ДОКАЗАТЕЛЬСТВО. Пусть f принимает значения a1,..., as, а g принимает значения b1,..., bt. Тогда 3. Пусть f, g независимые случайные величины. Тогда D(f + g) = D(f ) + D(g).

ДОКАЗАТЕЛЬСТВО. По свойству 1 случайные величины f M(f ) и g M(g) также являются независимыми. Следовательно, с учетом свойства 2 имеем = M((f M(f ))2 ) + M(2(f M(f ))(g M(g))) + M((g M(g))2 ) = Для суммы Sn = f1 +... + fn независимых бернуллиевских случайных величин, каждая из которых принимает значение 1 с вероятностью p, по свойству 3 имеем Неравенства Чебышева. Пусть g – неотрицательная случайная величина, а f – произвольная случайная величина. Тогда для любого ДОКАЗАТЕЛЬСТВО. Докажем неравенство (а). Пусть функция g принимает значения x1,..., xs. Тогда Каждое из оставшихся неравенств является непосредственным следствием предыдущего.

Используя неравенство Чебышева, докажем закон больших чисел в следующей весьма слабой форме.

Теорема 2.18. Для любых положительных и при достаточно большом n для суммы Sn = f1 +... + fn независимых бернуллиевских случайных величин, каждая из которых принимает значение 1 с вероятностью p, ДОКАЗАТЕЛЬСТВО. Для случайной величины f = Sn /n имеем M(f ) = M(Sn )/n = p. В силу неравенства Чебышева Рассмотрим случайные блуждания частицы по целочисленным точкам отрезка [0, k]. Если в момент времени i частица находится в точке j, 1 j k 1, то в момент i + 1 частица с вероятностью p оказывается в точке j + 1 и с вероятностью 1 p оказывается в точке j 1. Как только частица оказывается в точке 0 или k, процесс прекращается.

Обозначим через An (j, k) вероятность того, что частица, находящаяся в момент 0 в точке j, не более чем к n-му моменту времени окажется в точке 0. Аналогично, обозначим через Bn (j, k) вероятность того, что частица, находящаяся в момент 0 в точке j, не более чем к n-му моменту времени окажется в точке k. Наконец, через Cn (j, k) обозначим вероятность того, что частица, находящаяся в момент 0 в точке j, к n-му моменту времени окажется в отрезке [1, k 1] (т. е. не достигнет ни 0, ни k). Для любых натуральных n и k и любых целых 0 j k справедливы следующие соотношения:

An+1 (j, k) An (j, k), Bn+1 (j, k) Bn (j, k), Cn+1 (j, k) Cn (j, k). (15) Согласно (12) и (15) каждая из последовательностей {An (j, k)}, {Bn (j, k)}, {Cn (j, k)} является ограниченной и монотонn=0 n= ной. Следовательно, существуют пределы A(j, k) = limn An (j, k), B(j, k) = limn Bn (j, k) и C(j, k) = limn Cn (j, k).

По формуле полной вероятности Переходя к пределу по n в обеих частях, получаем Аналогично (16) выводятся равенства Таким образом, при фиксированном k каждая из последовательностей {A(j, k)}k, {B(j, k)}k, {C(j, k)}k удовлетворяет одному и тому же возвратному соотношению с характеристическим уравнением Корнями (17) являются x1 = 1 и x2 = (1 p)/p. Переходя к пределу по n в (13) и (14), получаем A(0, k) = B(k, k) = 1, A(k, k) = B(0, k) = C(0, k) = C(k, k) = 0. (18) Случай 1. p = 1/2. Тогда имеем C(j, k) = + ( 1p )j, где и определяются из уравнений Единственным решением этой системы являются = = 0, откуда C(j, k) = 0.

Аналогично, B(j, k) = + ( 1p )j, где и определяются из уравp нений Решая систему, получаем Переходя к пределу по n в (15), получаем A(j, k) = 1B(j, k)C(j, k) = = 1 B(j, k).

Случай 2. p = 1/2. Тогда C(j, k) = + j, и снова C(j, k) = 0.

Аналогично, B(j, k) = + j, где Получаем B(j, k) = j/k, A(j, k) = (k j)/k.

2.9 Формула включений и исключений Теорема 2.19. (Формула включений и исключений.) Пусть A1,..., Ak – конечные множества, K = {1,... , k}. Тогда ДОКАЗАТЕЛЬСТВО. Каждый элемент x A1... Ak дает единицу в |A1... Ak |. Покажем, что такой же вклад x вносит и в сумму в правой части (19). Пусть для определенности x A1... Ar, x / Ai (r < i k). По определению x iI Ai, если и только если I {1,..., r}. Число j-элементных множеств I {1,..., r} равно r.

Значит, x вносит в правую часть (19) вклад, равный Замечание. Предположим, что S – конечное множество и A1... Ak S. Если положить Ai = S, то (19) можно переписать в виде Следующая теорема обобщает теоремы 2.19 и 2.14.

Теорема 2.20. (Формула решета.) Пусть A1,..., Ak – произвольные события вероятностного пространства, (, P). Для каждого I {1,..., k} обозначим AI = iI Ai. Тогда ДОКАЗАТЕЛЬСТВО. По определению Покажем, что после такой замены в правой части (21) коэффициент при P{Ej } будет равен единице, если Ej A1... Ak, и нулю в противном случае. Если Ej A1...Ak, то Ej iI Ai при любом I.

Следовательно, P{Ej } не будет входить ни в одну из сумм вида P{AI }.

Пусть теперь Ej A1... Ak. Можно считать, что Ej A1... Ar, Ej Ar+1... Ak. Тогда P{Ej } будет входить в сумму P{AI }, если и только если I {1,..., r}. Значит, коэффициент при P{Ej } в правой части (21) равен Приведем несколько применений формул (19)–(21).

Теорема 2.21. Если |X| = m, |Y | = n, то число Z(m, n) всех сюръn ективных отображений f : X Y равно j=0 (1)j n (n j)m.

ДОКАЗАТЕЛЬСТВО. Пусть Y = {y1,..., yn }. Обозначим через Ai множество таких функций f : X Y, что yi f (X). Тогда f не сюръективное отображение, если и только если f A1... An. Поскольку всего имеется nm отображений f : X Y, по (20) имеем где A – множество всех отображений f : X Y.

По определению f AI, если и только если f (X) Y \{yi | i I}.

Следовательно, |AI | = (n |I|)m. Значит, Из теоремы 2.21 и утверждения 2.6 получаем Пусть Sn – множество всех перестановок чисел 1,..., n. Назовем Sn беспорядком, если (k) = k при любых 1 k n. Обозначим через Dn множество всех беспорядков на {1,..., n}.

Теорема 2.23. Число |Dn | всех беспорядков на {1,..., n} равно = 1,..., n). Тогда для любого I {1,..., n} Значит, |AI | = (n |I|)!. Число j-элементных подмножеств I множества {1,..., n} равно n. Поскольку Dn = Sn \(A1... An ) в силу (20), имеем

3 АЗБУКА ТЕОРИИ ГРАФОВ

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

Для графа G через V (G) и E(G) обозначим множества вершин и ребер G соответственно. Если (u, v) E(G), то говорят, что вершины u и v смежны. Ребро (u, v) и вершина v инцидентны. Если два ребра инцидентны одной и той же вершине, то они тоже называются смежными.

Степенью degG (v) вершины v в псевдографе G называют сумму числа всех ребер, инцидентных v, и числа петель, инцидентных v (таким образом, каждая петля подсчитана дважды). Вершина степени 0 называется изолированной, вершина степени 1 – висячей.

Утверждение 3.1. Сумма степеней вершин любого псевдографа равна удвоенному числу его ребер.

ДОКАЗАТЕЛЬСТВО. Каждое ребро вносит в указанную сумму вклад 2.

Говорят, что графы G1 = (V1, E1 ) и G2 = (V2, E2 ) изоморфны, если существует такое взаимно однозначное отображение f : V1 V2, что для любых u, v V Нередко графы будут рассматриваться с точностью до изоморфизма.

Граф G1 = (V1, E1 ) называется подграфом графа G2 = (V2, E2 ), если V1 V2, E1 E2. Граф G1 = (V1, E1 ) называется порожденным подграфом графа G2 = (V2, E2 ), если E1 = {(u, v) E2 | {u, v} V1 }. При этом говорят, что подграф G1 порожден множеством вершин V1.

Маршрут в псевдографе G – это такая последовательность v0, e1, v1, e2,..., en, vn вершин и ребер G, что каждое ребро в этой последовательности инцидентно соседним ему вершинам. При этом говорят, что маршрут ведет из v0 в vn. Если v0 = vn, то маршрут называется замкнутым. Маршрут, все вершины которого различны, называется путем. Замкнутый маршрут, все вершины которого различны, называется циклом. Длина маршрута – это число его ребер. Расстоянием G (u, v) в графе G между вершинами u и v называется длина кратчайшего пути, соединяющего их.

Говорят, что граф G связен, если для любых его вершин u и v найдется путь, ведущий из u в v. Максимальный по включению связный подграф графа G называют компонентой связности G.

Полный граф Kn – это граф с n вершинами, любые две из которых соединены ребром. Множество вершин полного двудольного графа Km,n состоит из двух подмножеств V1 и V2, |V1 | = m, |V2 | = n, а E(Km,n ) = {(u, v) | u V1, v V2 }.

Имеется ряд способов, чтобы задать граф:

1) рисунок;

2) матрица инциденций;

3) матрица смежности;

4) список ребер;

5) списки инцидентностей.

3.2 Деревья, характеризации деревьев Связный граф без циклов называется деревом. Лес – это граф без циклов. Таким образом, лес – это граф, каждая компонента связности которого – дерево, а дерево – это связный лес.

Теорема 3.2. Пусть G = (V, E) – граф с n вершинами. Тогда следующие условия эквивалентны:

(а) G – дерево;

(б) любые две вершины в G соединены ровно одним путем;

(в) G связен и имеет n 1 ребро;

(г) G имеет n 1 ребро и не имеет циклов;

(д) G не имеет циклов и добавление к G любого ребра приводит к графу ровно с одним циклом;

(е) G – связный граф, не совпадающий с Kn при n 3, и добавление к G любого ребра приводит к графу с ровно одним циклом.

ДОКАЗАТЕЛЬСТВО. (а) (б). Так как G связен, любые две его вершины соединены хотя бы одним путем. Предположим, что есть два разных пути (v0, v1,..., vt ) и (u0, u1,..., us ), соединяющие вершины x = v0 = u0 и y = vt = us. Пусть i – наименьшее натуральное число, для которого ui = vi, а j = min{k > i | uk {v0, v1,..., vt }}. Можно считать, что uj = vr. Тогда в G есть цикл (vi1, vi,..., vr = uj, uj1,..., ui1 ).

Значит, G – не дерево.

(б) (в). Поскольку любые две вершины соединены путем, граф G связен. Покажем индукцией по числу вершин, что |E| + 1 = |V |.

Если |V | = 1 или |V | = 2, то утверждение очевидно. Пусть |V | > и e = (v, u) – некоторое ребро в G. Рассмотрим H = G \ {e}. Согласно (б) в H нет пути из u в v. Пусть V1 – множество вершин, которые в G соединены с u путями, не проходящими через v, а V2 – множество вершин, которые в G соединены с v путями, не проходящими через u. Тогда подграф G1 графа G, порожденный множеством V1, связен, поскольку каждую его вершину какой-то путь, использующий лишь вершины из V1, соединяет с u. Аналогично, подграф G2 графа G, порожденный множеством V2, связен. По индукционному предположению, e1 = |V1 | 1, e2 = |V2 | 1, где ei – число ребер в Gi (i = 1, 2). Следовательно, (в) (г). Предположим, что в G = (V, E) есть цикл C с k вершинами. Для каждой вершины v V \ C найдется кратчайший путь от v до C (возможно, их несколько). Поставим каждой такой вершине в соответствие первое ребро этого пути. Поскольку любое ребро будет поставлено в соответствие не более чем одной вершине, число таких ребер не менее n k. Отсюда |E| k + (n k), что противоречит (в).

(г) (а). Так как G не имеет циклов, то G – лес. Если G имеет k компонент связности (деревьев), то (поскольку (а) (в)) в G ровно n k ребер. По условию |E| = n 1. Значит, k = 1.

(б) (д). Так как любые две вершины соединены ровно одним путем, добавив любое ребро, получим ровно один цикл.

(д) (е). Если бы G не был связным, то добавление ребра, соединяющего разные компоненты связности, давало бы граф без циклов.

(е) (а). Предположим, что в G есть цикл. Этот цикл должен быть 3-циклом, иначе добавление диагонали привело бы к наличию как минимум трех циклов. Пусть это цикл (x, y, z). Так как G = K3 и связен, то найдется вершина v, смежная с x, y или z. Можно считать, что v смежна с x. Тогда добавление ребра (v, y) приводит к графу с более чем одним циклом.

Следствие 3.3. В любом дереве T = (V, E) c |V | 2 имеется не менее двух висячих вершин.

3.3 Кодирование деревьев Задавать деревья можно по-разному. В гл. 2 описывался способ задания плоских корневых деревьев. Одним из экономных способов записи деревьев является код Прюфера.

Пусть T – некоторое дерево, вершины которого занумерованы числами 1, 2,..., n. Тогда код Прюфера для T строится по следующим правилам.

Удаляем висячую вершину с наименьшим номером и записываем номер ее соседа. В оставшемся дереве снова удаляем висячую вершину с наименьшим номером и выписываем номер ее соседа рядом с уже записанным. Повторяем эту процедуру n 1 раз. Полученная последовательность из n 1 чисел называется кодом Прюфера для T.

Теорема 3.4. Для любой последовательности (a1,..., an1 ) натуральных чисел такой, что существует единственное дерево на множестве вершин {1, 2,..., n}, код Прюфера которого совпадает с данной последовательностью.

ДОКАЗАТЕЛЬСТВО. Заметим сначала, что в силу следствия 3. последним числом в коде Прюфера должно быть n.

Единственность. Пусть T – дерево и (a1,..., an1 ) – его код Прюфера. Обозначим через bi (i = 1, 2,..., n 1) номер вершины, которую мы удаляли на шаге i. Очевидно, bi {b1,..., bi1, ai }. Кроме того, bi {ai+1,..., an }, поскольку при j > i вершина aj принадлежит дереву T \ {b1,..., bi }. И наоборот, если k {b1,..., bi1, ai, ai+1,..., an1 }, то k является висячей вершиной в T \ {b1,..., bi1 } (иначе на какомнибудь шаге q > i она оказалась бы соседней с висячей вершиной bq и совпала бы с aq ). Значит, Таким образом, последовательность (a1,..., an1 ) однозначно (по правилу (23)) определяет последовательность {b1,..., bn1 }. Поскольку (bi, ai ) – ребро в T для любого i {1,..., n 1}, последовательность (a1,..., an1 ) однозначно определяет T.

Существование. Пусть последовательность (a1,..., an1 ) удовлетворяет (22). По правилу (23) построим соответствующую ей последовательность {b1,..., bn1 } и проведем ребра (bi, ai ) для всех i {1,...,n 1}. Получим некоторый граф G. Обозначим Покажем, что (а) G – дерево, (б) код Прюфера для G есть (a1,..., an1 ).

Для доказательства (а) достаточно убедиться, что bi – висячая вершина в Gi для любого i, а для (б) – что номер любой висячей вершины в Gi не меньше, чем bi.

Поскольку согласно (23) ai {b1,..., bi1 }, имеем ai V (Gi ). Следовательно, bi смежна с некоторой вершиной из Gi. Предположим, что bi смежна в Gi с какой-то вершиной x = ai. Тогда ребро, соединяющее bi с этой вершиной, должно иметь вид (aj, bj ), где j > i, так как bj V (Gi ). Поскольку все bk различны, имеем bj = bi. Значит, bi = aj и j > i, что противоречит (23). Следовательно, наше предположение неверно, и вершина bi смежна в Gi лишь с ai. Итак, все Gi являются деревьями.

Предположим теперь, что в Gi есть висячая вершина k и k < bi. Поскольку при построении последовательности {b1,..., bn1 } по правилам (23) мы не положили bi = k, то это значит, что или k {b1,..., bi1 }, или k {ai, ai+1,..., an1 }. Первое невозможно, так как {b1,..., bi1 } V (Gi ) =. Значит, k = aj для некоторого j > i. Как отмечалось, bj – висячая вершина в Gj, смежная с aj. Но aj = k – висячая вершина в Gi, а следовательно, и в Gj. Таким образом, Gj имеет только две вершины:

Теорема 3.5. (Теорема Кэли.) Число n-вершинных деревьев с помеченными вершинами равно nn2.

3.4 Эйлеровы обходы Эйлеров обход (цикл) в псевдографе G – это такой замкнутый маршрут M в G, что каждое ребро входит в M ровно один раз. В известной в свое время задаче о кенигсбергских мостах требовалось указать эйлеров цикл в одном из мультиграфов. Задачи о рисовании фигур без отрыва карандаша от бумаги тоже сводятся к изучению эйлеровых обходов.

Назовем псевдограф эйлеровым, если в нем есть эйлеров цикл. Ясно, что эйлеров псевдограф связен.

Теорема 3.6. Для связного псевдографа G = (V, E) следующие утверждения эквивалентны:

(а) G – эйлеров псевдограф;

(б) каждая вершина псевдографа G имеет четную степень;

(в) множество ребер псевдографа G можно разбить на простые циклы.

ДОКАЗАТЕЛЬСТВО. (а) (б). Пусть M – эйлеров цикл в G, v – произвольная вершина в G. При каждом прохождении M через v используются два ребра, инцидентных v.

(б) (в). Индукцией по числу ребер в G. Пусть G – наименьший по числу ребер псевдограф, для которого наше утверждение не доказано. Если в G нет ребер, то утверждение тривиально. Если G связный и нетривиальный, то степень каждой вершины не меньше двух и по следствию 3.3 в G есть цикл C. Удалив ребра C из G, снова получим псевдограф (обозначим его G ), степени всех вершин которого четны.

По индукционному предположению ребра каждой компоненты связности псевдографа G можно разбить на циклы.

(в) (а). Индукцией по числу ребер в G. Пусть G – наименьший по числу ребер псевдограф, для которого наше утверждение не доказано, и пусть C1 – один из циклов, на которые разбито E(G). Рассмотрим G, полученный из G удалением ребер цикла C1. По индукционному предположению, в каждой компоненте связности Hi псевдографа G есть эйлеров цикл Mi. Из них и цикла C1 легко строится эйлеров цикл для G.

Следствие 3.7. Пусть G – связный псевдограф, x, y V (G). В G существует маршрут, связывающий x с y, который содержит каждое ребро G ровно по одному разу, если и только если степени всех вершин, кроме x и y, четны, а степени x и y нечетны.

3.5 Двудольные графы Мультиграф G = (V, E) называется двудольным, если множество его вершин можно так разбить на две части (доли) V1 и V2, что один из концов любого ребра принадлежит V1, а другой – V2.

Примеры 1. Любой лес – двудольный граф.

2. Циклы четной длины являются двудольными графами, а циклы нечетной длины – не являются таковыми.

Теорема 3.8. Граф G является двудольным, если и только если в G нет циклов нечетной длины.

ДОКАЗАТЕЛЬСТВО. ). Если в G есть цикл нечетной длины, то, как отмечалось в примере 2, G недвудолен.

). Достаточно доказать утверждение теоремы для связных графов.

Выберем произвольную вершину v V (G). Пусть Xi (i = 0, 1, 2,...) – множество вершин графа G, находящихся на расстоянии i от v. Имеем X0 = {v}, X1 = {x V (G) | (x, v) E(G)}. Предположим, что для некоторого i найдутся x, y Xi c (x, y) E(G). Пусть (x0, x1,..., xi ) и (y0, y1,..., yi ), где x0 = y0 = v, xi = x, yi = y являются кратчайшими путями от v до x и y, а xj = yj – последняя общая вершина на этих путях. Тогда цикл (xj, xj+1,..., xi, yi, yi1,..., yj ) имеет нечетную длину.

Из полученного противоречия следует, что каждое ребро в G соединяет Xi с Xi+1 для некоторого i 0. Положим V1 = X0 X2 X4..., Паросочетанием в мультиграфе называется любой набор попарно несмежных ребер. Паросочетание, покрывающее все вершины мультиграфа, называется совершенным паросочетанием. Такое паросочетание содержит |V (G)|/2 ребер.

Для каждого мультиграфа G через (G) обозначим мощность наибольшего паросочетания в G, а через (G) – мощность наименьшего множества вершин, покрывающего все ребра G.

Очевидно, (G) (G) для любого мультиграфа G. Для цикла C длины 5 имеем (C5 ) = 2, (C5 ) = 3. Для полного графа Kn на n вершинах имеем (Kn ) = n/2, (Kn ) = n 1.

Теорема 3.9. (Теорема Книга.) Для любого двудольного мультие графа G ДОКАЗАТЕЛЬСТВО. Пусть G = (V, E) – наименьший по числу ребер двудольный мультиграф, для которого Тогда в G найдется вершина, смежная с двумя или более другими вершинами. Можно считать, что долями G являются V1 и V2, x V1, Ввиду минимальности G имеем (G1 ) = (G1 ), (G2 ) = (G2 ). Учитывая (24) и то, что (Gi ) (G) (i = 1, 2), получаем Пусть Si – множество вершин, покрывающее все ребра Gi, и |Si | = (G) (i = 1, 2). Тогда Обозначим R = S1 S2, r = |R|, t = (G). Далее, обозначим через H подграф мультиграфа G, порожденный множеством вершин (S1 \ R) (S2 \ R) {x}. Пусть долями двудольного мультиграфа H являются A и B, причем |A| |B|. Имеем Покажем, что A R покрывает все ребра G. Действительно, рассмотрим произвольное ребро e E. Если хотя бы один конец e принадлежит R, то A R покрывает e. Убедимся, что когда оба конца e не принадлежат R, тогда e E(H). Отсюда сразу следовало бы, что A покрывает e. В силу (25) ребра (x, y1 ) и (x, y2 ) принадлежат E(H). Если e {(x, y1 ), (x, y2 )}, то S1 \R и S2 \R должны быть инцидентны e, и, следовательно, e соединяет S1 \ R с S2 \ R. Снова оба конца e принадлежат V (H).

Таким образом, Для любого мультиграфа G = (V, E) и любого W V через NG (W ) обозначим множество {v V \ W | w W : (w, v) E}.

Следствие 3.10. (Теорема Книга – Оре.) Пусть G = (V, E) – двуе дольный мультиграф с долями V1 и V2. В G существует паросочетание, покрывающее V1, если и только если ДОКАЗАТЕЛЬСТВО. ). Если |NG (A)| < |A| для некоторого A V1, то не существует паросочетания, покрывающего A.

). Предположим, что (G) < |V1 |. Тогда по теореме 3.9 (G) < |V1 |.

Пусть S – множество вершин, покрывающее все ребра G, с |S| = s < |V1 |.

Обозначим A1 = V1 \ S, A2 = V2 \ S. Тогда Другими словами, |A1 | |V2 \ A2 | + 1. Так как S покрывает все ребра G, имеем NG (A1 ) V2 \ A2. Следовательно, Системой различных представителей для семейства множеств {Ai }k называется такой набор {a1,..., ak } элементов множества i=1 Ai, что ai Ai для каждого i {1,..., k} и все ai различны.

Теорема 3.11. (Теорема Холла.) Пусть {Ai }k – семейство подi= множеств множества {v1,..., vn }. Система различных представителей для {Ai }k существует, если и только если для любого подмноi= жества I множества {1,..., k} ДОКАЗАТЕЛЬСТВО. Построим двудольный граф G = (V, E) по следующим правилам: долями V будут множества V1 = {A1,..., Ak } и V2 = {v1,..., vn }, а пара (Ai, vj ) будет ребром, если и только если vj Ai. Тогда наличие паросочетания в G, покрывающего V1 = {A1,..., Ak }, соответствует наличию системы различных представителей для {Ai }k. По следствию 3.10 наличие такого паросочетания в G эквивалентно выполнению (26). Но выполнение (26) для построенного нами графа эквивалентно выполнению (27) для {Ai }k. i= В ряде практических и теоретических задач требуется покрыть множество ребер какого-нибудь графа наименьшим числом паросочетаний.

Поскольку два смежных ребра нельзя покрыть одним и тем же паросочетанием, то для покрытия ребер любого графа требуется не меньше паросочетаний, чем максимальная степень его вершин.

Теорема 3.12. (Теорема Книга.) Пусть G = (V, E) – двудольный мультиграф с максимальной степенью вершин, равной k. Тогда множество E можно разбить на k паросочетаний.

ДОКАЗАТЕЛЬСТВО. Пусть V = V1 V2 – некоторое разбиение V на две доли: |V1 | = n1, |V2 | = n2, n1 n2. Добавим n1 n2 новых вершин к V2, а затем будем добавлять к полученному мультиграфу на 2n1 вершинах ребра, пока не получим k-однородный двудольный мультиграф с 2n1 вершинами. Обозначим этот мультиграф через H.

Для любого A V1 имеем |NH (A)| |A|, поскольку из A выходят k|A| ребер, а каждая вершина из NH (A) инцидентна не более чем k таким ребрам. Значит, по следствию 3.10 существует паросочетание 1, покрывающее V1. Поскольку |V (H)| = 2|V1 |, паросочетание 1 покрывает все вершины H, и H1 = H \ 1 является (k 1)-однородным мультиграфом. Снова, по следствию 3.10, существует паросочетание 2, покрывающее V1. Построим H2 = H1 \ 2 и т. д. Через k шагов будут построены k паросочетаний, в совокупности покрывающих E(H). Удалив из этих паросочетаний ребра, не принадлежащие E(G), получим требуемое разбиение множества ребер G.

3.6 Принцип Дирихле Стандартным способом доказательства существования объектов, обладающих теми или иными свойствами, в дискретной математике является конструирование таких объектов. Но иногда наилучшим оказывется использование мощностных соображений.

Принцип Дирихле состоит в следующем: если k + 1 предметов раскладываются в k ящиков, то хотя бы один ящик содержит более одного предмета.

В качестве применения этой идеи рассмотрим две задачи о турнирах.

Турнир T состоит из множества игроков V и множества E результатов турнира. Множество E состоит из |V | упорядоченных пар элементов множества V, и для любой пары {u, v} V в точности одна из пар (u, v), (v, u) принадлежит E. (Содержательный смысл пары (u, v):

игрок u выиграл у игрока v.) Часто элементы множества игроков изображают точками или кружками на плоскости, а элементы E – дугами, соединяющими эти точки. Поскольку для любой пары {u, v} V имеется ровно две возможности выбора дуги, соединяющей эти вершины, то всего на множестве из n различных игроков можно построить 2( 2 ) различных турниn ров.

Гамильтоновым путем в турнире T = (V, E) c V = {v1,..., vn } называется такая перестановка = (vi1,..., vin ) игроков турнира, что (vij, vij+1 ) E для каждого j {1,..., n 1}. Число различных гамильтоновых путей, которые можно построить на множестве из n игроков, равно n!.

Г. Селе (1943 г.) доказал, что в любом турнире с количеством игроков n число гамильтоновых путей меньше, чем n!23n/4.

Теорема 3.13. Существует турнир с количеством игроков n, содержащий не менее n!2n+1 гамильтоновых путей.

ДОКАЗАТЕЛЬСТВО. Пусть Tn – множество всех турниров на множестве игроков {v1,..., vn }. Как отмечалось, |Tn | = 2( 2 ). Положим Тогда Зафиксируем произвольный гамильтонов путь. Этот путь фиксирует направление n 1 дуг. Значит, существует 2( 2 )n+1 турниров, содержащих. Таким образом, откуда с учетом (28) имеем В последней сумме 2( 2 ) слагаемых. Следовательно, хотя бы одно из них не меньше Назовем турнир T = (V, E) транзитивным, если существует такая перестановка (vi1,..., vin ) его игроков v1,..., vn, что при любых 1 j < k n имеем (vij, vik ) E. Пусть (n) – наибольшее целое число такое, что в любом турнире с количеством игроков n есть транзитивный подтурнир с количеством игроков (n).

Примеры (2) = 2, (3) = 2. Нетрудно доказать, что (4) = 3.

Утверждение 3.14. Справедливо неравенство (n) 1 + log2 n.

ДОКАЗАТЕЛЬСТВО. При n 3 это следует из примера. Пусть утверждение доказано для всех n < n. Рассмотрим произвольный турнир Tn на множестве игроков v1,..., vn.

Случай 1. Число игроков, которых победил игрок vn, не менее (n 1)/2. Не теряя общности, мы можем предположить, что это игроки v1,..., vk, где k (n 1)/2 = n/2. По индукционному предположению подтурнир Tk на множестве {v1,..., vk } содержит некоторый транзитивный подтурнир Tr на каком-то множестве {vi1,..., vir }, где Покажем, что для любого натурального n Действительно, при четном n имеем n/2 = n/2. Пусть n = 2m + 1.

Равенство log2 (n/2) = s означает, что 2s n/2 < 2s+1, т. е.

2s m + 1/2 < 2s+1. Но тогда, поскольку m целое, 2s m, откуда s log2 m = log2 n/2. Последнее неравенство эквивалентно (29).

Таким образом, r 1 + log2 (n/2) = log2 n. Поскольку vn победил всех игроков из Tr, в Tn есть транзитивный подтурнир с количеством игроков r + 1.

Случай 2. Число игроков, которых победил игрок vn, меньше, чем (n 1)/2. Тогда число победивших vn больше (n 1)/2, и снова можно рассуждать как в случае 1.

Теорема 3.15. Справедливо неравенство (n) 1 + 2 log2 n.

ДОКАЗАТЕЛЬСТВО. Нам требуется показать, что в Tn есть турнир, не содержащий транзитивного подтурнира с количеством игроков Пусть I – класс тех турниров из Tn, которые содержат транзитивный подтурнир с количеством игроков k. Тогда где A пробегает все k-элементные подмножества множества {1,..., n}, – все перестановки элементов множества A, а IA, обозначает множество таких турниров T I, что подтурнир турнира T на множестве A транзитивен и старшинство игроков из A порождается перестановкой.

Понятно, что |IA, | = 2( 2 )(2). Следовательно, Значит, Tn \ I =.

Содержание

1 АЛГЕБРА ВЫСКАЗЫВАНИЙ И

БУЛЕВЫ ФУНКЦИИ

1.6 Применение алгебры высказываний в теории

2 ЭЛЕМЕНТЫ КОМБИНАТОРИКИ