Пятница, 09.12.2016, 04:51
Главная Регистрация RSS
Вы вошли как Гость | Группа "Гости"Приветствую Вас, Гость
Поделиться
Статистика
Яндекс.Метрика
Flag Counter
Онлайн всего: 4
Гостей: 4
Пользователей: 0
» »
13:26
как построить матрицы смежности, инцидентности


матрицы смежности, инцидентности

Пусть D = (V, Х)орграф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Image

Определение. Матрицей инцидентности орграфа D называется (nґm) –матрица B(D)=[bij], у которой

Image

Введем также матрицы смежности и инцидентности для неориентированных графов. Пусть G = (V, X) – граф, где V={v1, v2, …,vn}, X={x1, x2, …, xm}.

Определение. Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Image

Определение. Матрицей инцидентности графа G называется (nґm) –матрица B(G)=[bij], у которой

Image

С помощью введенных матриц удобно задавать графы для обработки на ЭВМ. Используя матрицу смежности легко определить локальные степени вершин графа: сумма элементов матрицы по строке равна локальной степени соответствующей вершины. Для орграфов по строке определяются полустепени исхода, по столбцам – полустепени захода.

Пример 72.

Построить матрицы смежности и инцидентности для графа G = (V, X) (рис. 25).

Решение.

ImageМатрица смежности имеет вид

Image.

Поскольку граф не имеет петель, то на главной диагонали стоят все нули. Для любого графа матрица смежности симметрична относительно главной диагонали.


ImageДля того, чтобы построить матрицу инцидентности необходимо пронумеровать ребра графа (рис. 26). Матрица инцидентности имеет вид:

Image

Напомним, что в строках указываются вершины, в столбцах – ребра. Матрица инцидентности может быть как квадратной, так и прямоугольной.

Пример 73.

Построить матрицы смежности и инцидентности для  орграфа D= (V, X) (рис. 27).

Решение.

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

Image

Матрица инцидентности имеет вид

Image

Категория: Комбинаторика | Просмотров: 10026 | Добавил: Admin | Теги: матрица смежности, матрица инцидентности | Рейтинг: 5.0/2


Похожие материалы:

Всего комментариев: 0
avatar
  .