Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Когда граф конечен для описания его вершин и ребер достаточно их занумеровать. Отношение инцидентности определяют матрицей ij, имеющей m строк и n столбцов. Столбцы соответствуют вершинам графа, строки – ребрам графа. Если ребро еi инцидентно вершине vj, то ij = 1, в противном случае ij = 0. Это матрица инцидентности для неориентированного графа.
Пример (Задание №9)
Обозначим вершины римскими цифрами, а ребра – арабскими. Матрица инцидентности для данного графа выглядит следующим образом:
I | II | III | IV | V | VI | VII | |
В матрице инцидентности орграфа ij = -1, если вершина vj – начало дуги ai; ij = 1, если vj – конец дуги ai; если ai – петля, а vj – инцидентная ей вершина, то ij = а, где а – любое число отличное от 0, 1, -1. В остальных случаях ij = 0.
|
|
Пример (Задание №10): построим ориентированный граф и матрицу инцидентности для нее:
|
Из матрицы инцидентности мы видим, что в каждой строке есть только два элемента (или один, если ребро является петлей) отличных от 0. Поэтому такой способ задания графа посчитали неэкономичным. Отношение инцидентности можно задать так же с помощью списков ребер графа. Каждая строка этого списка соответствует ребру, в ней записывают номера вершин, инцидентных ему. Для неориентированного графа порядок вершин в строке произволен, а для орграфа первым записывают номер вершины начала дуги, а вторым – номер вершины конца дуги.
Составим списки ребер для данных графов:
Таб. 8 Списки ребер неориентированного графа
Таб. 9 Списки ребер орграфа
Ребра | Вершины | Ребра | Вершины | |
I, II | I, II | |||
I, III | I, III | |||
II, IV | II, IV | |||
I, V | III, V | |||
II, VI | III, IV | |||
III, IV | III, VII | |||
III, V | VI, VII | |||
IV, VI | ||||
V, VII | ||||
VI, VII |
Каждая строка списка ребер соответствует строке матрицы с тем же номером ребра.