Графы: матрица смежности и таблица связей
💻 Информатика · 9 класс
Что такое матрица смежности
Граф — это математическая модель, состоящая из набора вершин и соединяющих их рёбер. Графами описывают карты дорог, схемы метро, связи между людьми и многое другое. Чтобы хранить граф в памяти компьютера или удобно работать с ним на бумаге, его записывают в виде таблицы. Матрица смежности — это квадратная таблица, в которой строки и столбцы соответствуют вершинам, а на пересечении строки и столбца стоит признак наличия ребра между соответствующими вершинами.
Для невзвешенного графа на пересечении пишут 1, если вершины соединены ребром, и 0, если ребра нет. Для взвешенного графа вместо единицы записывают вес ребра — расстояние, стоимость проезда или время в пути.
Свойства матрицы смежности
- Размер матрицы —
N × N, гдеN— число вершин графа. - Для неориентированного графа матрица симметрична относительно главной диагонали: значение в клетке «строка А, столбец Б» совпадает со значением в клетке «строка Б, столбец А».
- На главной диагонали обычно стоят нули или прочерки: считается, что вершина не соединена сама с собой.
Разбор примера
Пусть есть четыре города и дороги между ними. Запишем таблицу: на пересечении указано расстояние в километрах, а прочерк означает, что прямой дороги между городами нет.
| А | Б | В | Г | |
|---|---|---|---|---|
| А | — | 5 | — | 3 |
| Б | 5 | — | 2 | — |
| В | — | 2 | — | 4 |
| Г | 3 | — | 4 | — |
По этой таблице сразу видно, какие города соединены напрямую. Например, между А и Б есть дорога длиной 5 километров, а между А и В прямой дороги нет — стоит прочерк. Чтобы узнать длину пути А → Г → В, складываем числа из таблицы:
Длина пути А-Г-В:
А-Г = 3 км
Г-В = 4 км
Итого: 3 + 4 = 7 км
Сравним с путём А-Б-В:
5 + 2 = 7 км — столько же
Такие таблицы постоянно встречаются в заданиях ОГЭ, где по матрице нужно найти кратчайший маршрут или подсчитать число дорог. Чтобы найти все дороги, выходящие из города, достаточно прочитать одну строку таблицы, а чтобы узнать общее число дорог в графе, считают все ненулевые клетки и делят их количество на два (ведь каждая дорога записана в таблице дважды — в симметричных клетках).
Помимо матрицы смежности, граф можно задать списком рёбер, где просто перечислены пары соединённых вершин и веса дорог между ними. Список рёбер экономнее для разреженных графов, где дорог мало, а матрица удобнее, когда нужно быстро проверить наличие связи между двумя конкретными вершинами — достаточно заглянуть в одну клетку таблицы.
Частая ошибка. Брать только прямое ребро между нужными городами, забыв проверить обходные пути через другие вершины. Иногда обходной путь короче прямой дороги, а иногда прямой дороги вовсе нет, и добраться можно лишь в обход.
Кратко о главном
- Матрица смежности — таблица
N × N, описывающая связи вершин графа. - Число или единица на пересечении означает ребро, прочерк или ноль — его отсутствие.
- У неориентированного графа таблица симметрична относительно диагонали.
- По таблице удобно искать дороги, считать пути и сравнивать их длины.