Page 15 - 4336

Матрицею суміжності A графа G називається квадратна

nn-матриця, в якій елемент a i-го рядка і j-го стовпчика
i,j
дорівнює:

 числу ребер, що з'єднують вершини v та v у випадку
i
j
неорієнтованого графа;

 числу дуг з початком в i-тій вершині та кінцем в j-тій

вершині у випадку орієнтованого графа.

Занумеруємо всі вершини графа G натуральними числами

від 1 до n і всі його ребра натуральними числами від 1 до m.

Матрицею інцидентності B графа G називається nm-матриця, в

якій елемент b i-го рядка і j-го стовпчика дорівнює:
i,j
1) у випадку неорієнтованого графа:

 1, якщо ребро e інцидентне вершині v ;
i
j
 0, якщо ребро e не інцидентне вершині v ;
i
j
 , якщо ребро e є петлею, а v інцидентна їй вершина
j
i
(0, 1);

2) у випадку орієнтованого графа:

 1, якщо вершина v є початком дуги e ;
j
i
 -1, якщо вершина v є кінцем дуги e ;
j
i
 0, якщо дуга e не інцидентна вершині v ;
i
j
 , якщо дуга e є петлею, а v інцидентна їй вершина (0,
i
j
-1,1).

Список ребер графа – це таблиця, що складається із трьох

рядків. У першому перераховані всі ребра, у другому і третьому –

інцидентні їм вершини:

 у випадку неорієнтованого графа порядок вершин у

другому та третьому рядках довільний;

15