Спецкурс «Теория графов» пм 4 курс История возникновения и развития теории графов. Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой

Вид материалаЗадача
Подобный материал:
Вопросы к экзамену

Спецкурс «Теория графов»

пм 4 курс

  1. История возникновения и развития теории графов. Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой.
  2. Понятие графа, основные определения (вершины, ребра, дуги, ориентированные и неориентированные графы, простой граф, петли, кратные ребра, виды графов, подграфы и дополнения, операции над графами и т.д.). Примеры.
  3. Маршруты, цепи, пути, циклы. Связность, компоненты связности. Точки сочленения. Разрезы. Примеры.
  4. Эйлеров путь, эйлеров цикл. Определение, основные результаты. Примеры.
  5. Гамильтонов путь, гамильтонов цикл. Определение, основные результаты. Примеры.
  6. Планарные графы. Формула Эйлера. Критерий планарности. Примеры.
  7. Деревья. Понятие дерева, характеризация деревьев. Покрывающее дерево, алгоритм построения. Примеры.
  8. Раскраска графов. Вершинная k-раскраска, основные определения, основные результаты. Задача о раскрашивании карт, ее связь с вершинной раскраской графа. Примеры.
  9. Время выполнения программ. Степень роста. Правило сумм, правило произведения. Основные правила анализа программ. Примеры.
  10. Представление графов: матрица смежности, матрица инциденций, списки смежности. Преимущества и недостатки. Примеры.
  11. Обходы графов: в ширину и глубину (рекурсивная и нерекурсивная реализация). Алгоритмы, основанные на алгоритмах обхода: нахождение компонент связности, поиск кратчайших путей, топологическая сортировка, построение стягивающего дерева, построение множества фундаментальных циклов в графе). Время выполнения, примеры.
  12. Нахождение кратчайших путей. Понятие взвешенного графа. Алгоритмы нахождения кратчайших путей от выделенной вершины: алгоритм Форда-Беллмана, Дейкстры, алгоритм нахождения кратчайших путей в бесконтурных графах. Алгоритм Флойда. Время выполнения и сравнительная характеристика. Примеры.
  13. Потоки в сетях.