Графы: представление, кратчайший путь, число путей
11 класс, углублённый уровень. Обзорный практикум к седьмой паре:
шесть задач по содержанию темы.
- Что нужно сделать
- Шесть задач — по одной на каждый вопрос темы, и все сразу на
странице: решай в любом порядке. Ответил верно — вопрос закрыт.
Ошибся — сразу видно, как это решается, а вопрос остаётся
открытым: кнопка «Новые числа» даёт ту же задачу с другими данными,
и её можно сдать ещё раз. Сколько закрыл, столько и наработал.
Времени нужно около пятнадцати минут: кратчайший путь и подсчёт
путей удобнее решать на черновике.
- Отметка и добор
- Закрыто 6 из 6 — «5», 5 — «4», 3 или 4 — «3». Кнопка
«Получить код» внизу страницы появляется, как только закрыто
три вопроса: можно забрать код сразу, а можно дорешать оставшиеся и
получить код получше — решать самому, до какой отметки добирать.
- Ответ — целое число
- Без единиц измерения и без пробелов:
34, а не
34 км. На КЕГЭ ответ читает машина, и здесь так же.
- Как сдать
- В конце появится код работы и кнопка «Сдать работу»: впишешь
код ученика, кнопка сама откроет форму с уже вписанным кодом.
Переписывать код руками не надо — на этом чаще всего и ошибаются.
- Не успел на уроке
- Открой эту же страницу дома и пройди целиком: вариант будет другой,
а сдаётся всё так же — одним кодом.
Вопросы темы
наработано на—
Подсказка: графы
Основные понятия
Граф — вершины и связи между ними. Связь без направления —
ребро (неориентированный граф), со стрелкой — дуга
(ориентированный). Если у связей есть числа (длина, цена, время),
граф взвешенный. Степень вершины — сколько рёбер из неё
выходит.
Как граф записывают
- матрица смежности — таблица n × n, 1 в клетке: вершины
связаны. У неориентированного графа она симметрична, каждое ребро
записано дважды: рёбер = единиц : 2;
- весовая матрица — в клетке вес связи, пустая клетка — связи
нет;
- списки смежности — у каждой вершины перечислены соседи:
А → Б, В. У ориентированного графа строка вершины — это
выходящие дуги; входящие ищут по всем остальным спискам.
Виды графов
- полный граф — каждая вершина соединена с каждой:
n · (n − 1) : 2 рёбер;
- дерево — связный граф без циклов: ровно n − 1 рёбер.
Связный граф с m рёбрами становится деревом после удаления
m − n + 1 рёбер.
Кратчайший путь (алгоритм Дейкстры)
- у начальной вершины расстояние 0, у остальных — «не известно»;
- взять ближайшую ещё не закреплённую вершину и закрепить её;
- для каждого её соседа: если путь через неё короче записанного —
записать новое расстояние;
- повторять, пока не закреплена нужная вершина.
Прямая дорога не обязательно самая короткая — обход через другие
пункты бывает выгоднее.
Число путей в графе без циклов
Идти по вершинам от начальной: в начальную ведёт 1 путь, а в любую
другую — сумма путей во все вершины, из которых в неё есть
дуга.
| что спрашивают | как считать |
|---|
| через вершину X | (пути до X) · (пути от X до конца) |
| в обход X | вычеркнуть X со всеми дугами и пересчитать |
Материалы подготовлены с использованием технологий искусственного интеллекта.