Разберём, как представлять графы, находить пути и проверять свойства алгоритмами. Задачи будут усложняться — внимательно отслеживай каждый шаг.
№1 · Вершины и рёбра
1 вопрос · 3 балла
1. Поиск вершин на заданном расстоянии
В неориентированном графе вершины обозначены A, B, C, D, E, F, G, H. Рёбра: AB, AC, BD, CE, DE, EF, FG, BG, DH. Из графа удаляют вершины C и F вместе со всеми инцидентными рёбрами. Сколько оставшихся вершин находятся от A на расстоянии ровно 2?
4
3
1
2
№2 · Степени вершин
1 вопрос · 1 балл
2. Степень вершины
В неориентированном графе рёбра заданы списком: AB, AC, AD, BE. Чему равна степень вершины A?
№3 · Матрица смежности
3 пропуска · 2 балла
3. Заполнение строки матрицы
Заполните пропуски в строке матрицы смежности для вершины A. Граф неориентированный, рёбра: AB, AC, CD. Столбцы идут в порядке A, B, C, D.
Строка для A: ; ; ; .
№4 · Представление графа
4 пары · 2 балла
4. Соответствие представлений
Соотнесите способ представления графа с его характеристикой.
Список смежности
Матрица смежности
Список рёбер
Матрица инцидентности
Для каждой вершины перечислены соседние вершины
Таблица связи вершин и рёбер
Перечень пар вершин, соединённых рёбрами
Квадратная таблица наличия рёбер между парами вершин
№5 · Обход графа
5 утверждений · 2 балла
5. Свойства поиска в ширину
Определите истинность утверждений о поиске в ширину в невзвешенном графе. Оценивайте каждое утверждение только с точки зрения алгоритма обхода графа.
Поиск в ширину обрабатывает вершины по уровням удалённости от стартовой вершины.ИстинаЛожь
Поиск в ширину всегда выбирает следующую вершину с максимальным номером.ИстинаЛожь
Для хранения ожидающих обработки вершин обычно используют очередь.ИстинаЛожь
Поиск в ширину нельзя применять к неориентированному графу.ИстинаЛожь
В невзвешенном графе поиск в ширину может найти кратчайшее число рёбер от старта до вершины.ИстинаЛожь
№6 · Кратчайший путь
3 сравнения · 3 балла
6. Сопоставление составных маршрутов
Для каждой пары вычислите суммарный вес обоих маршрутов в одном взвешенном графе, затем сравните длины путей и выберите подходящий знак. Все веса рёбер положительны.
Найдите лишний вариант. Обычные варианты являются деревьями: в них граф связен и не содержит циклов.
Вершины A, B, C; рёбра AB, BC, CA
Вершины A, B, C; рёбра AB, BC
Вершины A, B, C, D; рёбра AB, BC, CD
Вершины A, B, C, D; рёбра AB, AC, AD
№8 · Алгоритм дейкстры
5 шагов · 3 балла
8. Порядок работы алгоритма
Расположите шаги алгоритма Дейкстры для поиска кратчайших расстояний от одной вершины в правильном порядке.
Завершить работу, если нужная вершина выбрана или непосещённых вершин не осталось.
Пометить выбранную вершину как обработанную.
Пересчитать метки соседей, если путь через выбранную вершину короче.
Для стартовой вершины установить расстояние 0, для остальных — бесконечность.
Выбрать непосещённую вершину с минимальной текущей меткой.
№9 · Анализ связности
4 строки · 4 балла
9. Таблица достижимости
Заполните таблицу для неориентированного графа с рёбрами AB, BC, DE. В каждой строке определите, достижима ли вторая вершина из первой.
Пара вершин
Есть ли путь?
Минимальное число рёбер
A и C
A и D
D и E
B и C
№10 · Алгоритмическая стратегия
1 задача · 4 балла
10. Поиск кратчайшего пути во взвешенном графе
В ориентированном взвешенном графе заданы рёбра: A→B (4), A→C (2), C→B (1), B→D (5), C→D (8), B→E (7), D→E (2), D→F (6), E→F (1). Найдите кратчайший путь из вершины A в вершину F и его длину. Покажите 2–3 шага выбора промежуточных вершин алгоритма поиска кратчайших путей.
№1 · Термины
1 вопрос · 1 балл
1. Поиск кратчайшего пути в графе
В неориентированном графе рёбра имеют вид: A—B, A—C, B—D, C—D, D—E, C—F, E—F. Какова длина кратчайшего пути из вершины A в вершину F? Выберите единственный верный ответ.
3 ребра
2 ребра
4 ребра
1 ребро
+10 заданий в этом листе
Зарегистрируйтесь — и соберите свой рабочий лист по этой теме за минуту: заданий столько, сколько нужно.
№2 · Матрица
3 пропуска · 2 балла
2. Представление графа матрицей смежности
Заполните пропуски в описании неориентированного графа.
В матрице смежности неориентированного графа Aij=abc, если вершины i и j соединены ребром. Такая матрица симметрична относительно главной диагонали, поэтому Aij=abc. Для графа без петель элементы главной диагонали равны .
№3 · Соответствие
4 пары · 2 балла
3. Алгоритмы и их назначение
Соедините каждый алгоритм с его основным назначением.
А)Поиск в ширину
Б)Алгоритм Дейкстры
В)Поиск в глубину
Г)Алгоритм Флойда — Уоршелла
1)Обход графа с углублением по непосещённым вершинам
2)Поиск кратчайших путей при неотрицательных весах рёбер
3)Поиск кратчайших расстояний между всеми парами вершин
4)Построение минимального остовного дерева
5)Поиск кратчайшего пути в невзвешенном графе
А
Б
В
Г
№4 · Матрица смежности
4 строки · 2 балла
4. Восстановление свойств графа
Изучите матрицу смежности простого неориентированного графа и заполните пропуски. В строке с названием вершины укажите её степень, а в последней строке определите число рёбер графа.
Вершина
A
B
C
D
Степень
A
0
1
1
0
B
1
0
1
1
C
1
1
0
1
D
0
1
1
0
Число рёбер
4
4
4
4
№5 · Свойства
5 утверждений · 2 балла
5. Связность и циклы
Для каждого утверждения определите, верно ли оно. Основание проверки — определения и свойства неориентированных графов.
Если между каждой парой вершин существует путь, граф связный.ИстинаЛожь
В связном графе обязательно есть цикл.ИстинаЛожь
Дерево — это связный граф без циклов.ИстинаЛожь
В полном графе каждая вершина соединена ровно с одной другой вершиной.ИстинаЛожь
В неориентированном графе сумма степеней всех вершин равна удвоенному числу рёбер.ИстинаЛожь
№6 · Алгоритм
5 шагов · 2 балла
6. Порядок поиска в ширину
Расположите шаги алгоритма поиска в ширину в правильном порядке.
Добавить в очередь непосещённую соседнюю вершину.
Выбрать стартовую вершину и пометить её посещённой.
Повторять обработку, пока очередь не станет пустой.
Извлечь из очереди очередную вершину.
Для извлечённой вершины просмотреть всех соседей.
№7 · Анализ
4 элемента · 2 балла
7. Распознавание дерева
Найдите лишний набор характеристик. Три варианта описывают свойства дерева, один вариант — нет.
Связный граф из 7 вершин и 6 рёбер без циклов.
Связный граф из 8 вершин и 8 рёбер без петель.
Граф, в котором между любыми двумя вершинами существует ровно один простой путь.
Связный граф из 10 вершин и 9 рёбер.
№8 · Сравнение
3 пары · 2 балла
8. Сравнение длин маршрутов
Сравните длины маршрутов в каждом пункте. Все веса рёбер неотрицательны; знак уже не указан, его нужно определить.
1)2+5+34+4+3
2)6+1+43+5+2
3)7+2+15+3+2
№9 · Кратчайший путь
1 задача · 3 балла
9. Алгоритм Дейкстры на взвешенном графе
В ориентированном графе заданы рёбра и их веса: A→B — 4, A→C — 2, C→B — 1, B→D — 5, C→D — 8. Найдите длину кратчайшего пути из вершины A в вершину D. Запишите основные действия алгоритма Дейкстры.
№10 · Подсчёт
4 выражения · 2 балла
10. Подсчёт числа рёбер и степеней
Вычислите значения выражений, используя свойства неориентированных графов.