|
"
0
C
F
G
H
K
L
N
P
S
T
W
Z
А
Б
В
Г
Д
Е
Ж
З
И
Й
К
Л
М
Н
О
П
Р
С
Т
У
Ф
Х
Ц
Ч
Ш
Э
Ю
Я
ГРАФОВ ИЗОМОРФИЗМЗначение ГРАФОВ ИЗОМОРФИЗМ в математической энциклопедии: - отношение эквивалентности на множестве графов. Изоморфным отображением одного неориентированного графа на другой наз. взаимно однозначное отображение вершин и ребер одного графа соответственно на вершиныи ребра другого графа, при к-ром сохраняется отношение инцидентности. Два графа наз. изоморфными, если существует изоморфное отображение одного из этих графов на другой. Графы G1 и G2, представленные на рис., не изоморфны, a G1 и G3 изоморфны. Обычно изоморфные графы не различают. Число попарно неизоморфных графов с данным числом вершин и данным числом ребер конечно. Подобным образом можно определить изоморфизм ориентированных графов, гиперграфов и сетей.
Проблема установления Г. и. является важной проблемой теории графов. Для нек-рых классов графов имеются алгоритмы, позволяющие установить изоморфизм достаточно эффективно (напр., для деревьев или плоских графов, см. [1]). Для нек-рых классов графов с пвершинами доказана однозначная (с точностью до изоморфизма) восстанавливаемость графа по набору всех его Лит.:[1] Хопкрофт Дж., Тарьян Р., "Кибернетический сборник", 1975, в. 12, с. 39-61; [2] Kelly P. J., "Pacific J. Math.", 1957, v. 7, p. 961-68. В. Б. Алексеев. |
|
|
|
-вершин ных подграфов 
, получаемых удалением всевозможных вершин 
. Это установлено, в частности, для деревьев и турниров (при 
).