вложение графа

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