Типы и способы задания.

Задать граф – значит описать множества его вершин и ребер, а также отношение инцидентности. Для описания вершин и ребер достаточно их занумеровать. Пусть вершины графа G; ребра. Отношение инцидентности задается:

1. по определению (V, E, отношение инцидентности)
2. графически
3. Матричный способ (матрицей инцидентности)

Матрицей инцидентности размера : по вертикали и горизонтали указываются вершины и ребра соответственно, а на пересечение i – й вершины и j –го ребра в случае неориентированного графа проставляется 1, если они инцидентны, и 0 – в противном случае, т.е.

если ребро инцидентно вершине , а в случае орграфа: -1, если вершина является началом ребра, 1- если вершина является концом ребра, и 0 – если вершина и ребро не инцидентны; если некоторая вершина является для ребра и началом, и концом (т.е. ребро - петля), проставляется любое другое число, например 2.

1. Списком ребер графа, представленным двумя столбцами: в левом перечисляются все ребра , а в правом – инцидентные ему вершины ; для н – графа порядок вершин в строке произволен, для орграфа первым стоит номер начала ребра;
2. Матрицей смежности - квадратной матрицей размера : по вертикали и горизонтали перечисляются все вершины , а на пересечении k –й и l –й вершин в случае н – графа проставляется число, равное числу ребер с началом в k – й вершине и концом в l –й.

Если два графа равны, то их матрицы совпадают. Если в графе поменять нумерацию вершин, матрицы (и список ребер) в общем случае изменяются, т.е. вид матриц и списка ребер зависит от нумерации вершин и ребер графа. Строго говоря, граф считается полностью заданным, если нумерация его вершин зафиксирована.