Глава 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. Планарный граф. Теорема Эйлера и следствия из нее. Теорема о пяти красках.

* - можно воспользоваться заранее подготовленными справочными материалами.