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

Два графа G₁=<V₁, U₁> и G₂=<V₂, U₂> называются изоморфными, если существуют взаимно –однозначные отображения : V₁ V₂ и : U₁  U₂ такие, что сохраняются отношения инцидентности и ориентации, то есть, если u_k=(v_i,v_j), в графе G₁,то  (u_k )=(  (v_i ), (v_j )) в графе G₂:

{v_i, v_j } U₁  {( v_i), (v_j)} U₂

Рис 1.25

На рис. 1.25: графы G₁ и G₂ – изоморфны, а граф G₃ – не изоморфен G₁ и G₂. То есть два графа являются изоморфными, если они совпадают с точностью до нумерации вершин. По конфигурации изоморфные графы могут существенно отличаться, но у них сохраняются связи между вершинами. Матрицы I и S задают графы с точность до изоморфизма. Чтобы определить, задают ли матрицы смежности изоморфные графы, можно провести всевозможные перестановки строк и столбцов. Если после какой-либо перестановки матрицы S окажутся тождественными, то соответствующие графы изоморфны. Однако чтобы убедиться таким способом в неизоморфности графов, нужно сделать n! перестановок, что весьма трудоёмко.

Изомофизм является отношением эквивалентности на множестве графов.