10. Строим графы

Определения и обозначения

Граф — модель, состоящая из вершин и соединяющих их рёбер. Он помогает представить не только отдельные объекты, но и отношения между ними: дороги между городами, связи компьютеров или знакомства людей. Такая модель нужна, чтобы увидеть структуру ситуации и анализировать возможные связи.

Вершина графа — точка, обозначающая объект или состояние. В учебных задачах вершиной может быть населённый пункт, участник общения, компьютер, станция или положение некоторой системы. Выбор вершин помогает отделить сами объекты от связей между ними.

Ребро графа — линия, соединяющая две вершины и обозначающая связь между ними. Одно и то же ребро может изображать дорогу, знакомство, кабельную связь или другой тип отношения, если это указано в условии. По рёбрам можно понять, какие объекты непосредственно связаны.

Смежные вершины — вершины, соединённые одним ребром. Чтобы определить смежность, достаточно выбрать вершину и посмотреть, какие линии подходят к ней и ведут к другим вершинам. Эти соседние вершины показывают непосредственные связи выбранного объекта.

Как это устроено

Чтобы перейти от описания ситуации к графу, сначала выделяют объекты, а затем связи между ними. Объекты становятся вершинами, потому что их нужно различать, а связи — рёбрами, потому что именно они показывают отношения. После построения стоит проверить, сохранилась ли вся нужная информация: каждый существенный объект и каждая указанная связь должны быть представлены.

При построении по перечню связей удобно двигаться в два этапа. Сначала изображают все вершины, чтобы не забыть объект, который пока ни с кем не соединён, а затем проводят ребро для каждой указанной пары. Такой порядок уменьшает риск принять подпись или точку за уже готовую связь.

Расположение вершин на листе и форма рёбер обычно не меняют граф, потому что смысл задаётся не расстояниями, а соединениями. Вершины можно поставить ближе или дальше, а прямую линию заменить ломаной, если не появились новые пересечения-связи. Поэтому два рисунка могут выглядеть по-разному, но описывать одну и ту же сеть.

Готовый граф читают, сначала находя нужные вершины, а затем рассматривая рёбра, которые к ним подходят. По такому рисунку можно восстановить список объектов, список связей и соседей выбранной вершины. Например, все вершины, соединённые с пунктом А, являются населёнными пунктами, до которых из А есть непосредственная дорога.

Проверка графа должна идти в обоих направлениях. Сначала для каждой записи условия находят соответствующее ребро, чтобы обнаружить пропуски, а затем для каждого ребра ищут подтверждение в условии, чтобы убрать лишние связи. Если обе проверки пройдены, граф передаёт исходную ситуацию без искажений.

Как описать граф

Выбирайте способ записи по задаче. Рисунок удобен для зрительного анализа, список — для построения по перечню, а матрица — для полного перебора пар. При любом способе содержание должно быть одинаковым: одна и та же пара объектов либо связана, либо нет.

Разбор задач

Дороги между населёнными пунктами

Условие. На схеме указаны четыре населённых пункта и дороги между некоторыми парами. Нужно построить граф дорожной сети.

1. Обозначьте четыре населённых пункта четырьмя вершинами и подпишите их, например А, Б, В и Г.
2. Просмотрите перечень дорог и для каждой указанной пары проведите одно ребро.
3. Ещё раз сравните рисунок со схемой, не добавляя линию только потому, что две вершины расположены рядом.

Ответ. Получится граф с четырьмя вершинами, где ребро есть ровно между теми парами населённых пунктов, которые соединены дорогами.

Граф знакомств

Условие. Даны пять участников и список пар, знакомых друг с другом. Нужно нарисовать граф знакомств и перечислить смежные с участником А вершины.

1. Создайте пять вершин и подпишите их именами участников.
2. Перенесите в рисунок каждую пару из списка знакомых, проводя между ними ребро.
3. Найдите вершину А и выпишите все вершины, к которым от неё идут рёбра.

Ответ. Граф содержит пять вершин и рёбра по списку знакомств, а смежными с А являются только участники, соединённые с А непосредственно.

Проверка по таблице

Условие. По таблице связей между шестью объектами нужно построить граф, а затем проверить, что в рисунке нет пропущенных и лишних рёбер.

1. Изобразите шесть вершин с теми же обозначениями, что и в таблице.
2. Для каждой записи о связи соедините соответствующую пару вершин.
3. Проверьте таблицу по рисунку, а затем рисунок по таблице: каждое ребро должно иметь запись, и каждая запись — своё ребро.

Ответ. Правильным будет граф, полностью совпадающий с таблицей связей и не содержащий дополнительных соединений.

Типичные ошибки

Ошибка: считать, что положение вершины или длина ребра несут смысл. Так происходит, когда ученик воспринимает рисунок как карту, хотя в обычном графе важны только пары соединённых вершин. Проверьте себя: после перестановки точек набор связей должен остаться прежним.

Ошибка: провести ребро между близкими на рисунке объектами. Близость часто принимают за связь, потому что на схеме точки кажутся соседними. Сверяйте каждую линию с условием: если там нет такой пары, ребро не нужно.

Ошибка: пропустить связь из списка. Это случается, когда пары переносят в граф без последовательной проверки. Отметьте каждую запись после нанесения ребра и убедитесь, что ни одна не осталась без отметки.

Ошибка: считать одну пару разными связями из-за другого изгиба или положения линии. Форма ребра может отличаться, но она не создаёт новую связь. Сравнивайте не вид линии, а две вершины, которые она соединяет.

Связь с другими темами

До изучения графов нужно уметь выделять объекты и связи в тексте задачи, а также читать простые схемы и таблицы. Эти навыки помогают правильно выбрать вершины и не перепутать условие с внешним видом рисунка.

Графы применяют для описания дорог, компьютерных сетей, знакомств и маршрутов. Позже такая модель становится основой для изучения поиска пути и алгоритмов на графах.

Что запомнить

• Граф состоит из вершин и рёбер.
• Вершина обозначает объект, ребро — связь между объектами.
• Ребро соединяет две вершины.
• Смежными называют вершины, соединённые ребром.
• Граф должен отражать связи из условия, а не внешнее сходство объектов.
• Для проверки постройки сравнивают каждую связь условия с ребром графа.