| dbo:abstract
|
- In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that:
* the endpoints of the arc associated with an edge are the points associated with the end vertices of
* no arcs include points associated with other vertices,
* two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold. Informally, an embedding of a graph into a surface is a drawing of the graph on the surface in such a way that its edges may intersect only at their endpoints. It is well known that any finite graph can be embedded in 3-dimensional Euclidean space . A planar graph is one that can be embedded in 2-dimensional Euclidean space Often, an embedding is regarded as an equivalence class (under homeomorphisms of ) of representations of the kind just described. Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding". This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "graph drawing" and "crossing number". (en)
- En teoría de grafos topológica, un embebido (o también incrustación) de un grafo en una superficie es una representación de sobre en la que sus vértices están asociados con puntos de y sus lados se asocian con arcos simples (imágenes homeomórficas de ) de , de tal forma que:
* Los extremos del arco asociado a un lado son los puntos asociados a los vértices extremos de
* Ningún arco incluye puntos asociados a otros vértices
* Dos arcos nunca se cortan en un punto interior a cualquiera de los arcos Aquí se entiende por superficie una variedad de orden compacta y conexa. De manera informal, un embebido de un gráfico en una superficie es un dibujo del gráfico en la superficie de tal manera que sus lados se intersequen solo en sus puntos extremos. Es bien sabido que cualquier gráfico finito se puede incrustar en el espacio euclídeo tridimensional . Por definición, un grafo plano es aquel que se puede incrustar en un espacio euclídeo bidimensional A menudo, un embebido se considera una clase de equivalencia (bajo homeomorfismos de ) de las representaciones del tipo que se acaba de describir. Algunos autores definen una versión más débil de la definición de "embebido de grafos" al omitir la condición de no intersección para los lados. En tales contextos, la definición más estricta se describe como embebido de grafos sin cruces. Este artículo trata solo de la definición estricta de embebido de grafos. La definición más débil se discute en los artículos "dibujo de grafos" y "número de cruce". (es)
- Вложение графа — изучаемое в рамках топологической теории графов представление графа на заданной поверхности , в котором точки ассоциируются с вершинами графа и простые дуги (гомеоморфные образы [0,1]) на поверхности ассоциируются с рёбрами графа таким образом, что:
* конечные точки дуги, ассоциированной с ребром графа , являются точками, ассоциированными с конечными вершинами этого ребра графа
* никакая дуга не содержит точки, ассоциированные с другими вершинами
* никакие две дуги не пересекаются во внутренних точках этих дуг. Здесь поверхность является компактным, связным 2-мерным многообразием. Неформально, вложение графа в поверхность является изображением графа на поверхности таким образом, что его рёбра могут пересекаться только в конечных точках. Хорошо известно, что любой конечный граф может быть вложен в трёхмерное евклидово пространство , а планарные графы могут быть вложены в двумерное евклидово пространство . Часто вложение рассматривается как класс эквивалентности (по гомеоморфизмам ) представлений описанного вида. В контексте проблематики визуализации графов рассматривают также слабую версию определения вложения графа, в которой не требуется отсутствие пересечений рёбер. Соответственно, сильное определение описывается как «вложение графа без пересечений». (ru)
- У топологічній теорії графів, вкладення (також врізання) графа у поверхню Σ — це подання графа на Σ, де точки Σ асоціюються з вершинами, а прості дуги (гомеоморфні образи [0,1]) асоціюються з ребрами таким чином, що:
* кінцеві точки дуги, які пов'язані з ребром , є точками, пов'язаними з кінцевими вершинами дуги
* ніяка дуга не містить точок, асоційованих з іншими вершинами,
* ніякі дві дуги не перетинаються у внутрішніх точках цих дуг. Тут поверхня є компактним, зв'язаним 2-многовидом. Неформально, вкладення графа в поверхню є зображенням графа на поверхні, побудоване так, що його ребра можуть перетинатися тільки в їхніх кінцевих точках. Відомо, що будь-який скінченний граф можна вкласти в 3-вимірний евклідів простір , а планарні графи можна вкласти у 2-вимірний евклідів простір . Часто вкладення розглядається, як клас еквівалентності (за гомеоморфізмами Σ) представлень описаного виду. Деякі автори дають слабшу версію визначення «вкладення графа», в якій не вимагається відсутність перетинів ребер. У цьому контексті сильніше визначення описується як «вкладення графа без перетинів». Ця стаття обговорює тільки строге визначення вкладення графа. Слабке визначення обговорюється в статтях «Візуалізація графів» і «Число схрещень». (uk)
|
| rdfs:comment
|
- In topological graph theory, an embedding (also spelled imbedding) of a graph on a surface is a representation of on in which points of are associated with vertices and simple arcs (homeomorphic images of ) are associated with edges in such a way that:
* the endpoints of the arc associated with an edge are the points associated with the end vertices of
* no arcs include points associated with other vertices,
* two arcs never intersect at a point which is interior to either of the arcs. Here a surface is a compact, connected -manifold. (en)
- En teoría de grafos topológica, un embebido (o también incrustación) de un grafo en una superficie es una representación de sobre en la que sus vértices están asociados con puntos de y sus lados se asocian con arcos simples (imágenes homeomórficas de ) de , de tal forma que:
* Los extremos del arco asociado a un lado son los puntos asociados a los vértices extremos de
* Ningún arco incluye puntos asociados a otros vértices
* Dos arcos nunca se cortan en un punto interior a cualquiera de los arcos Aquí se entiende por superficie una variedad de orden compacta y conexa. (es)
- Вложение графа — изучаемое в рамках топологической теории графов представление графа на заданной поверхности , в котором точки ассоциируются с вершинами графа и простые дуги (гомеоморфные образы [0,1]) на поверхности ассоциируются с рёбрами графа таким образом, что:
* конечные точки дуги, ассоциированной с ребром графа , являются точками, ассоциированными с конечными вершинами этого ребра графа
* никакая дуга не содержит точки, ассоциированные с другими вершинами
* никакие две дуги не пересекаются во внутренних точках этих дуг. (ru)
- У топологічній теорії графів, вкладення (також врізання) графа у поверхню Σ — це подання графа на Σ, де точки Σ асоціюються з вершинами, а прості дуги (гомеоморфні образи [0,1]) асоціюються з ребрами таким чином, що:
* кінцеві точки дуги, які пов'язані з ребром , є точками, пов'язаними з кінцевими вершинами дуги
* ніяка дуга не містить точок, асоційованих з іншими вершинами,
* ніякі дві дуги не перетинаються у внутрішніх точках цих дуг. Тут поверхня є компактним, зв'язаним 2-многовидом. (uk)
|
