4. Матрицы, соответствующие графам.

Пусть дан граф G с вершинами v1,..., v_n и ребрами x_h ..., х_т.

Матрица смежности графа G — это матрица A(G) размера п^хп (п — число вершин) с элементами, равными 1, если в графе вершина vi смежна с вершиной vj, и элементами, равными 0, в других случаях.

Матрица инцидентности графа G — это матрица B(G) размера п^хm (п — число вершин, т — число ребер) с элементами, равными 1, если вершина vi и ребро xj - инцидентны, и элементами, равными 0, в других случаях.

Для графа G построим матрицу смежности A(G) и матрицу инцидентности B(G).

Так как у графа 5 вершин и 6 ребер, то размеры матрицы смежности будут 5x5, а матрицы инцидентности - 5x6.

Пусть дан граф D с вершинами v1,..., v_n и ребрами x_h ..., х_т.

Матрица смежности орграфа D — это квадратная матрица A(D) размера п*п (п — число вершин) с элементами, равными 1, если в орграфе вершины vi vj соединены дугой, и элементами, равными 0, в других случаях.

Матрица инцидентности орграфаD — это матрица B(D) размера п *т (п — число вершин, т — число ребер) с элементами, равными 1, если j -ая дуга заканчивается в i-ой вершине, с элементами, равными (-1), если j-ая дуга начинается в i-ой вершине, и элементами, равными 0, в других случаях.

Для орграфа D (рис. 9) построим матрицу смежности и матрицу инцидентности.

Орграф содержит 5 вершин и 6 ребер, поэтому