Уроки 47 - 49
Графы. Основные понятия
(§44. Графы)

Содержание урока

Что такое граф?

«Жадные» алгоритмы. Задача 1

«Жадные» алгоритмы. Задача 2

Кратчайшие маршруты

Некоторые задачи

Вопросы и задания

Задачи

Вопросы и задания

1. Что такое граф?
2. Как обычно задаются связи узлов в графах?
3. Что такое матрица смежности?
4. Что такое петля? Как «увидеть» её в матрице смежности?
5. Что такое путь?
6. Какой граф называется связным?
7. Что такое орграф?
8. Как по матрице смежности отличить орграф от неориентированного графа?
9. Что такое взвешенный граф? Как может храниться в памяти информация о нём?
10. Что такое «жадный» алгоритм? Всегда ли он позволяет найти лучшее решение?

Подготовьте сообщение

а) «Работа с графами в языке Си»
б) «Работа с графами в языке Python»
в) «Жадный алгоритм в задаче коммивояжера»
г) «Метод ветвей и границ»
д) «Алгоритм Литтла»
е) «Задача о максимальном потоке»
ж) «Задача о кенигсбергских мостах»
з) «Использование графов для анализа данных в Интернете»
и) «Теория графов в практических задачах»

Следующая страница Задачи

Cкачать материалы урока