ЧЕРКАССЫ  ИНФОРМАЦИОННО-СПРАВОЧНЫЙ ПОРТАЛ ГОРОДА И ОБЛАСТИ   ГЛАВНАЯ         ВХОД          РЕГИСТРАЦИЯ        КАРТА САЙТА   
Энциклопедии и справочники

Математическая энциклопедия
ГРАФОВ ИЗОМОРФИЗМ

- отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой наз. взаимно однозначное отображение вершин и ребер одного графа соответственно на вершиныи ребра другого графа, при к-ром сохраняется отношение инцидентности. Два графа наз. изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы G1 и G2, представленные на рис., не изоморфны, a G1 и G3 изоморфны. Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом ребер конечно. Подобным образом можно определить изоморфизм ориентированных графов, гиперграфов и сетей.


Проблема установления Г. и. является важной проблемой теории графов. Для нек-рых классов графов имеются алгоритмы, позволяющие установить изоморфизм достаточно эффективно (напр., для деревьев или плоских графов, см. [1]). Для нек-рых классов графов с пвершинами доказана однозначная (с точностью до изоморфизма) восстанавливаемость графа по набору всех его -вершин ных подграфов , получаемых удалением всевозможных вершин . Это установлено, в частности, для деревьев и турниров (при ).

Лит.:[1] Хопкрофт Дж., Тарьян Р., "Кибернетический сборник", 1975, в. 12, с. 39-61; [2] Kelly P. J., "Pacific J. Math.", 1957, v. 7, p. 961-68. В. Б. Алексеев.



Наверх

Ротатор баннеров 468x60

Баннеров в ротаторе: 0   Смотреть все   Добавить баннер
 

 
Добавить баннер

Добавить баннер       Партнерка для Вашего сайта



Ротатор баннеров 88x31

Баннеров в ротаторе: 0   Смотреть все   Добавить баннер