Графы, 9 класс: примеры с решением, страница 1
Задания, которые прислали ученики. Каждое решено по шагам, как в тетради.
Расстояния между городами указаны в таблице. Определите минимальную длину пути от пункта A до пункта Z. A B C D E F Z ------------------------ A 4 6 33 B 4 1 C…
Поиск количества путей в ориентированном графеСколько существует различных маршрутов от города А до города М, которые проходят через город Ж, но не проходят через город В?
Поиск кратчайшего пути по таблицеМежду городами проложены дороги, протяженность которых указана в таблице. (Отсутствие числа в таблице означает отсутствие прямой дороги между пунктами). Какова…
Поиск кратчайшего пути по таблицеОпределите длину кратчайшего пути из A в B по данным о дорогах, приведённым в таблице (если в таблице отсутствует число, это значит, что прямой дороги между…
Поиск длины пути в графеТеперь мы можем определить количество путей от дома до школы. В нашем примере видно, что есть такие пути из А в Б: А → В → Г → Б: ? А → Д → В → Г → Б: ? А → Д…
Симметричная матрица смежности (весовая таблица графа)Заполните симметричную таблицу расстояний между пунктами А, Б, В, Г, Д, Е, Ж. А Б В Г Д Е Ж ------------------------ А 5 3 Б 5 2 В 5 3 2 Г 5 3 1 Д 3 2 1 Е Ж
Кратчайший путь во взвешенном графе... если добавить рёбрам веса — время дороги в минутах? Заполните пропуски на схеме. Какой путь оказался самым быстрым? Варианты для заполнения пропусков…
Взвешенные графы и кратчайший путьГраф с указанием весов На картинке представлен уже знакомый нам пример с дорогой от дома до школы. До этого мы считали, что время прохождения всех дорог…
Элементы теории графов: вершины и рёбраОпределите количество вершин и рёбер у первой схемы: Вершин: [ ] Рёбер: [ ]
Таблицы смежности графаЗаполните симметричную весовую матрицу для графа с вершинами А, Б, В, Г, Д, Е, Ж по имеющимся данным: А Б В Г Д Е Ж ------------------------ А 4 3 1 Б 10 3 3 В…
Кратчайший путь в ориентированном графеОпределите длины кратчайших путей от вершины А до каждой из остальных вершин графа (алгоритм Дейкстры / поиск кратчайшего пути). Заполните пустые поля у вершин…
Поиск длины пути в графеУстановите соответствие между маршрутами и их длинами согласно схеме дорог. Схема дорог: Из пункта А ведут дороги: в В (4 км), в Г (3 км), в Д (1 км). Дороги…
Ориентированные графы. ЦиклыА это циклический ориентированный граф. [Изображен ориентированный граф с четырьмя вершинами: А, Б, В, Г. Стрелки ориентированы следующим образом: - от А к Б …
Теория графовОпределить по изображению схемы: взвешенный граф или нет, ориентированный или нет.
Теория графовОпределить по изображению графа: 1. Граф взвешенный или невзвешенный? 2. Граф ориентированный или неориентированный?
Теория графовВыбери подходящие термины для этих графов. [Изображение 1: вершины А, Б, В, Г, Д, Е, Ж соединены ненаправленными линиями без указания весов]. ? ? [Изображение…
ГрафыЗаполни рёбра графа по описанию. Максим дружит с Полиной. У Полины есть ещё друзья: Виталик и Алиса. С этими ребятами Максим не знаком, но вместе с Полиной они…
Комбинаторика и алгоритмыВ старой базе знаний есть 7 страниц: A, B, C, D, E, F, G. Некоторые пары страниц соединены двусторонними ссылками: по такой ссылке можно перейти в обе стороны…
Кодирование информацииПри регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов и содержащий только символы из 60-символьного набора. В…
Таблица истинностиМиша заполнял таблицу истинности функции ¬(x ∨ y) ∨ (y ≡ z) ∨ w, но успел заполнить фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы…