Что такое граф в информатике
Граф состоит из вершин и рёбер. Вершины — это точки (города, станции, люди), рёбра — линии, которые их соединяют (дороги, рельсы, знакомства). Рисунок можно нарисовать как угодно, важно только, какие вершины соединены.
В заданиях встречаются несколько видов графов:
- неориентированный граф: по ребру можно ехать в обе стороны;
- ориентированный граф: у ребра есть стрелка, и ехать можно только по ней;
- взвешенный граф: у каждого ребра есть число (длина дороги, время в минутах, стоимость);
- связный граф: от любой вершины можно дойти до любой другой.
Путь — это последовательность вершин, где каждая следующая соединена с предыдущей. Длина пути во взвешенном графе равна сумме весов рёбер, а в обычном — числу рёбер. Цикл — путь, который заканчивается в той же вершине, где начался.
Когда граф задан таблицей, на пересечении строки и столбца стоит вес ребра между этими вершинами. Пустая клетка значит, что прямой дороги нет. Для неориентированного графа такая таблица симметрична: число на пересечении A и B равно числу на пересечении B и A. Это помогает заполнять пропуски и проверять себя. Сами графы часто служат информационной моделью реальной ситуации, например карты дорог.
Как найти кратчайший путь в графе по таблице
Возьмём пять пунктов и таблицу дорог. Нужно найти длину кратчайшего пути из A в E.
| A | B | C | D | E | |
|---|---|---|---|---|---|
| A | 4 | 2 | |||
| B | 4 | 1 | 5 | ||
| C | 2 | 1 | 8 | 10 | |
| D | 5 | 8 | 3 | ||
| E | 10 | 3 |
Шаг 1. Выпиши дороги из таблицы: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 3. Каждую дорогу берём один раз, потому что таблица симметрична.
Шаг 2. Посмотри, как можно попасть в конечный пункт E. В него ведут только две дороги: из C (10) и из D (3).
Шаг 3. Переберай маршруты и считай суммы:
- A–C–E: 2 + 10 = 12;
- A–B–D–E: 4 + 5 + 3 = 12;
- A–C–D–E: 2 + 8 + 3 = 13;
- A–C–B–D–E: 2 + 1 + 5 + 3 = 11.
Шаг 4. Выбери наименьшее значение. Ответ: 11.
Обрати внимание на последний маршрут. Он длиннее по числу дорог, но короче по километрам, потому что включает короткие участки 2, 1 и 3. Прямой путь не обязательно самый быстрый.
Как посчитать количество путей в ориентированном графе
В таких заданиях дан рисунок со стрелками, а нужно найти, сколько разных маршрутов ведёт из одной вершины в другую. Перебирать маршруты глазами долго и легко пропустить один. Надёжнее считать по вершинам.
Правило: число путей в вершину равно сумме чисел путей во все вершины, из которых в неё идут стрелки. Для начальной вершины ставим 1.
Пример. Стрелки: A→B, A→C, B→C, B→D, C→D, C→E, D→E. Сколько путей из A в E?
- A: 1;
- B: в неё идёт только стрелка из A, поэтому 1;
- C: стрелки из A и B, 1 + 1 = 2;
- D: стрелки из B и C, 1 + 2 = 3;
- E: стрелки из C и D, 2 + 3 = 5.
Ответ: 5 путей. Вершины считай по порядку, начиная от начальной, так чтобы значения предшественников уже были известны.
Если в условии есть «проходит через Ж», посчитай путей от начала до Ж и от Ж до конца, потом перемножь числа. Если есть «не проходит через В», вычеркни вершину В вместе с её стрелками и считай заново. Сама идея опирается на комбинаторику: пути перемножаются, когда выбор делается по шагам, и складываются, когда есть несколько вариантов.
Где ошибаются чаще всего
Путают направление стрелок. В ориентированном графе нельзя ехать против стрелки, даже если так короче. Перед подсчётом пометь для каждой вершины, откуда в неё приходят стрелки.
Берут кратчайший по числу рёбер вместо кратчайшего по весу. Во взвешенном графе сравнивай суммы чисел, а не количество дорог.
Принимают за цикл любую последовательность вершин. Например, в графе со стрелками A→Б, A→В, В→Г, Г→А, Г→Б цикл только АВГА: каждая стрелка на месте, и путь возвращается в А. В варианте АБГА нет стрелки Б→Г, а ВГАБ заканчивается в Б, а не в В.
Теряют дороги из таблицы. Если задание даёт рисунок и таблицу, а номера пунктов в таблице не совпадают с буквами на схеме, сопоставляй их по числу дорог у пункта. Пункт с одной дорогой или с самым большим числом дорог проще найти и на рисунке, и в таблице. Остальные определяются по весам рёбер.
Ошибаются при подсчёте вершин и рёбер. Считай каждое ребро один раз. Для проверки сумма степеней вершин (числа рёбер у каждой) должна быть вдвое больше числа рёбер.
Какие задания по графам присылают ученики
Чаще всего ученики 9 класса присылают поиск кратчайшего пути по таблице дорог, подсчёт путей в ориентированном графе и задания, где схему нужно сопоставить с таблицей. Реже попадаются вершины и рёбра, циклы, заполнение симметричной таблицы и построение связного графа с заданным циклом.
Найди в списке выше задание, похожее на твоё, и посмотри ход решения: он показывает, в каком порядке считать. Если такого нет, сфотографируй своё задание и отправь на сайт, чтобы получить решение с пошаговым объяснением. Подготовиться к таким задачам помогут также темы алгоритмы и исполнители и логика.