§ 11. Моделирование на графах

Определения и обозначения

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

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

Ребро графа — связь между двумя вершинами. Если связь действует в обоих направлениях, её изображают неориентированным ребром; если переход возможен только в заданную сторону, используют направленную дугу со стрелкой. Такое различие необходимо, чтобы модель не разрешала недопустимые переходы.

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

Как это устроено

Построение графовой модели начинается с выбора объектов и связей между ними. Сначала нужно понять, на какой вопрос предстоит ответить: от этого зависит, какие детали реальной ситуации важны. Если требуется найти путь между городами, здания, не участвующие в маршруте, можно не включать. Чем точнее отобраны вершины и рёбра, тем меньше лишних данных мешает анализу.

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

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

Матрица смежности переводит граф в табличную форму: каждой вершине соответствует строка и столбец. На пересечении строки и столбца записывают условный признак связи или её вес. Таблица удобна, когда нужно быстро выяснить, есть ли ребро между двумя вершинами, либо передать граф программе. Для неориентированного графа связь между вершинами A и B отражают и в ячейке A–B, и в ячейке B–A.

Путь в графе — последовательность вершин, в которой каждая соседняя пара соединена ребром или дугой в нужном направлении. Один путь можно сравнить с другим по числу рёбер, а во взвешенном графе — по сумме их весов. Так выбирают маршрут, отвечающий условию задачи: например, с наименьшим расстоянием или временем. Критерий сравнения следует определить заранее, иначе можно выбрать не тот маршрут.

Основные свойства графовой модели и способы её представления

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

Разбор задач

Четыре населённых пункта и дороги

Условие: есть четыре населённых пункта, а дороги проходят между некоторыми парами. Нужно построить графическую модель и назвать соединённые вершины. Обозначим пункты A, B, C и D, а сведения о дорогах возьмём из условия. Если дороги двусторонние, граф будет неориентированным.

1. Каждый населённый пункт представим вершиной A, B, C или D, потому что именно пункты являются объектами модели.
2. Для каждой указанной дороги проведём ребро между соответствующими вершинами; например, дорога между A и C означает ребро A–C.
3. Не будем соединять пары, между которыми дороги нет: иначе модель разрешит несуществующий переход.
4. Если дорога односторонняя, вместо обычного ребра нарисуем дугу со стрелкой в разрешённом направлении.

Ответ: вершинами служат A, B, C и D, а соединёнными являются только пары пунктов, для которых в условии указаны дороги. Конкретный перечень пар зависит от предоставленных данных. Направление учитывается отдельно, если движение по дороге несимметрично.

Матрица смежности для пяти вершин

Условие: дан граф из пяти вершин, нужно заполнить матрицу смежности и перечислить соседей указанной вершины. Соседями считаются вершины, непосредственно соединённые с выбранной вершиной ребром. Для примера обозначим вершины A, B, C, D и E, а связи перенесём из заданного графа.

1. Запишем A, B, C, D и E как заголовки строк и столбцов, чтобы каждой паре вершин соответствовала ячейка.
2. Для каждой пары проверим граф: если между вершинами есть ребро, внесём в ячейку 1, а если нет — 0.
3. В неориентированном графе заполним обе ячейки пары одинаково, например A–C и C–A, поэтому матрица должна быть симметричной.
4. Чтобы найти соседей выбранной вершины, например C, прочитаем её строку и выпишем вершины, которым соответствуют единицы.

Ответ: матрица содержит по одной строке и столбцу на каждую из пяти вершин. Соседи C — вершины, стоящие в столбцах с единицей в строке C; их точный список определяется заданными рёбрами. Если в условии принята другая кодировка, нужно использовать её последовательно.

Маршрут с наименьшим расстоянием

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

1. Выделим на схеме все пути, которые соединяют начальный пункт с конечным и не нарушают направление дорог, если оно задано.
2. Для каждого пути запишем веса входящих в него рёбер, чтобы не потерять отдельные участки.
3. Сложим веса каждого пути; например, для пути через рёбра длиной 4, 7 и 2 сумма равна 13.
4. Сравним полученные суммы и выберем путь с наименьшим значением, проверив, что ни один допустимый вариант не пропущен.

Ответ: кратчайшим по расстоянию будет маршрут с минимальной суммой весов его рёбер. Чтобы обосновать выбор, указывают сам путь и его общую длину, а также сравнивают её с длинами рассмотренных альтернатив. Без конкретных значений расстояний назвать пункты маршрута невозможно.

Типичные ошибки

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

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

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

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

Связь с другими темами

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

Что запомнить

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