Способы задания графа

Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности.

Для описания вершин и ребер достаточно их занумеровать.

Пусть вершины графа; ребра графа G.

Отношение инцидентности задается:

а) матрицей инцидентности размера (строкам соответствуют ребра, столбцам – вершины графа), в которой

для н-графа

для ор-графа

б) списком ребер графа, в котором каждая строка соответствует ребру и в ней записаны номера вершин графа, инцидентных этому ребру. Для н-графа порядок вершин в строке произволен, для ор-графа первым стоит номер вершины–начала ребра.

в) матрицей смежности размера , столбцам и строкам которой соответствуют вершины графа. Для н-графа равно количеству ребер, инцидентных i-й и j-й вершинам, для ор-графа равно количеству ребер с началом в i-й и концом в j-й вершине.

Вид матриц и списка ребер зависит от нумерации вершин и ребер графа. Граф считается полностью заданным, если нумерация его вершин зафиксирована.

Графы, отличающиеся только нумерацией вершин, называются изоморфными.

Перенумерация вершин и ребер графа задается соответственно строками и новых номеров вершин и ребер, расположенных в исходном порядке.