13:26
как построить матрицы смежности, инцидентности
|
матрицы смежности, инцидентностиПусть D = (V, Х) – орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}. Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой Определение. Матрицей инцидентности орграфа D называется (nґm) –матрица B(D)=[bij], у которой Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}. Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой Определение. Матрицей инцидентности графа G называется (nґm) –матрица B(G)=[bij], у которой С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины. Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода. Пример 72. Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25). Решение.
Поскольку граф не имеет петель, то на главной диагонали стоят все нули. Для любого графа матрица смежности симметрична относительно главной диагонали.
Напомним, что в строках указываются вершины, в столбцах – ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной. Пример 73. Построить матрицы смежности и инцидентности для орграфа D= (V, X) (рис. 27). Решение.
Матрица инцидентности имеет вид |
|
Всего комментариев: 0 | |