Лекции. Теория графов и комбинаторика (стр. 13 )

Утверждение 4.

Если – корень характеристического уравнения, то является решением уравнения .

Утверждение 5.

Если последовательности и являются решением уравнения , то любая их линейная комбинация также является решением этого уравнения.

Теорема 1. (Общее решение однородного уравнения)

Пусть – все корни характеристического уравнения, имеющие кратности . Тогда общее решение однородного уравнения имеет вид .

При фиксированных значениях получим частное решение.

Для нахождения частного решения используют начальные условия:

Пример.

Решить неоднородное уравнение.

Лекция № 16.

МЕТОД ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ.

Пример.

Пусть известны . Как найти ?

Аналогично .

Пример. (Задача о встречах)

Найти число перестановок n элементов, при которых ровно k элементов остаются на месте (k неподвижных элементов).

В общем случае задача ставится так:

Имеется N объектов, они могут обладать свойствами . Для каждого известно число объектов, обладающих свойствами и, возможно, другими. Требуется найти число объектов, обладающих ровно k свойствами из m.

Теорема 1.

Пусть , тогда

(общая формула включений-исключений).

В частности число объектов, не обладающих ни одним из свойств (частная формула включений-исключений).

4Если объект обладает ровно k свойствами, то в правой части формулы (1) он учтён только в слагаемом для r=k, причём ровно 1 раз.

Пусть объект А обладает ровно p (p>k) свойствами. Тогда в правой части формулы (1) он учтён в слагаемых для . В каждое такое слагаемое А входит ровно раз, т. к. имеется ровно подмножеств , содержащих А. Покажем, что (3).

Рассмотрим формулу бинома .

Дифференцируем:

Ещё раз дифференцируем:

...

После k дифференцирований: .

Положим t = –1:

Поделим на и тем самым докажем, что формула (3) имеет место.

Итак, в правой части формулы (1) объект, обладающий ровно k свойствами, учтён ровно 1 раз, остальные объекты учтены 0 раз, т. е. формула (1) верна. Формула (2) получается из (1) при k =0.3

Пример.

Пусть , объекты – элементы множества . Свойство стоит в принадлежности множеству .

Тогда (каждый элемент обладает хотя бы одним свойством).

По формуле (2)

Пример.

Объекты – перестановки на множестве . Свойство – элемент неподвижен, .

Тогда

При этом

.

При n=3, k=1 получим

Три такие перестановки: .

При n=3, k=2 получим (Если 2 элемента на месте, то и 3-й тоже на месте).

При n=3, k=3 получим

Перестановка: .

При n=3, k=0 получим

Две такие перестановки-циклы: .

Пример.

– количество простых чисел . Вычислим .

Число – простое оно не делится на простые числа (это легко доказать, используя разложение n на простые множители , число 1 по определению простым не является).

В случае чисел достаточно проверить, что число не делится на .

Итак, N = 100. Свойство состоит в делимости на

Количество чисел среди , не делящихся на 2, 3, 5 или 7:

Из множества таких чисел надо удалить 1 и добавить простые числа 2, 3, 5, 7.

Все простые числа:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

В общем случае известна асимптотика при .

(ёв, Валле-Пуссен, XIX век).

Экзаменационная программа.

1.  Сумма степеней всех вершин графа. Лемма о рукопожатиях.

2.  Матрицы смежности и инциденций простого графа. Их свойства.

3.  Эйлеровы циклы и контуры. Необходимые и достаточные условия их существования.

4.  Леммы о рёбрах, циклах и связных компонентах графа.

5.  Дерево, его характеристические свойства.

6.  Число остовов графа. Число деревьев с n помеченными вершинами.

7.  Фундаментальные циклы, цикломатическое число.

8.  Фундаментальные разрезы, коцикломатическое число.

9.  Матрицы фундаментальных циклов и разрезов графа. Соотношение между ними.

10.  Формула Эйлера для связных плоских графов.

11.  Следствия из формулы Эйлера.

12.  Непланарность графов и . Критерий планарности (т. Поптрягина-Куратовского).

13.  Хроматическое число. Теоремы о 5 и 4 красках.

14.  Двудольные графы, длины их простых циклов.

15.  Алгоритм построения минимального остова, его сложность.

16.  Совершенные паросочетания в двудольных графах, необходимое и достаточное условие их существования.

17.  Свойства потоков и разрезов в транспортных сетях.

18.  Теорема о максимальном потоке и минимальном разрезе.

19.  Биноминальные коэффициенты и их свойства.

20.  Число сочетаний без повторений и с повторениями.

21.  Производящие функции и их общие свойства.

22.  Нахождение сочетаний и их числа с помощью производящих функций.

23.  Нахождение числа размещений с помощью экспоненциальных производящих функций.

24.  Числа Фибоначчи, рекуррентное соотношение и его решение.

25.  Числа Стирлинга II рода и числа Белла, их применение в содержательных задачах. Рекуррентные соотношения.

26.  Формула общего решения линейного однородного рекуррентного уравнения.

27.  Формула включений – исключений.