Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой



Скачать 13.98 Kb.
Дата08.10.2012
Размер13.98 Kb.
ТипВопросы к экзамену
Вопросы к экзамену

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

пм 4 курс


  1. История возникновения и развития теории графов. Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой.

  2. Понятие графа, основные определения (вершины, ребра, дуги, ориентированные и неориентированные графы, простой граф, петли, кратные ребра, виды графов, подграфы и дополнения, операции над графами и т.д.). Примеры.

  3. Маршруты, цепи, пути, циклы. Связность, компоненты связности. Точки сочленения. Разрезы. Примеры.

  4. Эйлеров путь, эйлеров цикл. Определение, основные результаты. Примеры.

  5. Гамильтонов путь, гамильтонов цикл. Определение, основные результаты. Примеры.

  6. Планарные графы. Формула Эйлера. Критерий планарности. Примеры.

  7. Деревья. Понятие дерева, характеризация деревьев. Покрывающее дерево, алгоритм построения. Примеры.

  8. Раскраска графов. Вершинная k-раскраска, основные определения, основные результаты. Задача о раскрашивании карт, ее связь с вершинной раскраской графа. Примеры.

  9. Время выполнения программ. Степень роста. Правило сумм, правило произведения. Основные правила анализа программ. Примеры.

  10. Представление графов: матрица смежности, матрица инциденций, списки смежности. Преимущества и недостатки. Примеры.

  11. Обходы графов: в ширину и глубину (рекурсивная и нерекурсивная реализация). Алгоритмы, основанные на алгоритмах обхода: нахождение компонент связности, поиск кратчайших путей, топологическая сортировка, построение стягивающего дерева, построение множества фундаментальных циклов в графе). Время выполнения, примеры.

  12. Нахождение кратчайших путей. Понятие взвешенного графа. Алгоритмы нахождения кратчайших путей от выделенной вершины: алгоритм Форда-Беллмана, Дейкстры, алгоритм нахождения кратчайших путей в бесконтурных графах. Алгоритм Флойда. Время выполнения и сравнительная характеристика. Примеры.

  13. Потоки в сетях.


Похожие:

Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЗанимательные задачи наглядной геометрии
Например, зна­менитая задача о семи кенигсбергских мостах (о ней будет рассказа­но дальше), которую решил великий Эйлер и с которой,...
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЗадача на сложение. Головоломка. Занятие Отгадывание ребусов. Задача в стихах на сложение. Упражнения в анализе геометрической фигуры
Математический кружок является одним из основных видов систематической внеклассной работы
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЛекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой icon2. Задача «метод» это задача, метод решения которой можно использовать при решении похожих задач
Известно, что задача моет служить не только целью, но и средством обучения. Учиться решать задачи с помощью опорных (ключевых, базисных)...
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconПермь 2007 Разбор типовых задач Задача 1
Задача в партии из 10 деталей две бракованные. Найти вероятность того, что среди выбранных на удачу четырех деталей окажется одна...
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЛабораторная работа №2 Транспортная задача
Транспортная задача (Задача Монжа — Канторовича) — задача об оптимальном плане перевозок продуктов из пунктов отправления в пункты...
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЗадача №1 Определите продолжительность видимости Сириуса 28 февраля. Задача №2
Предлагаются задачи, включавшиеся в олимпиады проводимые Дворцом творчества детей и молодежи в 1999-2005 годах
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconТранспортная задача линейного программирования
Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей
Задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой iconЗадача 1 Задача 2 Медицина. Задача 3 Основные понятия моделирования
Модель — это некоторое упрощенное подобие реального объекта, явления или процесса
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org