Геометрическая реализация графов
1.1. Геометрическая реализация графов
Фигура F называется геометрической реализацией графа G(V,E), если существует взаимно однозначное соответствие между точками фигуры F и вершинами графа, между кривыми фигуры и ребрами, такое, что соответствующие кривые и ребра соединяют соответствующие точки и вершины.
Правильная укладка – это реализация графа, при которой разным вершинам соответствуют разные точки, а кривые, соответствующие ребрам, не проходят через точки (исключая концевые) и не пере ссекаются.
Теорема: каждый конечный граф допускает правильную укладку в трехмерном пространстве.
Граф называет планарным, если он допускает правильную укладку на плоскости.
Теорема (доказано в топологии): граф планарен, если он не имеет подграфов, изоморфных графам K5 и K3,3.