Матрица инцидентности
Ребро инцидентно вершине vi, если эта вершина является одним из концов ребра . Граф можно задавать так называемой матрицей инцидентности, которая строится по следующему правилу: строки матрицы соответствуют ребрам графа, а столбцы – вершинам. Элементы этой матрицы равны:
Если строим ориентированный граф то ставим -1 возле вершины из которой выходит ребро, и 1 в которую входит ребро.
Пример: По заданной матрице инцидентности построить неориентированный граф.
|
I |
II |
III |
IV |
V |
1 |
1 |
1 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
0 |
3 |
0 |
1 |
0 |
1 |
0 |
4 |
1 |
0 |
0 |
0 |
1 |
5 |
0 |
1 |
0 |
0 |
0 |
6 |
0 |
0 |
1 |
1 |
0 |
V
III 6 IV
2 3
I 1 II
Пример: По заданной матрице инцидентности построить ориентированный граф.
|
I |
II |
III |
IV |
1 |
-1 |
1 |
0 |
0 |
2 |
-1 |
0 |
1 |
0 |
3 |
1 |
0 |
0 |
-1 |
4 |
0 |
1 |
0 |
-1 |
5 |
0 |
0 |
-1 |
-1 |
IV
5 4
III 3 II
2 1
I
Матрица смежности
Матрица смежности – это квадратная матрица, строки и столбцы которой – вершины. Заполняется матрица для неориентированного графа следующим образам: ставится 1, если две вершины соединены ребром и 0 – если не соединены.
Пример: по матрице смежности начертить граф:
|
1 |
2 |
3 |
4 |
5 |
6 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
2 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
1 |
0 |
0 |
1 |
1 |
0 |
4 |
0 |
0 |
1 |
0 |
0 |
1 |
5 |
0 |
1 |
1 |
0 |
0 |
1 |
6 |
0 |
0 |
0 |
1 |
1 |
0 |
2
1 3
4
6
5
Матрица смежности для графа у которого нет петель является симметрической.
Матрица смежности для ориентированного графа заполняется 1 если ребро выходит из i-ой вершины и входит в j-ю вершину.
Сумма единиц по строке в матрице смежности неориентированного графа дает степень вершины.