Практикум по графам и путям
В задачах на графы важно не начинать с перебора вариантов, а сначала определить, что именно задано: маршрут, таблица смежности, граф переходов, длины рёбер или условие о цикле. Этот практикум объединяет основные приёмы для заданий ege-1, ege-8, ege-13, ege-27, oge-4 и oge-9.
1. Как читать граф и условие
Граф состоит из вершин и рёбер. Вершины обозначают объекты, а рёбра — связи между ними. Если направление движения важно, ребро является ориентированным: из вершины \(A\) можно перейти в \(B\), но не обязательно обратно. Если направления нет, связь считается двусторонней. Граф может быть задан рисунком, списком рёбер или таблицей смежности.
Степень вершины — число рёбер, выходящих из вершины в неориентированном графе. Путь — последовательность вершин, в которой соседние вершины соединены рёбрами. Длина пути — число рёбер, если все переходы равноправны, или сумма весов рёбер, если указаны расстояния или стоимости. Цикл — замкнутый путь, начинающийся и заканчивающийся в одной вершине.
В маршрутах обычно нужно учитывать порядок посещения. Если сказано «можно проехать из \(A\) в \(B\)», это не всегда означает возможность вернуться. В таблице смежности строки и столбцы имеют фиксированный порядок: значение 1 или положительный вес на пересечении строки \(A\) и столбца \(B\) означает переход \(A\to B\).
Сначала выпишите вершины и направления рёбер. Затем выясните, требуется ли один конкретный маршрут, число маршрутов, кратчайшее расстояние, наличие цикла или свойство всех вершин. Не смешивайте число рёбер с суммарным весом пути.
2. Пути, маршруты и количество нұсқа
Если требуется найти число путей между двумя вершинами, удобно составить таблицу переходов или использовать подсчёт путей по графу. Для небольших графов пути перечисляют системно: сначала фиксируют первый переход, затем продолжают каждый вариант и отбрасывают повторения вершин, если это запрещено условием.
В графе переходов вершинами могут быть состояния, а ребро означает разрешённое изменение состояния. Такие задачи связаны с графом переходов. Если этапы независимы, применяют правило произведения: число способов выполнить последовательность этапов равно произведению числа вариантов на каждом этапе. Если варианты объединены по взаимоисключающим случаям, применяют правило суммы.
Для маршрута с промежуточной вершиной \(C\) часто дұрыс: число путей из \(A\) в \(B\) через \(C\) равно произведению числа путей \(A\to C\) и \(C\to B\). Если маршруты проходят через разные взаимоисключающие промежуточные вершины, результаты складывают.
Если все пути в вершину \(X\) приходят из вершин \(A_1,\ldots,A_k\), то число путей до \(X\) равно сумме числа путей до этих предшественников: \(P(X)=P(A_1)+\ldots+P(A_k)\). Начальной вершине присваивают \(P=1\).
Из \(A\) в \(B\) ведут 3 пути, а из \(B\) в \(C\) — 4 пути. Каждый путь \(A\to C\) обязан проходить через \(B\). Сколько таких путей?
3. Расстояния и кратчайшие пути
Если рёбрам приписаны длины, стоимости или времена, длина маршрута равна сумме весов всех его рёбер. Кратчайший путь — путь минимальной длины. В простом графе с одинаковой длиной рёбер достаточно найти путь с наименьшим числом переходов. Для всех пар вершин можно применять алгоритм Флойда: он последовательно проверяет, не станет ли путь короче при добавлении промежуточной вершины.
Здесь \(d_{ij}^{(k)}\) — лучшее известное расстояние из \(i\) в \(j\), если разрешены промежуточные вершины с номерами от 1 до \(k\). Для одной пары вершин в небольшом графе можно просто сравнить несколько допустимых маршрутов. Если веса неотрицательны, полезен также последовательный выбор ближайшей ещё не обработанной вершины.
Эксцентриситет вершины — максимальное расстояние от неё до остальных вершин. Центр графа состоит из вершин с минимальным эксцентриситетом. Диаметр графа — максимальное из кратчайших расстояний между парами вершин.
4. Разобранный пример: кратчайший путь и цикл
Дан ориентированный граф с рёбрами \(A\to B\) длины 4, \(A\to C\) длины 2, \(C\to B\) длины 1, \(B\to D\) длины 3, \(C\to D\) длины 7 и \(D\to A\) длины 5. Требуется найти кратчайший путь из \(A\) в \(D\) и определить, образует ли найденный маршрут цикл.
Кратчайший путь: \(A\to C\to B\to D\), его длина — 6. Этот путь не является циклом, потому что начинается в \(A\), а заканчивается в \(D\). Однако в исходном графе есть цикл \(A\to C\to B\to D\to A\) длины \(6+5=11\).
5. Циклы, мосты и специальные свойства
Чтобы проверить цикл, ищут замкнутую последовательность рёбер без лишних повторов. В ориентированном графе направления всех рёбер должны совпадать с движением по циклу. В задачах о прохождении каждого ребра ровно один раз проверяют условия существования эйлерова пути. Эйлеров путь использует каждое ребро один раз, а эйлеров цикл дополнительно возвращается в начальную вершину.
Если удаление ребра увеличивает число компонент связности графа, это ребро является мостом. Мост не может входить в цикл: если его удалить из цикла, между его концами всё равно останется обход по другой части цикла.
Связный граф имеет эйлеров цикл тогда и только тогда, когда степени всех его вершин чётны. Эйлеров путь без требования вернуться в начало возможен, если нечётных вершин ровно 0 или 2.
1. Считают все проходы, хотя условие запрещает повторять вершины или рёбра. 2. Складывают количества маршрутов вместо умножения на последовательных этапах. 3. При поиске кратчайшего пути выбирают локально самое дешёвое ребро и не сравнивают весь маршрут. 4. Путают цикл с любым маршрутом, имеющим несколько рёбер. 5. Читают неориентированный граф как ориентированный или наоборот. 6. В условии про мост проверяют вершину, а не ребро.
6. Стратегия шешімдер экзаменационной тапсырма
- Перепишите граф в удобный вид: рисунок, список рёбер или таблицу.
- Отметьте направление, вес и ограничения на повторения.
- Выберите метод: перечисление, правило суммы и произведения, динамический подсчёт, поиск кратчайшего пути или проверка степеней.
- Запишите промежуточные значения, чтобы не потерять маршрут и не пересчитать его дважды.
- Проверьте ответ по условию: нужные ли вершины посещены, не нарушен ли порядок, совпадает ли единица измерения.
Перед этим практикумом полезно повторить тапсырма на маршруты, тапсырма на таблицы и графы и тапсырма на количество путей. Свойства смежных вершин удобно проверять через раскраску графа, если условие запрещает соединять вершины бір типа.
Быстрая проверка
Главное
- Граф описывают вершины, рёбра, направления и веса; сначала нужно точно прочитать эти свойства.
- Число нұсқа на последовательных этапах перемножают, а для взаимоисключающих случаев складывают.
- Длину пути находят суммированием весов, кратчайший путь выбирают сравнением допустимых маршрутов или алгоритмом Флойда.
- Цикл замыкается в исходной вершине; мост не кіреді ни в один цикл.
- Для эйлерова цикла в связном неориентированном графе все степени вершин должны быть чётными.