Экзаменационная программа (2010)_2

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

по курсу «Теория графов и комбинаторика» III семестр

для группы А-13-08

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. Формула включений – исключений.