Реберно изоморфные графы

Материал из WEGA
Перейти к навигации Перейти к поиску

Реберно изоморфные графы (Edge isomorphic graphs) — два графа [math]\displaystyle{ G }[/math] и [math]\displaystyle{ G' }[/math] реберно изоморфны, если существует такое взаимно однозначное соответствие между их ребрами, что если [math]\displaystyle{ e_{1} }[/math] и [math]\displaystyle{ e_{2} }[/math]смежные ребра в [math]\displaystyle{ G }[/math], то соответствующие ребра [math]\displaystyle{ e'_{1} }[/math]и [math]\displaystyle{ e'_{2} }[/math] смежны в [math]\displaystyle{ G' }[/math], и наоборот. Ясно, что любой обычный (вершинный) изоморфизм между [math]\displaystyle{ G }[/math] и [math]\displaystyle{ G' }[/math] определяет также реберный изоморфизм, но обратное, вообще говоря, не имеет места.

Литература

  • Оре О. Теория графов. — М.: Наука, 1968.