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

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

В. Б. Алексеев.

Источники:

1. Математическая Энциклопедия. Т. 1 (А - Г). Ред. коллегия: И. М. Виноградов (глав ред) [и др.] - М., «Советская Энциклопедия», 1977, 1152 стб. с илл.