Лабораторная работа № 21 (к § 52) Способы представления графов

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

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

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

Ребро — связь между двумя вершинами. В неориентированном графе ребро не имеет направления, поэтому связь A—B означает соединение в обе стороны. В ориентированном графе используют дуги: запись A→B означает движение только из A в B.

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

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

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

В матрице смежности заранее задают порядок вершин, например A, B, C, D. Если между двумя вершинами есть ребро, в соответствующую ячейку ставят 1, а если нет — 0, если именно так договорились в условии. Для неориентированного графа запись дублируется по другую сторону главной диагонали, поэтому матрица получается симметричной.

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

Список рёбер состоит из отдельных записей, каждая из которых содержит пару вершин, например (A, B). Для ориентированного графа порядок пары важен, а для неориентированного он не меняет смысл связи. Если граф взвешенный, к паре добавляют вес: (A, B, 7), где 7 может обозначать расстояние, стоимость или время.

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

Сравнение способов представления графа

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

Разбор задач

Задача 1. Матрица неориентированного графа

Даны вершины A, B, C, D и рёбра A—B, A—D, C—D. Требуется построить матрицу смежности. Считаем, что 1 означает наличие ребра, а 0 — его отсутствие.

1. Фиксируем одинаковый порядок строк и столбцов: A, B, C, D.
2. Для ребра A—B ставим единицы в ячейки A,B и B,A.
3. Для рёбер A—D и C—D аналогично заполняем пары D,A и D,C.
4. На диагонали и в остальных незаполненных ячейках ставим нули.

Ответ: матрица имеет строки 0 1 0 1; 1 0 0 0; 0 0 0 1; 1 0 1 0. Она симметрична относительно главной диагонали, поэтому результат согласуется с неориентированным графом.

Задача 2. Список для ориентированного графа

Пусть дуги ориентированного графа таковы: A→B, A→C, C→B и B→D. Нужно составить список смежности и список дуг. Направление нельзя заменять двусторонней связью.

1. Для A записываем B и C, потому что из A выходят две дуги.
2. Для B записываем D, а для C — B.
3. Для D оставляем пустой список, так как из неё дуг не выходит.
4. В список дуг переносим исходные упорядоченные пары: (A,B), (A,C), (C,B), (B,D).

Ответ: список смежности: A: B, C; B: D; C: B; D: нет. Список дуг содержит четыре указанные пары, причём (A,B) и (B,A) были бы разными дугами.

Задача 3. Веса в матрице

В строке вершины A матрицы взвешенного графа стоят значения 0, 5, 0, 12, а в условии ноль означает отсутствие ребра. Нужно определить соседей A и их веса. Сначала проверяем правило кодирования, потому что в другой задаче нулевой вес мог бы быть допустимым.

1. Просматриваем строку A, сопоставляя позиции с вершинами в зафиксированном порядке A, B, C, D.
2. Значение 5 в столбце B означает ребро A—B веса 5.
3. Значение 0 в столбце C не учитываем как связь, поскольку условие трактует его как отсутствие ребра.
4. Значение 12 в столбце D даёт ребро A—D веса 12.

Ответ: соседи вершины A — B и D. Их веса соответственно равны 5 и 12, а с вершиной C связи нет.

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

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

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

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

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

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

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

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

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

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