Графы. Основные понятия | Задачи (11 кл. 136 ч.)

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


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



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

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

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

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

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

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

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

Задачи


Задачи


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

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

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

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

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

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

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

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



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







Наверх