6.1.5 Изоморфизм графов

их ребрами можно установить взаимно однозначное соответствие X $ X0; U $ U0, сохраняющее инцидентор P ,

то есть

8x; y 2 X 8x0; y0 2 X0 8u 2 U 8u0 2 U0 fx $ x0 & y $ y0 & u $ u0 )

) [P (x; u; y) , P 0(x0; u0; y0)]g.

Здесь $ обозначает взаимно-однозначное соответствие, ) – логическое следствие, , – логическую эквивалентность.

Отношение изоморфизма рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности.

В дальнейшем нас будут интересовать в основном такие свойства графов, которые сохраняются при замене графа изоморфным ему графом. Тем самым оказываются несущественными как сама природа элементов, составляющих множества X и U, так и конкретный смысл предиката P . Но даже при таком абстрактном изучении графов требуется индивидуализация элементов. Поэтому всегда предполагается, что вершины и ребра графа либо сами являются определенными объектами (буквами, числами и т.п.), либо помечены различными индексами из каких-либо индексных множеств (обозначены буквами или пронумерованы). При этом два графа, отличающиеся лишь индексацией элементов, рассматриваются как изоморфные, но не как тождественные.

Пример 6.5.