Глава 3. Элементы комбинаторики.
39. Комбинаторика. Основные правила комбинаторики - правила суммы и произведения. Комбинаторные конфигурации – выборки. Размещения с повторениями – все выборки. Формула, пример.
40. Размещения без повторений – инъективные выборки. Формула, пример. Перестановки и их групповые свойства. Сочетания – монотонные выборки (в т.ч. инъективные сочетания без повторений). Формулы, пример.
41. Три основных свойства сочетаний. Бином Ньютона. Суммы биномиальных коэффициентов. Треугольник Паскаля. Его связь с биномиальными коэффициентами.
42. Разбиения. Числа Стирлинга 2 рода. Теорема о рекуррентной формуле. Теорема о разложении по биномиальным коэффициентам.
43. Количество всех сюрьективных выборок. Числа Стирлинга 1 рода. Связь чисел Стирлинга. Числа Белла – количество всех разбиений. Теорема о числах Белла.
44. Принцип включений и исключений. Теорема обращения. Формулы обращения для биномиальных коэффициентов. Замкнутые формулы для чисел Стирлинга (все – без доказательства, только схемы доказательств). Пример.
45. Определение рекуррентного соотношения (рекуррентной формулы). Линейные и однородные соотношения, возвратная последовательность. Характеристический многочлен. Решение рекуррентного соотношения (определение и простой пример).
46. Примеры рекуррентных соотношений: арифметическая и геометрическая прогрессии, числа Фибоначчи (задача о кроликах и о последовательностях нулей и единиц). Процесс последовательных разбиений.
47. Теорема о решении однородного линейного рекуррентного соотношения (с доказательством). Пример.
48. Решение неоднородного рекуррентного соотношения. Нахождение частного решения. Пример.
49. Определение производящей функции. Известные примеры: сумма геометрической прогрессии, бином Ньютона. Простейшие формальные операции над рядами.
50. Использование рядов для доказательства тождеств. Деление многочленов и производящие функции. Таблица производящих функций.
51. Решение рекуррентных соотношений с помощью производящих функций. Общий принцип и примеры. Производящая функция чисел Фибоначчи. Неоднородный случай.
Глава 4. Теория графов.
52. Определение графа как отношения. Смежность, множества смежности. Графическая интерпретация графа (диаграммы). Экскурс в историю: Кенигсбергские мосты, задача о трех колодцах, игра «Вокруг Света» (Гамильтон), раскраска карты в 4 цвета, закон Кирхгофа, изомеры предельных углеводородов, потоки в сетях и др.
53. Мультиграф. Псевдограф (с петлями). Ориентированный граф. Дополнение графа. Степень вершины. Степень графа. Лемма о рукопожатиях. Следствие о количестве «нечетных» вершин. Утверждение о двух вершинах одинаковой степени.
54. Примеры (виды) графов: пустой, полный, двудольный (в т.ч. полный), звезда, простой цикл, скелеты платоновских тел, графы Куратовского, граф Петерсона, звезда Давида. Планарность графа. Связность графа.
55.Представление графов в компьютере. Матрица смежности. Матрица инциденций. Списки смежности. Массив дуг. Достоинства и недостатки представлений.
56. Обходы графов*: поиск в ширину и в глубину. Теорема о корректности обходов и следствия* из нее. Пример обхода.
57. Изоморфные графы. Помеченные графы, их количество. Формула Пойа. Проблема изоморфности и поиск полного инварианта. Примеры неполных инвариантов: n, m, вектор степеней, плотность, хроматическое число, порождающие функции. Канонический код графа, двоичный код смежности.
58. Подграф. Остовный и порожденный подграф. Гипотеза восстановления (по колоде). Маршруты, цепи, циклы. Утверждения о простых маршрутах и простых циклах.
59. Эйлеров цикл и эйлеров граф. Критерий эйлеровости графа. Алгоритм построения эйлерова цикла. Теорема о количестве эйлеровых графов (только схема доказательства).
60. Гамильтонов цикл и гамильтонов граф. Необходимые и достаточные условия гамильтоновости графа. Теорема Оре, следствие Дирака. Теорема о количестве гамильтоновых графов (без д-ва). Задача коммивояжера.
61. Связные и несвязные графы. Связность дополнения графа. Лемма о циклическом ребре. Теорема о количестве ребер в графе с k компонентами связности.
62. Метрические характеристики графа. Геодезическая, эксентриситет, радиус, диаметр, центр графа. Пример. Двудольные графы, критерий двудольности.
63. Орграфы. Дуги, узлы. Сильная, односторонняя и слабая связность. Достижимость. Транзитивное замыкание.
64. Деревья. Теорема о деревьях*. Доказать один из пунктов. Следствие о висячих вершинах. Центр дерева. Лес. Остовный подграф.
65. Теорема о количестве деревьев. Код Прюфера*. Пример построения кода и восстановления по нему.
66. Ориентированные, бинарные, упорядоченные деревья. Представление упорядоченных деревьев: список, упакованный массив, польская запись. Примеры представлений. Теорема* об ориентированных деревьях.
67. Обходы бинарных деревьев: прямой, обратный, концевой. Алгоритмы* обходов. Примеры обходов.
68. Ассоциативная память. Способы реализации: упорядоченный массив, неупорядоченный массив, дерево сортировки, хэш-таблица. Алгоритмы* вставки, поиска и удаления для массивов.
69. Деревья сортировки. Алгоритмы* поиска, вставки и удаления для деревьев сортировки.
70. Выровненные, заполненные и полные деревья. Сбалансированное дерево. Оценка высоты этих видов деревьев (только схема доказательства). Балансировка* деревьев. Пример балансировки.
71. Отыскание кратчайшего остова. Постановка задачи. Алгоритм* Краскала.
72. Отыскание кратчайшего остова. Алгоритм* Прима. Задача Штейнера.
73. Точки сочленения, мосты и блоки. Свойства точек сочленения и мостов. Вершинная и реберная связность. Теорема о связи вершинной и реберной связности. Примеры.
74. Непересекающиеся цепи и разделяющие множества. Теорема Менгера в вершинной форм (только схема д-ва). Критерий вершинной связности. Теорема Менгера в реберной форме. Критерий реберной связности.
75. Лемма Холла (с д-вом) и ее варианты. Примеры применения.
76. Потоки в сетях. Постановка задачи об отыскании максимального потока. Насыщенные, пустые, допустимые дуги. Разрезы. Алгоритм* Форда-Фалкерсона.
77. Потоки в сетях. Насыщенные, пустые, допустимые дуги. Лемма о разрезах. Теорема* Форда-Фалкерсона. Связь с теоремой Менгера. Алгоритм* Эдмондса-Карпа.
77. Компоненты сильной связности. Алгоритм* отыскания КСС.
78. Кратчайшие пути. Алгоритм* Дейкстры.
79. Кратчайшие пути. Алгоритм* Флойда.
80. Кратчайшие пути. Алгоритм* Форда-Беллмана.
81. Независимые и покрывающие множества вершин и ребер. Пример. Связь чисел независимости и чисел покрытий (доказать любое неравенство).
82. Построение независимых множеств вершин. Полный перебор, поиск с возвратами*, улучшенный перебор*. Доминирующие множества. Задача о наименьшем покрытии*.
83. Хроматическое число графа. Примеры. Оценки для хроматического числа (с д-вом). Хроматическое число дополнения графа (без д-ва). Точный алгоритм раскрашивания.
84. Приближенный алгоритм* последовательного раскрашивания. Улучшенный алгоритм* последовательного раскрашивания.
85. Планарный граф. Теорема Эйлера и следствия из нее. Теорема о пяти красках.
* - можно воспользоваться заранее подготовленными справочными материалами.