Сверь числа и знаки с фото.
- Матрица смежности графа — это таблица, в которой... Выбери подходящие варианты ○ записаны веса рёбер ○ на пересечении строки i и столбца j стоит 1, если вершины i и j соединены ребром, и 0 — если нет ○ перечислены все пути в графе ○ указаны степени вершин
Краткий ответ: второй вариант — «на пересечении строки \(i\) и столбца \(j\) стоит 1, если вершины \(i\) и \(j\) соединены ребром, и 0 — если нет».
Как понять принцип
Матрица смежности — это квадратная таблица размером \(n \times n\), где \(n\) — число вершин графа. Строки и столбцы подписаны номерами вершин, а каждая клетка отвечает на вопрос «есть ли ребро?»:
\[ a_{ij} = \begin{cases} 1, & \text{если вершины } i \text{ и } j \text{ соединены ребром},\\ 0, & \text{если ребра между ними нет.} \end{cases} \]
Проверка на маленьком примере
Граф из трёх вершин с рёбрами \(1\text{—}2\) и \(2\text{—}3\):
\[ A = \begin{pmatrix} 0 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 0 \end{pmatrix} \]
Проверяем себя:
- матрица симметрична относительно диагонали (граф неориентированный, ребро \(1\text{—}2\) даёт единицы и в \(a_{12}\), и в \(a_{21}\));
- сумма чисел в строке равна степени вершины: в первой строке \(0+1+0=1\), и вершина 1 действительно имеет одну связь;
- по диагонали нули, потому что петель нет.
Почему остальные варианты не подходят
- «записаны веса рёбер» — это матрица весов (для взвешенного графа), в ней в клетках стоят числа-веса, а не только 0 и 1;
- «перечислены все пути в графе» — это просто список, а не таблица «вершина × вершина»;
- «указаны степени вершин» — это вектор (набор чисел), а не матрица смежности.