Упражнения 2.1 Пусть орграф задан матрицей смежности. Постройте изображение этого графа укажите степени вершин графа. По матрице смежности постройте матрицу инцидентности этого…

Чтобы помочь с заданием по орграфам, давайте рассмотрим, что такое матрица смежности и матрица инцидентности.

1. Матрица смежности орграфа — это квадратная матрица, где строки и столбцы соответствуют вершинам графа. Если существует направленное ребро от вершины \( i \) к вершине \( j \), то в ячейке \( (i, j) \) будет стоять 1, а в остальных ячейках — 0.

2. Степени вершин:

   • Входная степень вершины — это количество рёбер, направленных в эту вершину.
   • Выходная степень вершины — это количество рёбер, исходящих из этой вершины.

3. Матрица инцидентности указывает, какие рёбра инцидентны (связаны) с какими вершинами. В этой матрице строки соответствуют вершинам, а столбцы — рёбрам. Если вершина инцидентен ребру, в соответствующей ячейке будет стоять 1, если нет — 0.

Давайте теперь рассмотрим пример. Пусть у нас есть матрица смежности следующего orgрафа:

\[ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \]

Шаги для решения:

1. Изображение графа:

   • Вершины: \( A_1, A_2, A_3 \)
   • Рёбра:
     • Из \( A_1 \) в \( A_2 \)
     • Из \( A_2 \) в \( A_3 \)
     • Из \( A_3 \) в \( A_1 \)

2. Степени вершин:

   • Выходная степень \( A_1 = 1 \) (ребро \( A_1 \to A_2 \))
   • Входная степень \( A_1 = 1 \) (ребро \( A_3 \to A_1 \))
   • Выходная степень \( A_2 = 1 \) (ребро \( A_2 \to A_3 \))
   • Входная степень \( A_2 = 1 \) (ребро \( A_1 \to A_2 \))
   • Выходная степень \( A_3 = 1 \) (ребро \( A_3 \to A_1 \))
   • Входная степень \( A_3 = 1 \) (ребро \( A_2 \to A_3 \))

3. Матрица инцидентности: Для рёбер \( e_1 = (A_1, A_2) \), \( e_2 = (A_2, A_3) \), \( e_3 = (A_3, A_1) \) матрица инцидентности будет выглядеть следующим образом:

\[ \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} \]

Результат:

• Матрица смежности: \[ \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} \]
• Степени вершин:
  • \( A_1 \): входная 1, выходная 1
  • \( A_2 \): входная 1, выходная 1
  • \( A_3 \): входная 1, выходная 1
• Матрица инцидентности: \[ \begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} \]

Если у вас есть конкретная матрица смежности, вы можете предоставить ее, и вместе мы сможем пройтись по этим шагам.