Знаковая модель

Граф — это знаковая модель системы объектов и связей между ними. Состоит из вершин (объекты) и рёбер (связи). Рёбра могут быть ориентированными (дуги, есть направление) или неориентированными (связи без направления).

Табличная модель

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

Матрица смежности

Квадратная таблица размера N×N (N — число вершин). В ячейке M[i][j] стоит 1, если есть ребро из вершины i в вершину j, и 0, если ребра нет. Для неориентированного графа матрица симметрична: M[i][j] = M[j][i].

Весовая матрица

Если у рёбер есть веса (расстояния, стоимости, пропускная способность), то в ячейке W[i][j] записывается вес ребра (число). Если прямого ребра нет — ставится 0 или прочерк. По диагонали всегда 0 (путь из вершины в саму себя).

Почему в ячейках нули или числа?

Ноль на диагонали (M[i][i]): путь из вершины в саму себя не рассматривается — поэтому по диагонали всегда 0.

Ноль вне диагонали: между вершинами i и j нет прямого ребра — нет связи, поэтому 0.

Единица (1): в матрице смежности — ребро существует (просто факт связи).

Число (вес): в весовой матрице — ребро существует и его вес равен этому числу (например, расстояние 7 км, стоимость 5 рублей).

Симметрия: в неориентированном графе M[i][j] = M[j][i] — если есть дорога из A в B, она же ведёт и из B в A. В ориентированном графе это не так: может быть дорога из A в B, но не обратно.

Кратчайший путь по весовой матрице

По весовой матрице можно найти кратчайший маршрут между городами. Для этого перебирают все возможные маршруты и суммируют веса рёбер. Маршрут с наименьшей суммой — кратчайший. В небольших графах (4–5 вершин) это делается вручную перебором. Важно: вес «0» означает «нет дороги», а не «бесплатно».

Генератор задач

Заполняйте матрицу: 1 — есть ребро, 0 — нет ребра.

Нажмите «Новая задача»

Граф

Матрица смежности

Пошаговый алгоритм построения матрицы

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

1

Определите вершины

Выпишите все вершины графа в одинаковом порядке для строк и столбцов. Например: A, B, C, D, E. Строки и столбцы матрицы будут иметь те же заголовки.

2

Определите тип графа

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

3

Заполните диагональ нулями

По диагонали (где номер строки равен номеру столбца) всегда ставьте 0. Путь из вершины в саму себя не учитывается.

4

Проверьте каждую пару вершин

Для каждой ячейки M[i][j] (где i ≠ j) посмотрите на граф: есть ли ребро из вершины i в вершину j?

  • Ребро есть → поставьте 1 (для матрицы смежности) или вес ребра (для весовой матрицы)
  • Ребра нет → поставьте 0
5

Проверьте симметрию (для неориентированного графа)

Если граф неориентированный, убедитесь что M[i][j] = M[j][i]. Каждое ребро даёт две симметричные единицы (или два одинаковых веса). Если граф ориентированный — направление имеет значение: M[i][j] может быть 1, а M[j][i] — 0.

6

Проверьте результат

Пересчитайте количество рёбер: каждое неориентированное ребро даёт две единицы в матрице, каждое ориентированное — одну. Сумма всех единиц в матрице смежности неориентированного графа = 2 × (число рёбер).

Интерактивная демонстрация

Просмотрите пошаговое построение матрицы для текущей задачи из генератора.

Типовые задания в формате ОГЭ

Задания составлены по образцу ОГЭ по информатике по теме «Графы. Поиск путей». Каждое задание можно решить прямо здесь и проверить ответ.

Задачи повышенной сложности в стиле ЕГЭ

Это отдельная ступень после базовых заданий ОГЭ: подсчёт путей динамическим программированием и маршруты с дополнительным условием. Задачи учебные, а не копии официального банка.

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