8

Теория графов

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

Определение. Неориентированные графы G = (V ; E) и G0 = (V 0; E0) изоморфны, если существуют биективные отображения f : V ! V 0 и g : E ! E0 такие, что

e 2 E инцидентна a 2 V () g(e) 2 E0 инцидентна f (a) 2 V 0:

Для случая простых графов для изоморфизма достаточно существования биективного отображения f : V ! V 0 такого, что

a; b 2 V смежные () f (a); f (b) 2 V 0 смежные:

Для изоморфных графов G и G0 имеем deg(a) = deg(f (a)).