Перечислите без пробелов и разделителей элементы второй строки матрицы достижимости для орграфа G

Предмет: Теория графов
Раздел: Матрицы достижимости орграфов

Дано: орграф G = \langle V = \{v_1, v_2, v_3, v_4\}, E = \{(v_2, v_1), (v_1, v_3), (v_4, v_2), (v_3, v_1)\}\rangle.

Нужно найти вторую строку матрицы достижимости этого орграфа.

Шаг 1: Построим матрицу смежности

Нумеруем вершины:
v_1 = 1, v_2 = 2, v_3 = 3, v_4 = 4

Матрица смежности A размера 4x4, где A[i,j] = 1, если есть ребро из вершины v_i в вершину v_j, иначе 0.

Ребра:

• (v2, v1) → из 2 в 1
• (v1, v3) → из 1 в 3
• (v4, v2) → из 4 в 2
• (v3, v1) → из 3 в 1

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

 A = \begin{pmatrix} 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \end{pmatrix} 

Шаг 2: Определение матрицы достижимости

Матрица достижимости R показывает, достижима ли вершина v_j из вершины v_i по пути длины ≥ 1.

Правило:
R = A + A^2 + A^3 + \dots + A^{n}, где n = 4 — количество вершин.
Элементы матрицы достижимости — 1, если существует хотя бы один путь из v_i в v_j, иначе 0.

Шаг 3: Найдем степени матрицы A

Посчитаем A^2 = A \times A:

 A^2 = \begin{pmatrix} 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \end{pmatrix} \times \begin{pmatrix} 0 & 0 & 1 & 0 \ 1 & 0 & 0 & 0 \ 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \end{pmatrix} \end{formula> Вычислим поэлементно вторую строку A^2:

Вторая строка A — (1,0,0,0)

Умножаем на столбцы A:

• (2,1): 1*0 + 0*1 + 0*1 + 0*0 = 0
• (2,2): 1*0 + 0*0 + 0*0 + 0*1 = 0
• (2,3): 1*1 + 0*0 + 0*0 + 0*0 = 1
• (2,4): 1*0 + 0*0 + 0*0 + 0*0 = 0

Итого вторая строка A^2 — (0,0,1,0).

Шаг 4: Найдем A^3 = A^2 \times A

Вторая строка A^2 — (0,0,1,0)

Умножаем на столбцы A:

• (2,1): 0*0 + 0*1 + 1*1 + 0*0 = 1
• (2,2): 0*0 + 0*0 + 1*0 + 0*1 = 0
• (2,3): 0*1 + 0*0 + 1*0 + 0*0 = 0
• (2,4): 0*0 + 0*0 + 1*0 + 0*0 = 0

Вторая строка A^3 — (1,0,0,0).

Шаг 5: Найдем A^4 = A^3 \times A

Вторая строка A^3 — (1,0,0,0)

Умножаем:

• (2,1): 1*0 + 0*1 + 0*1 + 0*0 = 0
• (2,2): 1*0 + 0*0 + 0*0 + 0*1 = 0
• (2,3): 1*1 + 0*0 + 0*0 + 0*0 = 1
• (2,4): 1*0 + 0*0 + 0*0 + 0*0 = 0

Вторая строка A^4 — (0,0,1,0).

Шаг 6: Сложим все степени

Складываем поэлементно вторую строку матриц A + A^2 + A^3 + A^4:

 (1,0,0,0) + (0,0,1,0) + (1,0,0,0) + (0,0,1,0) = (1+0+1+0, 0+0+0+0, 0+1+0+1, 0+0+0+0) = (2,0,2,0) 

В матрице достижимости элементы равны 1, если сумма > 0, иначе 0.

Итоговая вторая строка матрицы достижимости:

(1,0,1,0)

Ответ: без пробелов и разделителей — 1010