Элементы теории графов и их технические приложения - 8 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

8
Рис. 6
Аналогично двудольным определяются К-дольный и полный К-дольный
графы.
Поскольку в применениях теории графов существенным является то, что есть
объекты (вершины графа) и связи между объектами (ребра), граф является не
геометрической, а топологической фигурой, определенные свойства которой
инвариантны при взаимнонепрерывном и взаимнооднозначном пространственном
преобразовании. Существенные инвариантные свойства графа отражают только
число вершин, число ребер (дуг) и характер связей между вершинами. Так как граф
является топологической фигурой, то один и тот же граф может быть изображен
различными способами: вершины можно располагать в произвольном порядке, а
соединяющие их ребра проводить в виде прямых или ломаных линий, информация,
содержащаяся в графе, остается одной
и той же. Оформим эти соображения в виде
следующего определения:
Пусть G и Н – графы, а ϕ : VG →VH – биекция. Если для любых вершин u и
графа G их образы ϕ (u) и ϕ (v) смежны в Н, тогда и только тогда, когда u и v
смежны в G, то эта биекция называется изоморфизмом графа G на граф H. Иначе
говоря два
графа называют изоморфными, если они имеют одинаковое число
вершин и каждой паре вершин, соединенных ребром в одном графе, соответствует
такая же пара вершин, которые соединены ребром в другом графе. Если
существенные свойства графа не связаны со способом его изображения или
нумерацией вершин и ребер, то изоморфные графы, обычно, не различают
между
собой. Изоморфизм графов G и Н обозначают следующим образом: G
≅
Н.
Например, три графа, представленные на рис. 7 изоморфны между собой, так же как
и два графа на рис. 8, а графы на рис. 9 не изоморфны.
Рис. 7
Рис. 8 рис. 9

Страницы