Вычисление пределов
Криволинейный интеграл
Карта сайта

Дискретная математика Матрицы графов

 

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

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

 

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

 

 Определение. Если вершина v является крнцом ребра х, то говорят, что v и х инциндентны. Среди правильных дробей различают четыре типа так называемых простейших дробей

 

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

 

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

 

 x1

 


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

 

 

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 – кратность дуги (ребра).

 

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

 


На главную страницу сайта