Спирина, М.С. Дискретная математика

ния графа (диаграммой, матрицей, таблицей) является указание соответствия между множествами я вершин V, и т ребер X,. Одним из самых распространенных способов задания графа является матричный способ. Пусть дан граф G(V, X), где И= {Fj, V2, ..., К) ~ вершины, а Х= {Хь Х2, X J — ребра графа. ' Назовем матрицей инцидентности таблицу В, состоящую из я с т р о к (вершины) и т столбцов (ребра), в которой: . для неориентированного графа: b)j= 1, если вершина V, инцидентна ребру Х-, bjj = 0, если вершина V, не инцидентна ребру X/, . для ориентированного графа: bij- 1, если вершина V, является началом дуги Х-, Ь^— 0, если вершина V, не инцидентна дуге X/, by— —1, если вершина V, является концом дуги Ху Очевидно, что в каждом столбце матрицы инцидентности долж­ но быть только два ненулевых числа, так как ребро инцидентно двум вершинам. Число ненулевых элементов каждой строки —сте­ пень соответствующей вершины. Но в математике удобнее рабо­ тать с квадратными матрицами, так как для них хорошо разрабо­ тан соответствующий алгебраический аппарат. Назовем матрицей смежности графа G( V, X) без кратных ребер квадратную матрицу А порядка я, в которой: Oj = 1, если (Vlf Vj) g X, ay - 0, если ( Vj, Vj) i X. Поскольку для неориентированного графа ребра ( V/, и ( Vj, Vj) одновременно принадлежат или не принадлежат графу, так как символизируют одно и то же ребро, то = ajr Матрица смеж­ ности неориентированного графа является симметрической и не меняется при транспонировании. Хотя формально каждая вершина всегда смежна сама с собой, в матрице смежности мы будем ставить акк = 0, если у нее нет петли, и акк= 1, если есть одна петля. Итак, если граф имеет матрицу смежности и не имеет петель, на главной диагонали у него всегда стоят нули. Например, орграф на рис. 2.3 можно задать такой таблицей инцидентности (табл. 2.1). Т а б л и ц а 2.1 Таблица инцидентности орграфа V j X j S t r u V\ - l 0 l 0 V j 0 1 - l 1 v 3 1 - 1 0 - 1 85