3.1.3. Матричное задание графов. Матрицы смежности, инцидентности

Пусть 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).

Решение.

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

.

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

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

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

Пример 73.

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

Решение.

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

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

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 3.1.3. Матричное задание графов. Матрицы смежности, инцидентности:

  1. 3.3. Пример расчета вероятностных характеристик развития на основе данных комплекса предприятий ОАО «КАМАЗ»
  2. 1. Основные понятия теории графов
  3. ряд примеров приложений теории графов.
  4. 3.4. Методические подходы к анализу взаимосвязей показателей устойчивости и скрытых воздействий с применением экономико-математических методов
  5. Регламенты
  6. БАЛАНСОВЫЙ (МАТРИЧНЫЙ) МЕТОД ОЦЕНКИ ФИНАНСОВОЙ УСТОЙЧИВОСТИ ПРЕДПРИЯТИЯ И ЕГО ВЗАИМОСВЯЗЬ С ДЕНЕЖНЫМИ ПОТОКАМИ
  7. Матрицы графов.
  8. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  9. 4.3. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ
  10. 3.1. Элементы теории графов
  11. ГЛОССАРИЙ
  12. §5. Графы
  13. §2.2. Способы задания графов
  14. Планарные графы