double arrow

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

 
 

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

 
 

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


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


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: