Матрица инцидентности H - это матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.
Матрица инцидентности для неориентированного графа
Элемент матрицы инцидентности для неориентированного графа hij определяется следующим образом:
- равен единице, если вершина vi инцидентна ребру ej;
- равен нулю, если вершина vi не инцидентна ребру ej.
Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
Ответ.
V
|
1-2
|
1-3
|
2-4
|
2-5
|
3-5
|
1
|
1
|
1
|
0
|
0
|
0
|
2
|
1
|
0
|
1
|
1
|
0
|
3
|
0
|
1
|
0
|
0
|
1
|
4
|
0
|
0
|
1
|
0
|
0
|
5
|
0
|
0
|
0
|
1
|
1
|
Элемент матрицы инцидентности для ориентированного графа hij определяется следующим образом:
- равен минус единице, если вершина vi является началом ребра ej;
- равен единице, если вершина vi является концом ребра ej;
- равен нулю, если вершина vi не инцидентна ребру ej.
Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
Ответ.
V
|
1-2
|
1-3
|
2-4
|
2-5
|
3-5
|
1
|
1
|
-1
|
0
|
0
|
0
|
2
|
-1
|
0
|
-1
|
-1
|
0
|
3
|
0
|
1
|
0
|
0
|
-1
|
4
|
0
|
0
|
1
|
0
|
0
|
5
|
0
|
0
|
0
|
1
|
1
|
На сайте есть пример реализации на языке программирования С++ алгоритма обхода в глубину графа, представленного матрицей инцидентности.
Do'stlaringiz bilan baham: |
