Страница 14 из 32
- 49 -
Граф можно представить также матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее (ij) - элемент равен числу кратных ребер, связывающих вершины vi и vj, (или направленных от вершины vi к вершине vj, для орграфа). Например, для графов, приведенных на рис. 8, а и 9, а, имеем соответственно следующие матрицы смежности:
Матрица смежности неориентированного графа всегда симметрична а орграфа - в общем случае несимметрична. Неориентированным ребрам соответствуют пары ненулевых элементов, симметричных относительно главной диагонали матрицы, дугам - ненулевые элементы матрицы, а петлям - ненулевые элементы главной диагонали. В столбцах и строках, соответствующих изолированным вершинам, все элементы равны нулю. Элементы матрицы простого графа равны 0 или 1, причем все элементы главной диагонали нулевые.
Для взвешенного графа, не содержащего кратных ребер, можно обобщить матрицу смежности так, что каждый ее ненулевой элемент равняется весу соответствующего ребра или дуги. Обратно, любая квадратная матрица n-го порядка может быть представлена орграфом с n вершинами, дуги которого соединяют смежные вершины и имеют веса, равные соответствующим элементам матрицы. Если матрица симметрична, то она представима неориентированным графом.
6. Инцидентность. Если вершина vi, является концом ребра ek то говорят, что они инцидентны: вершина vi инцидентна ребру ek и ребро ek, инцидентно вершине vi. В то время как смежность представляет собой отношение между однородными объектами (вершинами), инцидентность — это отношение между разнородными объектами (вершинами и ребрами). При рассмотрении орграфов различают положительную инцидентность (дуга исходит из вершины) и отрицательную инцидентность (дуга заходит в вершину).
Рассматривая инцидентность вершин и ребер (p и q) - графа, можно представить его матрицей инцидентности размера p × q, строки которой соответствуют вершинам, а столбы - ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: ij-элемент равен 1, если вершина vi, инцидентна ребру ei, и равен нулю, если vi, и ei, не инцидентны.
- 50 -
В случае орграфа ненулевой ij-элемент равен 1, если vi начальная вершина дуги ei, и равен - 1, если vi - конечная вершина дуги ei.
Например, матрица инцидентности графа, приведенного на Рис. 9, а, имеет вид:
Каждый столбец матрицы инцидентности содержит обязательно два единичных элемента (для орграфа эти элементы всегда имеют различные знаки и равны соответственно 1 и —1). Количество единиц в строке равно степени соответствующей вершины (для орграфа количество положительных единиц определяет положительную степень, а количество отрицательных единиц — отрицательную степень). Нулевая строка соответствует изолированной вершине, а нулевой столбец - петле.
Рис. 10. Изоморфные графы
Следует иметь в виду, что нулевой столбец матрицы инцидентности лишь указывает на наличие петли, но не содержит сведений о том, с какой вершиной эта петля связана (в практических приложениях это может быть несущественно).
7. Изоморфизм. На Рис. 10 изображены три графа, которые с геочетрической точки зрения совершенно различны (пересечение ребер, если оно не отмечено точкой, не является вершиной). Но по существу они различаются лишь начертанием, а отношения инцидентности (при соответствующем обозначении вершин и ребер) для них одинаковы. Графы, для которых сохраняется отношение инцидентности, называются изоморфными.
Ясно, что матрица инцидентности определяет граф без петель с точностью до изоморфизма. Обычно на ее основе можно изобразить различные в геометрическом отношении, но изоморфные между собой графы, каждый из которых называют геометрической реализацией. Графы, которые имеют одинаковые начертания и отличаются лишь нумерацией вершин и ребер, не будучи тождественными, являются изоморфными.
- 51 -
Если существенные свойства графа не связаны со способом его изображения на плоскости или нумерацией вершин и ребер, то изоморфные графы, как правило, не различают между собой.
8. Маршруты. Нередко задачи на графах требуют выделения различных маршрутов, обладающих определенными свойствами и характеристиками. Маршрут длины m определяется как последовательность т ребер графа (не обязательно различных) таких, что граничные вершины двух соседних ребер совпадают. Маршрут проходит и через все вершины, инцидентные входящим в него ребрам. Примерами маршрутов на графе Рис. 9, а могут служить последовательности ( e1, e3, e2, e3, e5 ), ( e5, e6, e4, e4). Первый маршрут проходит через последовательность вершин ( v1, v2, v3, v2, v3, v5 ) и соединяет вершины v1 и v5 a второй — через последовательность вершин ( v3, v5, v5, v2, v5 ) и соединяет вершины v3 и v5. Замкнутый маршрут приводит в ту же вершину, из которой он начался.
Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называется циклом, а простая цепь - простым циклом. Так, на графе Рис. 9, а ( e2, e5, e6 ) - цепь, ( e1, e2, e5 ) -простая цепь, ( e2, e3, e4, e5 ) - цикл, ( e2, e4, e5 ) - простой цикл.
Цикл, который содержит все ребра графа, называется эйлеровым циклом (задача о кенигсбергских мостах сводится к выяснению существования такого цикла), а граф, в котором имеется такой цикл, называется эйлеровым графом. Простой цикл, который проходит через все вершины графа, называют гамильтоновым. Если критерий существования эйлерового цикла очень прост (необходимо, чтобы степени всех вершин были четными), то для гамильтоновых циклов никакого общего правила не найдено.
Ориентированные маршруты на орграфе определяются аналогично с той разницей, что начальная вершина каждой последующей дуги маршрута должна совпадать с конечной вершиной предыдущей дуги. Иначе говоря, движение по маршруту допускается только в направлениях, указанных стрелками. Маршрут, не содержащий повторяющихся дуг, называется путем, а не содержащий повторяющихся вершин - простым путем. Замкнутый путь называется контуром, а простой замкнутый путь - простым контуром. Граф (орграф) называется циклическим (контурным), если он содержит хотя бы один цикл (контур), в противном случае он называется ациклическим (бесконтурным).
- 52 -
Понятия цепи и цикла применимы и к ориентированным графам. При этом направления дуг не учитываются, т. е. по существу вместо орграфа рассматривают неориентированный соотнесенный ему граф.
9. Части графа. Граф G' = (V', Е') является частью графа G = (V, Е), если V' ⊂ V и Е' ⊂ Е, т. е. граф содержит все вершины и ребра любой его части. Часть, которая, наряду с некоторым подмножеством ребер графа, содержит и все инцидентные им вершины, называется подграфом. Часть, которая наряду с некоторым подмножеством ребер графа, содержит все вершины графа (V’=V, Е' ⊂ Е), называется суграфом. Рассмотренные графы показаны на Рис. 11.