Графы. Основные понятия | Задачи (11_68_pol) (68 часов в уч. год)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)


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



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

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

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

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

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

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

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

Задачи


Задачи


1. Напишите программу, которая вводит из файла весовую матрицу графа и строит для него минимальное остовное дерево.

2. Оцените асимптотическую сложность алгоритма Прима-Крускала.

3. Напишите программу, которая вводит из файла весовую матрицу графа, затем вводит с клавиатуры номера начальной и конечной вершин и определяет кратчайший маршрут.

4. Напишите программу, которая вводит из файла весовую матрицу графа и определяет длины всех кратчайших маршрутов с помощью алгоритма Флойда-Уоршелла.

5. Оцените асимптотическую сложность алгоритмов Дейкстры и Флойда-Уоршелла.

6. Напишите программу, которая решает задачу коммивояжёра для 5 городов методом полного перебора. Можно ли использовать её для 50 городов?

*7. Напишите программу, которая решает задачу 5 (о размещении школы). Для определения кратчайших путей используйте алгоритм Флойда-Уоршелла. Весовую матрицу графа вводите из файла.

Следующая страница §44. Графы



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







Наверх