Изоморфизм. Плоские графы

В изображении графа имеется относительно большая свобода в размещении вершин и в выборе формы соединяющих их ребер. По­этому один и тот же граф может быть представлен по-разному (рис. 3.16).

G2(X2)

G1(X1)

Рис. 3.16. Примеры изоморфных графов

Графы G₁(X₁) и G₂(X₂) называются изоморфными, если между множествами их вершин существует взаимно однозначное соответ­ствие, сохраняющее смежность вершин. Иначе, если вершины являются смежными (соединены ребрами) в одном из графов, то соответствующие им вершины в другом графе также являются смежными. Если ребра графов ориентированы, то их направление в изоморфных графах также должно соответствовать друг другу.

Граф G(X) называется плоским, если он может быть изобра­жен на плоскости так, что все пересечения его ребер являются вер­шинами графа G(X) (рис. 3.17).

а) б)

Рис. 3.17. Примеры плоского (а) и неплоского (б) графов