ПО КУРСУ «ГИПЕРГРАФЫ И СЕТИ», 2020/2021

Стр 1 из 2Следующая ⇒

ВОПРОСЫ

ПО КУРСУ «ГИПЕРГРАФЫ И СЕТИ», 2020/2021

ТЕОРИЯ ГРАФОВ И СЕТЕЙ (осень)

1. Головоломки. Постановки задач и графовые решения.

2. Исторические аспекты возникновения теории графов

3. Примеры применения теории графов. Задача о покупке автомобиля.

4. Примеры применения теории графов. Задача о прокладке нефтепровода.

5. Гипотеза о 4-х красках

6. Типы графов

7. Основные понятия. Гипотеза Улама

8. Маршруты и связность

9. Степени

10. Задача Рамсея. Обобщение задачи Рамсея

11. Экстремальные графы. Теорема Турана

12. Двудольный граф. Теорема о двудольном графе

13. Граф пересечений. Теорема 1 и 2

14. Клики графа. Граф клик

15. Операции над графами

16. Точки сочленения, мосты и блоки (Харари, стр. 41)

17. Графы блоков и графы точек сочленения (Харари, стр. 45)

18. Деревья. Теорема о семи определениях дерева

19. Матричные представления графов. Матрица смежности и инциденций (Харари, стр. 178-183).

20. Теорема о связи матрицы инциденций исходного графа и матрицы смежности реберного графа

21. Центры и центроиды

22. Следствие о существовании хотя бы 2 висячих вершин в дереве

23. Определение расстояния между вершинами, геодезической цепи, диаметра графа, эксцентриситета вершины, радиуса графа, центральной вершины и центра графа

24. Теорема о центре дерева

25. Определение ветви (3 пункта)

26. Деревья блоков и точек сочленения

27. Независимы циклы и коциклы. Матроиды (Харари)

28. Связность. Теорема Менгера (Харари)

29. Определение остовного дерева

30. Теорема о числе всех деревьев в графе

31. Теорема о числе всех остовных деревьев. Теорема Кирхгофа

32. Циклы. Эйлеровы и гамильтоновы циклы

33. Алгебраический метод поиска всех циклов и всех гамильтоновых циклов

34. Метод ветвей и границ для поиска наикратчайших гамильтоновых циклов

35. Реберные графы

36. Плоские и планарные графы (с. 150, Емеличев)

37. Грани плоского графа. Формула Эйлера (с. 153)

38. Плоские триангуляции (с. 157)

39. Критерии планарности. Теорема Понтрягина – Куратовского (с. 159)

40. Двойственность и планарность (с. 169)

41. Алгоритм укладки графа на плоскости (с. 175)

42. Характеристики непланарных графов (с. 183)

12 Следующая ⇒