"Информатика", Горячев А.В., Суворова Н.И.
Граф — это модель, которая помогает показать объекты и связи между ними. Объекты изображают вершинами, а связи — рёбрами, соединяющими вершины. Например, так можно представить знакомства учеников или дороги между пунктами. При чтении графа важно смотреть, какие вершины соединены, а не где они расположены на листе. Поэтому один и тот же граф можно нарисовать разными способами, если набор вершин и связей остаётся прежним.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Граф — модель, состоящая из вершин и соединяющих их рёбер. Его используют, когда нужно показать не только отдельные объекты, но и отношения между ними. Например, граф может описывать города и дороги или людей и знакомства. Такая модель помогает наглядно увидеть, как устроены связи.
Вершина графа изображает отдельный объект или элемент модели. Вершинами могут быть пункты на карте, люди в группе или компьютеры в сети. Обычно их обозначают точками, кружками или фигурами и подписывают буквами либо названиями. Благодаря вершинам понятно, о каких объектах идёт речь.
Ребро графа — связь между двумя вершинами. На рисунке его обычно показывают линией, которая соединяет эти вершины. Например, ребро может означать дорогу между пунктами или знакомство двух людей. Рёбра позволяют увидеть, какие именно объекты связаны между собой.
Смежные вершины — вершины, соединённые одним ребром. Чтобы определить такую пару, нужно найти ребро и посмотреть на его концы. Это понятие помогает быстро перечислить связи в графе. Если две вершины просто стоят рядом, но ребро их не соединяет, смежными они не являются.
Представим ситуацию, где важны отношения между объектами, например дороги между населёнными пунктами. Сначала выделяют сами объекты: каждому пункту сопоставляют вершину. Затем находят связи, которые нужно отразить: каждой дороге сопоставляют ребро между вершинами её начала и конца. Такой перевод удобен, потому что вместо длинного описания получается схема, по которой легко увидеть соседние пункты.
В графе важны объекты и связи, а не то, где именно они нарисованы. Если переместить вершину в другое место, но оставить все её рёбра, описание отношений не изменится. Расстояние между точками на листе может быть выбрано только для удобства чтения. Поэтому нельзя считать, что близкие вершины связаны, если между ними нет ребра.
Чтобы прочитать граф, сначала найдите вершину, которая вас интересует, а затем проверьте, какие линии-рёбра к ней подходят. Концы каждого такого ребра и образуют пару смежных вершин. Например, если ребро соединяет A и B, вершины A и B смежны. Если линия проходит рядом с вершиной, но не соединяется с ней, связи между ними нет.
Один и тот же граф можно нарисовать несколькими способами: расположить вершины кругом, цепочкой или в произвольных местах. Рисунки будут изображать один граф, если в них сохранены одинаковые объекты и пары соединённых вершин. Это возможно потому, что расположение на бумаге не входит в описание связей. При сравнении схем смотрите на состав вершин и рёбер, а не на сходство их формы.
Проверяя, соответствует ли граф описанной ситуации, по очереди сверьте его элементы с условием. Каждой вершине должен соответствовать объект, а каждому ребру — указанная в ситуации связь. Затем убедитесь, что все нужные связи нанесены и что лишних рёбер нет. Такая проверка помогает заметить как пропуски, так и неверно добавленные соединения.
| Элемент или понятие | Что обозначает | Как распознать на рисунке |
|---|---|---|
| Вершина | Отдельный объект или элемент модели | Точка, кружок или другая фигура, часто с подписью |
| Ребро | Связь между двумя вершинами | Линия, соединяющая две вершины |
| Смежные вершины | Пара вершин, соединённых одним ребром | Две вершины, к которым подходят концы одного ребра |
Пользуйтесь таблицей, чтобы различать объект, связь и пару связанных объектов. При чтении схемы сначала найдите вершины, затем проверьте линии между ними. Если нужно назвать смежные вершины, записывайте концы каждого ребра как пару.
На рисунке четыре вершины A, B, C, D и рёбра AB и CD. Перечислите пары смежных вершин. Здесь не требуется сравнивать расстояния между вершинами или искать дополнительные связи. Достаточно установить, какие вершины соединяет каждое указанное ребро.
Ответ: A и B; C и D. Вершины из разных пар не соединены заданными рёбрами, даже если на рисунке они расположены близко.
В кружке есть пять учеников. Аня знакома с Борисом и Викой, Борис — с Димой, Вика — с Димой и Галей. Постройте граф знакомств и назовите вершины, смежные с Димой. Знакомство в этой модели записывается одним ребром между двумя учениками. Нужно перенести все перечисленные связи, не придумывая новых.
Ответ: граф содержит пять вершин и пять перечисленных рёбер; с Димой смежны Борис и Вика.
Между четырьмя пунктами A, B, C, D проложены дороги AB, AC, BC и CD. Изобразите граф дорог и определите, можно ли проехать из A в D, не проходя через C. Сначала нужно точно перенести дороги, а уже затем проследить возможный маршрут. Важно отличать наличие пути от того, как вершины расположены на листе.
Ответ: проехать из A в D, не проходя через C, нельзя. Перестановка вершин на рисунке этого вывода не изменит, поскольку набор дорог останется прежним.
Ошибка — считать, что близко нарисованные вершины обязательно соединены. Так кажется, потому что на обычной схеме соседство на листе часто используют для удобства, но в графе связь показывает ребро. Проверьте, есть ли между вершинами линия, которая действительно соединяется с обеими. Если её нет, близкое расположение ничего не означает.
Ошибка — принимать пересечение линий за новую вершину. Линии могут пересекаться просто из-за выбранного способа рисунка, поэтому точка пересечения не обязательно соответствует объекту. Проверьте, обозначена ли она как отдельная вершина и предполагает ли её описание ситуации. Если нет, не добавляйте её в граф.
Ошибка — пропустить ребро или добавить лишнее при переносе описания в граф. Это случается, когда связи наносят по памяти, не сверяясь с условием. Перечитайте каждое предложение и отметьте, какой паре объектов оно соответствует. После построения проверьте, что каждое ребро подтверждается условием, а каждая названная связь отражена.
Ошибка — считать, что граф изменился, когда вершины переставили на рисунке. Мы часто воспринимаем схему как картинку, но для графа важны не форма и расположение, а связи. Сравните два рисунка по вершинам и парам, соединённым рёбрами. Если эти данные совпадают, граф тот же, даже если рисунки выглядят по-разному.
Перед изучением графов полезно уметь читать схемы и условные обозначения. Ещё важно различать сами объекты и связи между ними: например, не путать город с дорогой между городами. Это умение помогает правильно определить, что станет вершиной, а что — ребром. Тогда описание ситуации можно без потери смысла перенести в модель.
Графы пригодятся при изучении алгоритмов поиска пути, сетей и способов представления данных. В сети вершины могут обозначать устройства, а рёбра — соединения между ними. При поиске пути рассматривают последовательность рёбер, ведущую от одной вершины к другой. Так граф становится основой для решения практических задач о перемещении и связях.
Чем вершина графа отличается от ребра?
Вершина обозначает отдельный объект или элемент модели, например ученика или город. Ребро показывает связь между двумя вершинами, например знакомство или дорогу.
Как понять, какие вершины являются смежными?
Найдите ребро и посмотрите, какие две вершины являются его концами. Именно эта пара вершин называется смежной.
Обязательно ли рисовать граф так же, как он изображён в учебнике?
Нет, граф можно расположить на листе по-разному. Главное, чтобы остались те же вершины и те же связи между ними.
Считается ли пересечение двух рёбер вершиной?
Само по себе пересечение линий вершиной не считается. Оно становится вершиной только тогда, когда в модели явно обозначено как отдельный элемент.
Как перевести описание связей между объектами в граф?
Сопоставьте каждому объекту вершину, а каждой указанной связи — ребро между соответствующими вершинами. Затем сверьте получившийся граф с условием, чтобы не пропустить связь и не добавить лишнюю.
§ 14. Граф. Вершины и рёбра
