2014-02-09
927
Способы задания графов
В общем виде задать граф - значит описать множества его вершин и ребер, а также отношение инцидентности. Для описания вершин и ребер достаточно их занумеровать. Пусть v1,v2,..., vn - вершины графа G; е1,е2,...,ет - ребра. Отношение инцидентности задается:
• матрицей инцидентности 
размера тхп: по вертикали и горизонтали указываются вершины и ребра соответственно, а на пересечении i -й вершины и j -го ребра в случае неориентированного графа проставляется 1, если они инцидентны, и 0 - в противном случае, т.е.
а в случае орграфа: -1, если вершина является началом ребра, 1 - если вершина является концом ребра, и 0 - если вершина и ребро не инцидентны; если некоторая вершина является для ребра и началом, и концом (т.е. ребро - петля), проставляется любое другое число, например 2,
• списком ребер графа, представленным двумя столбцами: в левом перечисляются все ребра 
, а в правом инцидентные ему вершины vi,vj, для н-графа порядок вершин в строке произволен, для орграфа первым стоит номер начала ребра;
|
|
|
• матрицей смежности 
| - квадратной матрицей размера п х п: по вертикали и горизонтали перечисляются все вершины 
, а на пересечении k-й и l-й вершин в случае н-графа проставляется число, равное числу ребер, соединяющих эти вершины; для орграфа 
равно числу ребер с началом в к-й вершине и концом в l-й.
Если два графа равны, то их матрицы совпадают. Если в графе поменять нумерацию вершин, матрицы (и список ребер) в общем случае изменяются, т.е. вид матриц и списка ребер зависит от нумерации вершин и ребер графа. Граф считается полностью заданным, если нумерация его вершин зафиксирована. Графы, отличающиеся только нумерацией вершин, являются изоморфными.
Задать матрицами инцидентности и смежности, а также списком ребер графы 
,
(рис. 4.3).
Рис. 4.3. Н-граф G1 и орграф G2
Матрицы инцидентности графов иприведены в табл. 1. В матрице инцидентности в каждом столбце только два элемента, отличных от 0 (или один, если ребро - петля).
Таблица 1. Матрица инцидентности графов и
|
| a | b | c | d | e | f | g |
| a | b | c | d | e | f | g | ||||
| -1 | -1 | ||||||||||||||||||
| -1 | -1 | -1 | |||||||||||||||||
| -1 | |||||||||||||||||||
Список ребер орграфа приведен в табл. 2 для н–графа он аналогичен, однако последовательность указания вершин здесь безразлична. Матрицы смежности графов ,даны в табл.3.
|
|
|
| Таблица 3. | Таблица 2. | ||||||||||||||||
|
|
| Ребро | Вершины | ||||||||||||||
| a | |||||||||||||||||
| b | |||||||||||||||||
| c | |||||||||||||||||
| d | |||||||||||||||||
| e | |||||||||||||||||
| f | |||||||||||||||||
| g |
