Математический аппарат инженера
Шрифт:
Например, матрица инцидентности графа, приведенного на Рис. 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.
Рис. 11. Граф и его части:
а - граф; б - часть графа; в - подграф; г – суграф.
Исходный граф по отношению к его подграфу называют надграфом, а по отношению к суграфу - сверхграфом. Совокупность всех ребер графа, не принадлежащих его подграфу (вместе с инцидентными вершинами), образует дополнение подграфа. Говорят, что подграфы G' = (V', Е') и G" = (V", Е") разделены ребрами, если они не имеют общих ребер (Е' Е" =) и разделены вершинами, если у них нет общих вершин (V' V" =).
10. Связность. Две вершины графа называют связанными, если существует маршрут, соединяющий эти вершины. Граф, любая пара вершин которого связана, называют связным графом. Очевидно, в связном графе между любыми двумя вершинами существует простая цепь, так как из связывающего их маршрута всегда можно удалить циклический участок, проходящий через некоторую вершину более одного раза (Рис. 12, где маршрут между вершинами vi и vj, изображен жирными линиями).
Если граф не связный, то множество его вершин можно единственным образом разделить на непересекающиеся подмножества, каждое из которых содержит все связанные между собой вершины и вместе с инцидентными им ребрами образует связный подграф.
– 53 -
Таким образом, несвязный граф представляет собой совокупность отдельных частей (подграфов), называемых компонентами. На Рис. 13 показан подграф, состоящий из трех компонент (изолированная вершина считается компонентой).
Часто отношение связности усложняется дополнительными условиями. Граф называют циклически связным, если любые две различные вершины содержатся в цикле (например, граф на Рис. 11, а циклически связный, а граф на Рис. 12 - нет, так как вершина и, не содержится ни в каком цикле с другими вершинами). Граф называют R– связным, если любая пара различных вершин связана, по крайней мере R цепями, которые не имеют общих вершин (кроме начальной и конечной). Так, граф на Рис. 11, а двусвязный, а на Рис. 12 - односвязный.