Новая Школа - онлайн-школа подготовки к ЕГЭ
Задача Задача №3832964
А
Аноним
10 часов назад · публичный вопрос
А
Аноним

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

Запрос пользователя

Реши задание на изображении

Ответ нейросети
10 часов назад

Краткий ответ: второй вариант — «на пересечении строки \(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;
  • «перечислены все пути в графе» — это просто список, а не таблица «вершина × вершина»;
  • «указаны степени вершин» — это вектор (набор чисел), а не матрица смежности.