<<
>>

Матрицы графов.

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

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

Определение.

Если вершина v является крнцом ребра х, то говорят, что v и х – инциндентны.

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

Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.

x1

v1 x4 v2

x2

x3

v3

Составим матрицу смежности:

v1 v2 v3
v1 0 1 0
v2 1 0 1
v3 1 0 0

Т.е. – матрица смежности.

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

x1 x2 x3 x4
v1 –1 0 1 1
v2 1 –1 0 –1
v3 0 1 –1 0

Т.е.

Если граф имеет кратные дуги (ребра), то в матрице смежности принимается aij=k, где k – кратность дуги (ребра).

С помощью матриц смежности и инциндентности всегда можно полностью определеить граф и все его компоненты.

Такой метод задания графов очень удобен для обработки данных на ЭВМ.

Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисованть также орграф , имеющий матрицу смежности Q, определить его матрицу инциндентности С.

x4

x3

v2

x2 x5

x6

x1 v1 v3 x7 x8

x10

x11 x9

v4

Составим матрицу инциндентности:

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11
v1 1 1 0 0 0 0 0 0 0 0 1
v2 0 1 1 1 1 1 0 0 0 1 0
v3 0 0 0 0 1 1 1 1 1 0 0
v4 0 0 0 0 0 0 0 0 1 1 1

Итого:

Построим теперь ориентированный граф с заданной матрицей смежности.

x4

x5

v2

x2 x7

х3 x6

x1 v1 х8 v3 x10 x11

х9

х17 х15 x14

x16 х13 x12

v4

Составим матрицу инцидентности для ориентированного графа.

Элемент матрицы равен 1, если точка является концом дуги, –1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.

Таким образом, операции с графами можно свести к операциям с их матрицами.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме Матрицы графов.:

  1. ряд примеров приложений теории графов.
  2. 3.4. Методические подходы к анализу взаимосвязей показателей устойчивости и скрытых воздействий с применением экономико-математических методов
  3. Интервьюирование
  4. 8.5. Проектирование функциональной модели.Матрица разделения административных задач управления (РАЗУ)
  5. Содержание дисциплины
  6. Матрицы графов.
  7. Перечень вопросов к экзамену на первом курсе
  8. 4.2. СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ
  9. 3.1. Элементы теории графов
  10. ГЛОССАРИЙ
  11. §5. Графы
  12. 3.8. Конструктивные особенности компьютерных томографов
  13. 14.Індикаторний метод оцінки конкурентоспроможності потенціалу підприємства і його різновиди.
  14. 5. Вычисление собственных значений матрицы Методом Данилевского
  15. §2.2. Способы задания графов
  16. 3. ТЕОРИЯ ГРАФОВ
  17. 3.1.3. Матричное задание графов. Матрицы смежности, инцидентности
  18. 3.2.2. Расстояния в графе. Диаметр, центр, радиус графа
  19. 3.2.3. Нахождение минимального пути в нагруженном графе
  20. 5.5 Многокритериальный выбор на языке бинарных отношений