Cтраница 3
Под топологическим графом [80] понимается граф G ( X, U, F), вершинами которого служат некоторые выделенные точки трехмерного евклидова пространства, а ребрами - жордановы дуги, соединяющие эти точки. У звена обе инцидентные вершины ( концевые точки) различны, у петли - совпадают. Изображение абстрактного графа на плоскости само является топологическим графом, изоморфным исходному лишь при условии, что вершины изображены точками и рисунок не содержит пересечений. [31]
Есть разные способы представления графов. Для человека наиболее удобны рисунки ( по крайней мере в тех случаях, когда граф не слишком велик), но для машинной обработки более приемлемы иные формы представления. Опишем две из них, в основе которых лежит изображение графа в виде матрицы с произвольной нумерацией вершин и ребер. Если в графе G нет петель, то в каждом столбце матрицы М будет ровно две единицы. Наличие столбца с одной единицей означает, что в графе имеется петля; параллельные ( кратные) ребра соответствуют одинаковым столбцам. [32]
При таком изображении графа дуги-ребра ( отрезки-ребра) могут пересекаться в точках, отличных от точек-вершин. Обычно эти пересечения ребер игнорируются как ничего не интерпретирующие в структуре исходного графа. Но если нас интересует наименьшее допустимое число реберных пересечений при изображении графа, то возникают весьма тонкие и сложные проблемы. [33]
Это справедливо для любых инцидентных матриц, поскольку каждое ребро инцидентно двум вершинам. Пользуясь этим свойством, можно легко построить граф цепи по его матрице инциденций. При этом следует - учитывать, что расположение вершин при изображении графа является произвольным и может не соответствовать привычному изображению электрической цепи. [34]
Значения элементов, отличные от нуля, будут обозначать вес связи. Например, вес может быть равен вероятности перехода из одной вершины в другую или длительности работы при переходе из одного состояния в другое. В тех случаях, когда всем ненулевым элементам присваивается значение единицы, матрица будет обозначать наличие дуги независимо от ее веса. Изображение графа в виде матрицы А позволяет использовать аппарат матричного исчисления для выявления свойств графов. [35]
Мы уже отмечали, что при фактическом изображении графа имеется большая свобода в размещении вершин и в выборе формы соединяющих их дуг. Поэтому может оказаться, что один и тот же граф представляется совсем различными чертежами. Будем говорить, что два графа G и G изоморфны, если существует такое взаимно однозначное соответствие между множествами их вершин V и V, что вершины соединены ребрами в одном из графов в том и только в том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу. Для нас в дальнейшем всюду будет несущественно, какое именно изображение графа используется, так как все изоморфные графы имеют одни и те же свойства. На рис. 1.2.1 приведены примеры изоморфных графов, образованных ребрами и вершинами правильных многогранников. [36]