Графы: читаем схему и находим пути, 7 класс

Как читать граф

Граф помогает изобразить объекты и связи. Например, вершины — остановки, а рёбра — прямые участки маршрута между ними. Сначала объясни смысл вершины и ребра. Здесь рассматриваются графы без петель и без нескольких рёбер между одной парой вершин.

Вершины на наших рисунках отмечены кружками с буквами. Пересечение линий без кружка не создаёт вершину: в этом месте нельзя переходить на другую линию. Положение точек и изгибы рёбер могут меняться, а связи останутся прежними. Длина линии на рисунке сама по себе не означает расстояние.

Степень (валентность) вершины — число рёбер, которые из неё выходят. Изолированная вершина не соединена ни с одной другой: её степень равна нулю. Каждое ребро без петли имеет два конца, поэтому в сумме степеней всех вершин учитывается дважды. Эта сумма равна удвоенному числу рёбер и всегда чётна.

Путь задаёт последовательное движение по рёбрам. Каждая пара соседних букв в записи должна быть соединена ребром. Например, при рёбрах KL и LM запись K–L–M задаёт путь из двух рёбер. Число пройденных рёбер — длина пути в этих заданиях. Начальную вершину не считают отдельным шагом.

Если запрета нет, путь может проходить по ребру или вершине повторно. Каждый проход добавляет один к длине. Когда условие требует путь без повторений вершин или рёбер, отдельно проверь это ограничение. Кратчайший путь имеет наименьшее число рёбер среди всех допустимых путей между нужными вершинами.

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

В ориентированном графе ребро со стрелкой допускает движение только по её направлению. Возможность попасть из одной вершины в другую не гарантирует обратного пути. При перечислении путей записывай всю последовательность, чтобы не потерять вариант и не посчитать один дважды.

Вернуться к тренажёру →

Построй граф и объясни путь

На бумаге покажи связи, перечисли рёбра и обоснуй вывод. Схемы с другим расположением вершин тоже верны, если связи совпадают.

1. Нарисуй граф с вершинами K, L, M, N, P и только рёбрами KL, LM, MK, MN, NP. Найди степени всех вершин, проверь сумму степеней и число рёбер. Выпиши два различных пути из L в P без повторений вершин.

   Разбор и ориентиры для проверки

   Проверяются все пять вершин и ровно пять заданных рёбер, степени, двойной подсчёт и оба пути. Путь должен использовать только существующие рёбра и не повторять вершины. Любое расположение точек допустимо. Между L и M можно пройти прямо или через K; дальше к P ведут MN и NP.

   Проверь: Степени K, L, M, N, P: 2, 2, 3, 2, 1. Сумма степеней 10 = 2 · 5. Пути L–M–N–P и L–K–M–N–P.

2. В парке пять площадок: вход В, пруд П, сцена С, беседка Б, сад Д. Прямые дорожки есть только между В и П, В и С, П и Б, С и Б, Б и Д. По каждой дорожке можно идти в обе стороны. Построй граф, объясни обозначения и найди все кратчайшие пути от входа в сад. Длина пути — число дорожек.

   Разбор и ориентиры для проверки

   Граф должен точно передавать пять перечисленных связей. Для достижения Д нужно пройти через Б; из В в Б прямой дорожки нет, но есть два пути по две дорожки. Поэтому меньше трёх до Д не получится. Проверяются оба пути и довод минимальности, а не только число 3.

   Проверь: Два кратчайших пути: В–П–Б–Д и В–С–Б–Д, по три дорожки.

3. Нарисуй ориентированный граф: стрелки K→L, K→M, L→N, M→N, N→P. Перечисли все пути из K в P по стрелкам и объясни, почему обратный путь из P в K невозможен. Добавь одну стрелку так, чтобы обратный путь появился.

   Разбор и ориентиры для проверки

   Принимаются точный исходный рисунок, два пути без пропусков и объяснение невозможности выйти из P. Для одного добавленного ребра обратного пути нужно попасть из P в K; стрелка P→K подходит. Стрелки P→N, P→L или P→M не создают пути в K в этой исходной модели.

   Проверь: K–L–N–P и K–M–N–P. Из P нет исходящих стрелок. Например, можно добавить P→K.

4. Придумай два графа с четырьмя вершинами и тремя рёбрами: один связный, другой несвязный. Петли и несколько рёбер между парой вершин не разрешены. Нарисуй оба, перечисли рёбра и объясни связность или её отсутствие.

   Разбор и ориентиры для проверки

   Проверяются четыре вершины и три различных ребра в каждом примере, отсутствие петель и кратных рёбер. В первом между любыми вершинами можно пройти; во втором от D нет пути к остальным. Допустимы другие корректные примеры, например звезда вместо цепочки в первом графе. Изолированную вершину нельзя забывать на рисунке.

   Проверь: Один из вариантов: связный — AB, BC, CD; несвязный — AB, BC, CA и отдельная вершина D.

Задания с ответами и объяснениями

Сначала реши задание самостоятельно, затем открой объяснение.

Вопросы о тренировке