В изображении графа имеется относительно большая свобода в размещении вершин и в выборе формы соединяющих их ребер. Поэтому один и тот же граф может быть представлен по-разному (рис. 3.16).
Рис. 3.16. Примеры изоморфных графов
Графы G1(X1) и G2(X2) называются изоморфными, если между множествами их вершин существует взаимно однозначное соответствие, сохраняющее смежность вершин. Иначе, если вершины являются смежными (соединены ребрами) в одном из графов, то соответствующие им вершины в другом графе также являются смежными. Если ребра графов ориентированы, то их направление в изоморфных графах также должно соответствовать друг другу.
Граф G(X) называется плоским, если он может быть изображен на плоскости так, что все пересечения его ребер являются вершинами графа G(X) (рис. 3.17).
а) б)
Рис. 3.17. Примеры плоского (а) и неплоского (б) графов
