Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



Два графа G1 = <V1, E1> и G2 = <V2, E2> изоморфны ( G1 ~ G2) если существует биекция φ: V1 → V2 сохраняющие смежность

е1 = (u,v) E1 е2 = (φ (u), φ (v)) E2

Теорема. Изоморфизм графов есть отношение эквивалентности.

Графы G = <V, E>, G ' = < V ', E ' > изоморфны, если существует такое взаимно однозначное отображение f из V на V ', что для произвольных имеем ( в случае ориентированных графов). Обычно изоморфные графы не различаются между собой.





Дата публикования: 2014-11-04; Прочитано: 266 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...