Информатика, 4 классГраф4 минуты чтения
Граф
Нарисуй несколько точек и соедини часть из них линиями. Получится граф. Точки называют вершинами, линии рёбрами.
4классВершины и рёбра
Вершина это место или предмет: город, остановка, человек, компьютер в сети. Ребро это связь между двумя вершинами, и связью может быть что угодно: дорога, авиарейс, дружба, провод.
Больше в графе ничего нет. Из этих двух вещей и строится всё остальное, вплоть до карты всех дорог страны.
Пять посёлков и дороги между ними
Что бывает графом
- Карта дороггорода и дороги
- Схема метростанции и перегоны
- Классученики и кто с кем дружит
- Интернеткомпьютеры и связи между ними
Путь по рёбрам
Двигаться можно только по рёбрам, а перепрыгнуть с вершины на вершину, между которыми связи нет, нельзя. Путь это цепочка рёбер, ведущая от одной вершины к другой.
Путей между двумя вершинами обычно много. Один короче, другой длиннее, третий проходит через полгорода.
Как найти путь на схеме
- 1Отметь начальную вершину
- 2Выпиши всех соседей, куда есть ребро
- 3Двигайся к тому соседу, что ближе к цели
- 4Повторяй, пока не придёшь
- 5Сосчитай рёбра, это длина пути
Кратчайший путь
Обычно ищут самый короткий путь. Так работает навигатор.
Длину меряют числом рёбер или километрами. Иногда минутами: одна дорога длиннее, зато без пробок.
Компьютер перебирает пути быстро. Человеку на схеме метро проще считать пересадки.
Ищем короткую дорогу от дома до парка
Путь: Дом → Школа → Парк
Меньше станций
Меньше пересадок
Едешь дольше в вагоне
Стоишь дольше на переходах
Хорошо с тяжёлой сумкой
Хорошо, когда торопишься
Считаем рёбра
Считаем смены линии
Граф без корня
В дереве всегда есть начало. В графе его может не быть.
Из вершины пути расходятся и снова сходятся. Можно вернуться туда, откуда вышел.
Такой круговой путь называют циклом. В дереве циклов не бывает.
Путь, который вернулся туда, откуда вышел
Путь: А → Б → В → Г → А
Направление имеет значение
Ребро бывает с направлением. Тогда его рисуют стрелкой.
Улица с односторонним движением как раз такая. Туда проехать можно, обратно нет.
В графе дружбы стрелки не нужны: если ты дружишь с Петей, то и Петя с тобой.
Улицы с односторонним движением
Как граф хранят в компьютере
Нарисовать граф красиво нельзя: у компьютера нет бумаги. Поэтому его хранят списком, где для каждой вершины перечислены соседи.
Такой список занимает мало места и читается программой мгновенно. Из него легко узнать, есть ли ребро между двумя вершинами, и куда можно шагнуть дальше.
Ни точек, ни линий внутри машины нет. Есть только имена и связи.
Обход графа
Обойти граф значит побывать в каждой вершине. Делают это двумя способами, и оба придумали давно.
Первый способ уходит вглубь: идёшь вперёд, пока есть дорога, а упёршись, возвращаешься к последней развилке. Второй способ обходит соседей по кругу, слой за слоем, и потому первым находит короткий путь.
Обход не даст заблудиться, если помечать пройденные вершины. Иначе по циклу можно ходить бесконечно.
Задача о мостах
Триста лет назад в городе Кёнигсберге было семь мостов. Жители спорили, можно ли пройти по всем ровно по разу.
Учёный по имени Эйлер доказал, что нельзя. Для этого он и придумал считать линии, сходящиеся в каждой точке.
С этой задачи и началась наука о графах.
Про деревья читай урок «Дерево». Про маршруты исполнителя есть урок «Маршрут исполнителя».
Проверь себя: В графе пять вершин, и каждая соединена с каждой. Сколько всего рёбер?
Десять. Каждая из пяти вершин связана с четырьмя другими, получается двадцать концов, а рёбер вдвое меньше.
Короткие ответы
- Чем граф отличается от дерева?
- В дереве от корня к листу ведёт один путь, а в графе путей бывает много, и они могут возвращаться в начало.
- Зачем графы нужны на самом деле?
- По ним строят маршруты в навигаторе, чинят расписание автобусов и ищут друзей друзей в сети.