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