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

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

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

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

2.2 Отношения на множествах и графы

Каждый ориентированный граф G(X) определяет некоторое отноше­ние на множестве X своих вершин. Это отношение может быть записано как x_iG x_j. Оно означает, что в графе есть дуга, идущая от x_i к x_j .

Отношению со свойством рефлексивности (x R x) должна соответ­ствовать на графе петля в вершине. Если это отношение соблюдается во всех вершинах x  X, то соответствующий граф G(X) должен иметь петлю в каждой своей вершине. В случае антирефлексивного отношения на множестве X, соответствующий граф ни в одной из вершин не имеет пет­ли.

Симметрическому отношению на множестве X соответствует граф с неориентированными ребрами и наоборот граф с неориентированными ребрами определяет некоторое симметрическое отношение. В случае ан­тисимметрического отношения на графе невозможно присутствие двух дуг (x_i, x_j), (x_j, x_i) на графе, то есть существование неориентированного ребра. Кроме того, на этих графах нет петель, то есть соответствующее антисимметрическое отношение антирефлексивно.

Отношение, обладающее свойством тождественности, соответствует графу с антисимметричным отношением на множестве вершин (ориенти­рованному графу) и добавлением петли в каждой вершине. Этот граф не должен иметь контуров.

Граф, соответствующийтранзи­тивному отношению (рис.2.18), обла­дает следующими свойствами: для лю­бой пары ориентированных ребер (дуг) графа (x_i, x_j),(x_j, x_k) имеется замыкаю­щая дуга (x_i, x_k). Можно сказать, что в графе, который соответствует транзи­тивному отношению, для каждого пути S(x_i, x_k) имеется дуга (x_i, x_k) (рис.2.19).

Отношение, обладающее свойством полноты, определено на множе­стве вершин полного ориентированного графа.

Нулевоеотношение определено на множестве вершин ноль-графа.

Универсальноеотношение определено на множестве вершин пол­ного неориентированного графа с петлями.

Дополнительное к R отношениеR определено на множестве вер­шин дополнительного G_k(X)графа к графу G(X).

Графы, соответствующие отношениюэквивалентности, представ­ляют собой совокупность компонент связности (для каждого класса экви­валентности своя компонента) несвязного графа. Каждая компонента не­связного графа должна быть полным неориентированным графом с пет­лями (рис. 2.20).

При рассмотрении отношенияквазипорядка соответствующий граф должен иметь петли в каждой вершине и может иметь неориентирован­ные и ориентированные ребра. В отличие от предыдущего случая здесь не соблюдается свойство симметричности (рис. 2.21, а, б, в).

Граф, на множестве вершин которого определено отношение эквива­лентности, одновременно является графом, на множестве вершин которо­го определено отношение квазипорядка.

Граф, на множестве вершин которого определено отношение поряд­­ка, является также графом, на множестве вершин которого определено отношение квазипорядка. Этот граф:

• имеет петли во всех вершинах;

• для каждого пути S(x_i, x_k) должен иметь замыкающую дугу (x_i, x_k);

• не должен иметь контуров и все ребра должны быть ориентиро­ваны (рис. 2.21, в).

Граф, на множестве вершин которого определено отношение стро­гого порядка, получается удалением всех петель в графе, на множестве вершин которого определено отношение порядка.

Отношение полного порядка соответствует каждой компоненте связности графа, на множестве вершин которого определено отношение порядка.

Если на графе G(X) определено одно из отношений эквивалентности, квазипорядка, порядка, строгого порядка, полного порядка, нулевое, универсальное, дополнительное, то данное отношение сохраняется и на графе G^-1(X).