ГРАФОВ ИЗОМОРФИЗМ

ГРАФОВ ИЗОМОРФИЗМ

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


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

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Игры ⚽ Поможем сделать НИР

Полезное


Смотреть что такое "ГРАФОВ ИЗОМОРФИЗМ" в других словарях:

  • ГРАФОВ ГОМЕОМОРФИЗМ — отношение эквивалентности на множестве графов, характеризующее их геометрия, свойства. Г. г. определяется следуюпшм образом. Подразбиением ребра ( а, b).графа Gназ. операция, состоящая в добавлении новой вершины v, удалении ребра (а, b).и… …   Математическая энциклопедия

  • Изоморфизм графов — В теории графов изоморфизмом графов и называется биекция между множествами вершин графов такая, что любые две вершины и графа смежны, тогда и только тогда, когда вершины …   Википедия

  • Изоморфизм — У этого термина существуют и другие значения, см. Изоморфизм (значения). Изоморфизм (от др. греч. ἴσος «равный, одинаковый, подобный» и μορφή «форма»)  это очень общее понятие, которое употребляется в различных разделах математики. В общих… …   Википедия

  • Изоморфизм (математика) — Изоморфизм  это очень общее понятие, которое употребляется в различных разделах математики. В общих чертах его можно описать так: Пусть даны два множества с определённой структурой (группы, кольца, линейные пространства и т. п.). Биекция между… …   Википедия

  • Изоморфизм (матем.) — Изоморфизм  это очень общее понятие, которое употребляется в различных разделах математики. В общих чертах его можно описать так: Пусть даны два множества с определённой структурой (группы, кольца, линейные пространства и т. п.). Биекция между… …   Википедия

  • Теория графов и мографов — Теорема 3.27. замена любого ребра (a, b)in Gкритического графа G на k вершинно непересекающихся простых цепей длинны 3 тогда и только тогда приводят к образованию критического графа T 3(G), когда k удовлетворяет одному из следующих условий: # k=1 …   Википедия

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф …   Википедия

  • Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
… Нажмите правой клавишей мыши и выберите «Копировать ссылку»