Вложение графа
Материал из Википедии — свободной encyclopedia
Вложение графа — изучаемое в рамках топологической теории графов представление графа на заданной поверхности
, в котором точки
ассоциируются с вершинами графа и простые дуги (гомеоморфные образы [0,1]) на поверхности ассоциируются с рёбрами графа таким образом, что:
- конечные точки дуги, ассоциированной с ребром графа
, являются точками, ассоциированными с конечными вершинами этого ребра графа
- никакая дуга не содержит точки, ассоциированные с другими вершинами
- никакие две дуги не пересекаются во внутренних точках этих дуг.
Здесь поверхность является компактным, связным 2-мерным многообразием.
Неформально, вложение графа в поверхность является изображением графа на поверхности таким образом, что его рёбра могут пересекаться только в конечных точках. Хорошо известно, что любой конечный граф может быть вложен в трёхмерное евклидово пространство [1], а планарные графы могут быть вложены в двумерное евклидово пространство
.
Часто вложение рассматривается как класс эквивалентности (по гомеоморфизмам ) представлений описанного вида.
В контексте проблематики визуализации графов рассматривают также слабую версию определения вложения графа, в которой не требуется отсутствие пересечений рёбер. Соответственно, сильное определение описывается как «вложение графа без пересечений»[2].