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