Математическая энциклопедия - графов изоморфизм
Связанные словари
Графов изоморфизм
отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой наз. взаимно однозначное отображение вершин и ребер одного графа соответственно на вершиныи ребра другого графа, при к-ром сохраняется отношение инцидентности. Два графа наз. изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы 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
Вопрос-ответ:
Похожие слова
Самые популярные термины
1 | 557 | |
2 | 483 | |
3 | 480 | |
4 | 472 | |
5 | 454 | |
6 | 440 | |
7 | 437 | |
8 | 433 | |
9 | 424 | |
10 | 423 | |
11 | 422 | |
12 | 413 | |
13 | 406 | |
14 | 375 | |
15 | 375 | |
16 | 372 | |
17 | 365 | |
18 | 364 | |
19 | 364 | |
20 | 362 |