Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Изоморфизм графов.




Пусть G(V, Е) и G’ = (V’, Е’) – два графа. Скажем, что эти два графа изоморфны, если существует пара биективных отображений j: V ®V’, y: Е®Е’ таких, что для любого ребра е = (v1, v2)ÎЕ y(е) = (j(v1), j(v2)). Иными словами, отображение y переводит ребро, соединяющее две вершины, в ребро, соединяющее образы этих вершин при отображении j.

Изоморфными могут быть на первый взгляд непохожие друг на друга графы.

 
 

Примеры. 1

Изоморфизм этих двух графов задается отображением вершин j: xi®уi, i =1,2,3,4; ребро (хi, хj) переводится отображением y в ребро (уij). Заметим, что данные графы являются полными, то есть вместе с любыми двумя вершинами содержат единственное соединяющее их ребро. Полные графы с n вершинами обозначаются Kn. Ясно, что любые два полных графа с одинаковым количеством вершин изоморфны.

       
   

Изоморфизм этих двух графов зададим отображением вершин с помощью подстановки:

(вершина хi переходит в вершину уi расположенную под ней; ребро (хi, хk) переходит в соответствующее ребро (уj, уl), где хi переходит в уj, а хk — в уl). Как устроен этот изоморфизм ясно: семиугольник с вершинами х1,…,х7 переходит в ломаную, составленную из диагоналей семиугольника с вершинами у,…,у; наоборот — диагонали семиугольника слева переходят в стороны семиугольника справа.

 
 

Ясно, что у изоморфных графов должно быть одинаковое число вершин и ребер. Однако этого условия не достаточно для изоморфизма. Пусть, например, последовательность ребер образует цикл, то есть конец каждого предыдущего ребра является началом последующего и конец последнего ребра совпадает с началом первого; число ребер последовательности называется длиной цикла (точные определения см. в § 5). Очевидно, при изоморфизме цикл переходит в цикл той же длины. Значит, у изоморфных графов должно быть одинаковое число циклов определенной длины. Следующие два графа

неизоморфны, так как у одного из них два цикла длины 4, а у другого – один.


Поделиться:

Дата добавления: 2014-12-03; просмотров: 219; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты