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