Определение
Матрица смежности — это квадратная таблица, которой задают граф: строки и столбцы подписаны одними и теми же вершинами, а клетка на пересечении строки A и столбца B показывает, есть ли ребро между A и B. В простом случае в клетке пишут 1 (ребро есть) или 0 (нет), а в таблице расстояний — длину ребра; пустая клетка там означает, что прямой дороги нет.
Ключевые признаки
- Квадратная форма — сколько вершин, столько строк и столько же столбцов, и вершины в строках и столбцах идут в одном и том же порядке
- Симметрия при двусторонних дорогах — если по дороге можно ехать в обе стороны, в строке A и столбце B стоит то же число, что в строке B и столбце A
- Только прямые дороги — если прямой дороги между A и D нет, клетка A–D пуста, даже когда из A в D можно добраться через другие пункты; длину такого маршрута получают, складывая длины нескольких рёбер
- Пустота вместо нуля — в таблице расстояний пустая клетка значит «дороги нет», а не «расстояние 0 км»; клетки на диагонали (A–A, B–B) там обычно пустые
Пример
Таблица расстояний для пунктов A, B, C, D: в строке A стоят 4 (в столбце B) и 9 (в столбце C), клетка A–D пуста — прямой дороги нет. Есть ещё дороги B–C = 3 и C–D = 2, других нет. Путь A→C→D = 9 + 2 = 11 км, а A→B→C→D = 4 + 3 + 2 = 9 км: он короче, хотя дорог в нём больше.
Тема целиком: Граф — теория, разобранные задания и тренажёр.
Не путай: Матрица смежности и список рёбер
Список рёбер перечисляет только существующие дороги: «A–B 4, A–C 9, B–C 3, C–D 2». Матрица смежности отводит клетку каждой паре вершин, и отсутствие дороги видно по пустой клетке; граф один и тот же, различается только способ записи.
Частые вопросы
Что такое матрица смежности простыми словами (для 7–9 класса)?
Матрица смежности — это квадратная таблица, которой задают граф: строки и столбцы подписаны одними и теми же вершинами, а клетка на пересечении строки A и столбца B показывает, есть ли ребро между A и B. В простом случае в клетке пишут 1 (ребро есть) или 0 (нет), а в таблице расстояний — длину ребра; пустая клетка там означает, что прямой дороги нет.
Как матрица смежности выглядит на практике?
Таблица расстояний для пунктов A, B, C, D: в строке A стоят 4 (в столбце B) и 9 (в столбце C), клетка A–D пуста — прямой дороги нет. Есть ещё дороги B–C = 3 и C–D = 2, других нет. Путь A→C→D = 9 + 2 = 11 км, а A→B→C→D = 4 + 3 + 2 = 9 км: он короче, хотя дорог в нём больше.
В каких заданиях ОГЭ встречается «матрица смежности»?
В заданиях на знание понятий информатики — потренируйся в тренажёре Совелия.