Гомеоморфизм графов

Гомеоморфи́зм гра́фов, отношение эквивалентности на множестве графов, характеризующее их геометрические свойства. Гомеоморфизм графов определяется следующим образом. Подразбиением ребра ${\displaystyle (a,b)}$ графа ${\displaystyle G}$ называется операция, состоящая в добавлении новой вершины ${\displaystyle v}$, удалении ребра ${\displaystyle (a,b)}$ и добавлении двух рёбер ${\displaystyle (a,v)}$ и ${\displaystyle (b,v)}$. Геометрически эта операция состоит в выделении на линии ${\displaystyle (a,b)}$ некоторой (внутренней) точки ${\displaystyle v}$, которая объявляется новой вершиной. Граф ${\displaystyle G'}$ называется подразбиением графа ${\displaystyle G}$, если он может быть получен из ${\displaystyle G}$ путём применения некоторого числа раз операции подразбиения рёбер. Графы ${\displaystyle G_{1}}$ и ${\displaystyle G_{2}}$ называются гомеоморфными, если существуют такие их подразбиения, которые изоморфны (см. Изоморфизм графов).