Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов. Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой
| Вид материала | Задача |
- Задача является np-полной для кубических планарных графов, реберных графов, ориентированных, 39.45kb.
- 1. Элементы теории графов Введение в теорию графов: основные понятия и определения., 32.17kb.
- Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной, 160.59kb.
- Спецкурс проходит по вторникам с 18: 30 до 19: 50 в ауд. 301 лк. Первая лекция состоится, 20.89kb.
- «Применение информационный технологий в теории графов», 272.84kb.
- Лекция 12: Алгоритмы на графах и деревьях, 395.7kb.
- Задачи на графах. 17 Задачи на графах., 255.85kb.
- Задачи на графах. 16 Задачи на графах., 319.52kb.
- Билеты по Дискретной математике «Теория Графов», 12.79kb.
- Задание графов соответствием 9 > Матричное представление графов 10 Вопросы применения, 230.14kb.
Вопросы к экзамену
Спецкурс «Теория графов»
пм 4 курс
- История возникновения и развития теории графов. Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой.
- Понятие графа, основные определения (вершины, ребра, дуги, ориентированные и неориентированные графы, простой граф, петли, кратные ребра, виды графов, подграфы и дополнения, операции над графами и т.д.). Примеры.
- Маршруты, цепи, пути, циклы. Связность, компоненты связности. Точки сочленения. Разрезы. Примеры.
- Эйлеров путь, эйлеров цикл. Определение, основные результаты. Примеры.
- Гамильтонов путь, гамильтонов цикл. Определение, основные результаты. Примеры.
- Планарные графы. Формула Эйлера. Критерий планарности. Примеры.
- Деревья. Понятие дерева, характеризация деревьев. Покрывающее дерево, алгоритм построения. Примеры.
- Раскраска графов. Вершинная k-раскраска, основные определения, основные результаты. Задача о раскрашивании карт, ее связь с вершинной раскраской графа. Примеры.
- Время выполнения программ. Степень роста. Правило сумм, правило произведения. Основные правила анализа программ. Примеры.
- Представление графов: матрица смежности, матрица инциденций, списки смежности. Преимущества и недостатки. Примеры.
- Обходы графов: в ширину и глубину (рекурсивная и нерекурсивная реализация). Алгоритмы, основанные на алгоритмах обхода: нахождение компонент связности, поиск кратчайших путей, топологическая сортировка, построение стягивающего дерева, построение множества фундаментальных циклов в графе). Время выполнения, примеры.
- Нахождение кратчайших путей. Понятие взвешенного графа. Алгоритмы нахождения кратчайших путей от выделенной вершины: алгоритм Форда-Беллмана, Дейкстры, алгоритм нахождения кратчайших путей в бесконтурных графах. Алгоритм Флойда. Время выполнения и сравнительная характеристика. Примеры.
- Потоки в сетях.