Список вопросов к экзамену

Список вопросов к экзамену по курсу
«Избранные вопросы теории графов»

Лектор: доцент Д. С. Романов.

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

2. Матрицы смежности, инцидентности, степеней вершин, полустепеней исхода и захода. Интерпретация элементов степеней матрицы смежности.

3. Теоремы о связи матриц инцидентности для мультиграфов и мультиорграфов с их матрицами смежности.

4. Теоремы о тотальной унимодулярности и ранге матрицы инцидентности мультиорграфа.

5. Теорема Кирхгофа о деревьях.

6. Утверждения о числе остовных деревьев в полном графе (доказательство Кэли) и о формуле для древесной сложности мультиграфа.

7. Алгебра смежности мультиграфа. Теоремы о размерности алгебры смежности при заданном диаметре мультиграфа и при заданном числе его собственных значений.

8. Утверждение о величине некоторых коэффициентов характеристического многочлена графа.

9. Теорема о верхней границе для собственных значений простого графа.

10. Теорема о собственных значениях регулярного мультиграфа.

11. Критерий принадлежности матрицы J_n алгебре смежности мультиграфа. Следствие о виде матрицы J_n.

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

13. Теорема о связи характеристических многочленов регулярного мультиграфа и его реберного мультиграфа.

14. Выражение сложности регулярного мультиграфа через его характеристический многочлен.

15. Теорема о сложности реберного мультиграфа, построенного для регулярного связного мультиграфа.

16. Верхняя оценка для сложности регулярного связного мультиграфа.

17. Циркулянтные графы и их спектры. Спектры полных графов, циклов, гипероктаэдральных графов.

18. Теорема о спектрах дополнительных графов.

19. Матрицы подстановок. Теорема о перестановочности матрицы подстановки, соответствующей автоморфизму графа, с матрицей смежности графа.

20. Теорема о связи матриц подстановок с простыми собственными значениями графа.

21. Теорема об автоморфизме, порядок которого больше 2.

22. Вершинно-транзитивные и реберно-транзитивные графы. Теорема о двудольности реберно-транзитивных графов.

23. Теорема о простом собственном значении вершинно-транзитивного графа.

24. Реберно-симметрические графы. Теорема о простых собственных значениях реберно-симметрических графов.

25. Число помеченных графов и орграфов. Рекуррентная формула для помеченных связных графов.

26. Теорема об асимптотике отношения числа помеченных связных n-графов к числу всех помеченных n-графов.

27. Лемма о перечислении помеченных графов.

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

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

30. Перечисление помеченных блоков.

31. Теорема об асимптотике числа блоков.

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

33. Связь циклового индекса знакопеременной группы с цикловым индексом симметрической группы.

34. Лемма Бернсайда (с доказательством) и ограниченная форма леммы Бернсайда (формулировка).

35. Теорема Д. Пойа о перечислении (для случая одной переменной с доказательством, для случая многих переменных – формулировка).

36. Теорема о перечислении инъективных функций.

37. Перечисление корневых непомеченных деревьев. Рекуррентная формула для числа корневых деревьев.

38. Теорема о характеристике неподобия для графов.

39. Теорема Р. Оттера о характеристике неподобия для деревьев.

40. Теорема Р. Оттера о производящей функции для непомеченных деревьев.

41. Перечисляющий многочлен для n-графов.

42. Асимптотика числа n-графов.

43. Связь производящей функции для непомеченных графов с производящей функцией для непомеченных связных графов. Рекуррентная формула для числа непомеченных связных графов.

44. Утверждения об асимптотике числа непомеченных связных n-графов и n-блоков.

45. Константная форма теоремы перечисления степенной группы.

46. Перечисление самодополнительных графов.

Список литературы

I. Основной список

1. Гаврилов Г. П., Романов Д. С., Методы линейной алгебры в теории графов. — М.: изд-во ВМиК МГУ, 1996 г.

2. Харари Ф., Палмер Э., Перечисление графов. — М.: «Мир», 1977.

3. Стенли Р. Перечислительная комбинаторика. — М.: «Мир». I том, 1992; II том, 2005.

II. Дополнительный список

1. Харари Ф., Теория графов. — М.: «Мир», 1973 г.

2. Цветкович Д., Дуб М., Захс Х., Спектры графов. Теория и применение. — Киев: «Наукова думка», 1984 г.

3. Де Брёйн Н., Теория перечисления Пойа // В сб. «Прикладная комбинаторная математика». — М.: «Мир», 1968, стр. 61-106.

4. Пойа Д., Комбинаторные вычисления для групп, графов и химических соединений // в сб. «Перечислительные задачи комбинаторного анализа». — М.: «Мир», 1979, стр. 36-138.

5. Оттер Р., Число деревьв. — Там же, стр. 139-159.

6. Айгнер М., Комбинаторная теория. — М.: «Мир», 1982.

7. Риордан Дж., Введение в комбинаторный анализ. — М.: ИЛ, 1963.

8. Сачков В. Н., Введение в комбинаторные методы дискретной математики. — М.: «Физматлит», 2004.

9. Татт У. Т., Теория графов. — М.: «Мир», 1988.

10. Чандрасекхаран К., Введение в аналитическую теорию чисел. — М.: «Мир», 1974, стр. 77-79.