Матрицы, соответствующие графам.
Пусть дан граф G с вершинами v1,..., vn и ребрами xh ..., хт.
Матрица смежности графа 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,..., vn и ребрами xh ..., хт.
Матрица смежности орграфа D — это квадратная матрица A(D) размера п*п (п — число вершин) с элементами, равными 1, если в орграфе вершины vi vj соединены дугой, и элементами, равными 0, в других случаях.
Матрица инцидентности орграфа D — это матрица B(D) размера п *т (п — число вершин, т — число ребер) с элементами, равными 1, если j -ая дуга заканчивается в i-ой вершине, с элементами, равными (-1), если j-ая дуга начинается в i-ой вершине, и элементами, равными 0, в других случаях.
Для орграфа D (рис. 9) построим матрицу смежности и матрицу инцидентности.
 |
Орграф содержит 5 вершин и 6 ребер, поэтому
Дата добавления: 2022-01-22; просмотров: 86; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!