Задачи на таблицы и графы
Во многих заданиях сначала дана таблица связей между объектами, а ответ требуется получить по графу: определить соседей, найти путь, посчитать расстояние или выбрать подходящую последовательность вершин. Главный навык — переводить таблицу в понятную схему и затем систематически проверять все допустимые переходы.
1. Таблица связей и граф
Граф состоит из вершин и рёбер. Вершины обозначают объекты: населённые пункты, станции, компьютеры, помещения или этапы работы. Ребро показывает, что между двумя вершинами существует связь. Если связь направленная, переход разрешён только в указанную сторону; если ненаправленная, по ребру можно двигаться в обоих направлениях.
Вершина — объект графа. Ребро — связь между двумя вершинами. Путь — последовательность вершин, в которой каждая соседняя пара соединена ребром. Длина пути — число рёбер в нём или сумма их весов, если рёбрам приписаны расстояния, время или стоимость.
В таблице связей строки и столбцы соответствуют одним и тем же вершинам. Запись в клетке означает наличие или отсутствие перехода. В матрице смежности обычно используют 1 для существующего ребра и 0 для отсутствующего. Взвешенная таблица может содержать длину, время или стоимость ребра; пустая клетка означает, что прямой связи нет.
Перед решением уточните направление. В ориентированной таблице запись в строке \(A\) и столбце \(B\) означает дугу \(A\to B\). Обратная запись в строке \(B\) и столбце \(A\) может быть равна нулю. В неориентированном графе таблица симметрична относительно главной диагонали.
2. Как перейти от таблицы к графу
Удобно действовать по одному алгоритму. Сначала выпишите все названия вершин. Затем для каждой строки таблицы просмотрите клетки, где указана связь. Для каждой такой клетки проведите ребро. Если граф неориентированный, не рисуйте одно и то же ребро дважды: записи \(A\text{--}B\) и \(B\text{--}A\) описывают одну связь.
- Определите, являются ли связи направленными.
- Проверьте, что строки и столбцы имеют одинаковый порядок вершин.
- Найдите ненулевые или непустые клетки.
- Перенесите каждую связь на схему, сохраняя направление и вес.
- После построения графа ещё раз сравните каждую строку с рисунком.
В неориентированном графе степень вершины равна числу рёбер, выходящих из неё. В ориентированном графе отдельно считают полустепень исхода и полустепень захода: число дуг, выходящих из вершины и входящих в неё.
Степень помогает быстро проверять рисунок. Например, если в строке таблицы у вершины указаны связи с тремя объектами, на схеме у неё должно быть три исходящих ребра для ориентированного графа или три соседних вершины для неориентированного.
3. Поиск пути и расстояния
В простых заданиях нужно проверить существование пути между двумя вершинами. Начинайте с начальной вершины и выписывайте только разрешённые переходы. Не следует переходить по строке в обратную сторону, если граф ориентированный. Уже посещённые вершины отмечайте, чтобы не зациклиться.
Маршрут может проходить через вершину или ребро несколько раз. Простой путь не повторяет вершины. В заданиях на кратчайший путь обычно достаточно рассматривать простые пути: повторение цикла не уменьшает длину при неотрицательных весах.
Если все рёбра имеют одинаковую длину, длина пути — количество рёбер. Если в таблице указаны веса, складывайте значения рёбер, а не количество переходов.
Для двух-трёх возможных ветвей выпишите пути полностью и посчитайте их длины. Если вариантов много, распространяйте от начальной вершины уже известные минимальные расстояния к соседям; такой подход лежит в основе алгоритмов поиска кратчайшего пути.
В ориентированном графе есть дуга \(A\to B\), но нет дуги \(B\to A\). Можно ли сразу перейти из B в A?
4. Разобранный пример
Дана таблица для ориентированного взвешенного графа. Ненулевые значения означают время перехода в минутах: \(A\to B=4\), \(A\to C=2\), \(B\to D=3\), \(C\to B=1\), \(C\to D=7\). Требуется найти кратчайший путь из A в D.
| Из \ В | A | B | C | D |
|---|---|---|---|---|
| A | — | 4 | 2 | — |
| B | — | — | — | 3 |
| C | — | 1 | — | 7 |
| D | — | — | — | — |
Кратчайший путь: \(A\to C\to B\to D\). Его длина равна \(6\) минут. Важно не остановиться на первом найденном пути A\to B\to D длиной \(4+3=7\): нужно сравнить все разумные варианты.
5. Типовые задания и ошибки
По таблицам и графам часто спрашивают: сколько у вершины соседей; существует ли путь; сколько рёбер в пути; какова длина кратчайшего пути; какая последовательность объектов допустима; какая таблица соответствует рисунку. В последнем случае сравнивайте не общий вид, а каждую связь: наличие ребра, его направление и вес.
1. Считать клетку на главной диагонали ребром: обычно она обозначает связь вершины с самой собой и не используется. 2. Забывать направление дуги. 3. Считать вершины вместо рёбер при поиске длины невзвешенного пути: путь из четырёх вершин содержит три перехода. 4. Складывать номера вершин вместо весов рёбер. 5. Дважды учитывать ребро в неориентированном графе. 6. Делать вывод о кратчайшем пути по числу рёбер, когда рёбра имеют разные веса.
Если связи описывают последовательность выполнения работ, граф может быть ориентированным ацикличным. Тогда полезно вспомнить топологическую сортировку: она упорядочивает вершины так, чтобы каждая работа шла после необходимых предшественников. Для задач с числом маршрутов применяются отдельные правила из страницы задачи на количество путей.
Понятия расстояния и кратчайшего пути подробнее связаны со страницей расстояние между вершинами. Если ребро обозначает длительность работы, задача может перейти к теме критический путь или сетевой граф. После этого конспекта полезно решить практикум по графам и путям.
Быстрая проверка
Проверьте себя
Главное
- Таблица связей задаёт рёбра графа; строка обычно обозначает начало, столбец — конец направленной связи.
- Сначала определяйте направление, затем переносите ненулевые клетки на схему и проверяйте степени вершин.
- Длина невзвешенного пути — число рёбер, а длина взвешенного пути — сумма их весов.
- Для кратчайшего пути сравнивайте допустимые маршруты и не забывайте о направлении дуг.
- Главные ошибки: обратный переход по ориентированному ребру, двойной учёт связи и смешение числа вершин с числом рёбер.