| dbo:abstract
|
- En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla). Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K₅ i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals. En canvi, el graf complet K₄ és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior. Per poder comprovar la planaritat d'un graf, primer s'ha d'adequar a una sèrie de criteris bàsics:
* El graf és connex. Si tenim un graf inconnex, podem considerar cada part com a graf connex independent.
* No té cap vèrtex de grau 1. Si conté vèrtexs de grau 1, per tant amb una sola aresta, aquests es poden eliminar de l'estructura sense risc a modificar-ne la planaritat. (ca)
- Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží. (cs)
- في المخططات، المخطّط المستوي هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط. (ar)
- Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden. (de)
- Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs. (fr)
- En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos. Todo grafo plano puede ser dibujado sobre la esfera, y viceversa. Una generalización de los grafos planos son grafos dibujados e incrustados sobre superficies de género arbitrario. En esta terminología, los grafos planos tienen género 0, por ser el plano y la esfera de género 0. (es)
- In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. Every graph that can be drawn on a plane can be drawn on the sphere as well, and vice versa, by means of stereographic projection. Plane graphs can be encoded by combinatorial maps or rotation systems. An equivalence class of topologically equivalent drawings on the sphere, usually with additional assumptions such as the absence of isthmuses, is called a planar map. Although a plane graph has an external or unbounded face, none of the faces of a planar map has a particular status. Planar graphs generalize to graphs drawable on a surface of a given genus. In this terminology, planar graphs have genus 0, since the plane (and the sphere) are surfaces of genus 0. See "graph embedding" for other related topics. (en)
- 평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다. 예를 들어 다음의 그래프는 모두 평면 그래프이다.
* 평면 그래프의 예
*
* 이 그림 상에서는 두 변이 만나지만, 만나지 않도록 그릴 수 있다.
* 앞의 그래프와 같은 그래프이다. 한편 아래 그래프는 평면 그래프가 아니다.
* 평면 그래프가 아닌 그래프의 예
* 꼭짓점이 5개인 완전 그래프
* 꼭짓점이 3개씩인 완전 이분 그래프
* 페테르센 그래프 엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다. (ko)
- Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano. Ad esempio sono planari i seguenti grafi: Il secondo può essere raffigurato senza archi che si intersecano spostando uno degli archi dati da una diagonale al di fuori del perimetro del quadrato. Vi sono invece grafi che posseggono solo raffigurazioni piane nelle quali si hanno coppie di archi che si intersecano. Le due seguenti figure forniscono raffigurazioni di due grafi non planari: K5 K3,3 Si tratta del grafo completo con 5 nodi e del grafo bipartito completo con 3+3 nodi ; questi due grafi sono chiamati anche grafi di Kuratowski, in onore del matematico polacco Kazimierz Kuratowski. Si constata infatti che non è possibile ridisegnare queste raffigurazioni evitando che gli archi si intersechino. In effetti Kuratowski nel 1929 ha dimostrato che questi sono i due grafi non planari più ridotti, con il seguente enunciato. (it)
- 平面グラフ（へいめんグラフ、英: plane graph）は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフである。平面グラフと同型なグラフを平面的グラフ (planar graph) という。平面的グラフであっても、描き方によっては平面グラフにならない。 平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。極小な非平面的グラフは、K3,3とK5である。 (ja)
- Em Teoria dos Grafos, um grafo planar é um grafo que pode ser imerso no plano de tal forma que suas arestas não se cruzem, esta é uma idealização abstrata de um grafo plano, um grafo plano é um grafo planar que foi desenhado no plano sem o cruzamento de arestas. Aparentemente o estudo da planaridade de um grafo é uma questão topológica que se baseia em resultados como o Teorema da Curva de Jordan que de forma simplificada diz que uma curva fechada simples no plano divide-o em duas partes, apesar deste ser um critério muito importante, é natural o questionamento se há algum resultado combinatório que caracterize um grafo plano. Observe os dois exemplos, ambos isomorfos entre si, ambos planares, porém apenas o que é desenhado sem cruzamento de arestas é um grafo plano. (pt)
- Graf planarny – graf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim. (pl)
- Inom grafteori är en planär graf en graf som kan i planet, det vill säga ritas på planet på ett sådant sätt att kanterna inte skär varandra, utan bara möts i noderna. En sådan avbildning kallas en plan graf eller planär inbäddning av grafen. En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna. Varje graf som kan avbildas på ett plan kan avbildas på en sfär och vice versa. En generalisering av planära grafer är grafer som kan ritas på en yta av ett givet genus. Med denna terminologi har planära grafer grafgenus 0, eftersom planet (och sfären) har genus 0. (sv)
- Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых. (ru)
- Планарний граф — граф, який може бути зображений на площині без перетину ребер. Граф зображений на площині називається плоским, якщо його ребра не перетинаються. Граф називається планарним, якщо він ізоморфний деякому плоскому графу. Тобто існує відображення вершин графа на деякі точки площини і ребер графа на прості криві у площині, так що кінцями кривих є точки, що відповідають вершинам ребра і дві різні криві не мають спільних точок, окрім можливо кінцевих. (uk)
- 在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3（湯瑪森圖）是最“小”的非平面图。 一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。 藉由球极投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在關係中的等價類稱為平面映射。注意到一個平版圖會有外圍面，又稱無界面，但因為平面映射定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。 平面圖可以被視為一個。 (zh)
|
| rdfs:comment
|
- Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží. (cs)
- في المخططات، المخطّط المستوي هو المخطّط الذي يقبل تمثيلا في المستوى، بحيث لا يتقاطع أي حرفين من المخطّط. (ar)
- Ein planarer oder plättbarer Graph ist in der Graphentheorie ein Graph, der auf einer Ebene, mit Punkten für die Knoten und Linien für die Kanten, dargestellt werden kann, sodass sich keine Kanten schneiden. (de)
- Dans la théorie des graphes, un graphe planaire est un graphe qui a la particularité de pouvoir se représenter sur un plan sans qu'aucune arête (ou arc pour un graphe orienté) n'en croise une autre. Autrement dit, ces graphes sont précisément ceux que l'on peut plonger dans le plan, ou encore les graphes dont le nombre de croisements est nul. Les méthodes associées à ces graphes permettent de résoudre des problèmes comme l'énigme des trois maisons et d'autres plus difficiles comme le théorème des quatre couleurs. (fr)
- 평면 그래프(planar graph)는 평면 상에 그래프를 그렸을 때, 두 변이 꼭짓점 이외에 만나지 않도록 그릴 수 있는 그래프를 의미한다. 예를 들어 다음의 그래프는 모두 평면 그래프이다.
* 평면 그래프의 예
*
* 이 그림 상에서는 두 변이 만나지만, 만나지 않도록 그릴 수 있다.
* 앞의 그래프와 같은 그래프이다. 한편 아래 그래프는 평면 그래프가 아니다.
* 평면 그래프가 아닌 그래프의 예
* 꼭짓점이 5개인 완전 그래프
* 꼭짓점이 3개씩인 완전 이분 그래프
* 페테르센 그래프 엄밀하게 정의하면, 평면 그래프는 평면에 그래프 임베딩이 가능한 그래프를 의미한다. (ko)
- 平面グラフ（へいめんグラフ、英: plane graph）は、平面上の頂点集合とそれを交差なく結ぶ辺集合からなるグラフである。平面グラフと同型なグラフを平面的グラフ (planar graph) という。平面的グラフであっても、描き方によっては平面グラフにならない。 平面的グラフは、球面などの種数0の曲面に描けるグラフと同値である。極小な非平面的グラフは、K3,3とK5である。 (ja)
- Graf planarny – graf, który można narysować na płaszczyźnie (i każdej powierzchni genusu 0) tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim. Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim. (pl)
- Плана́рный граф — граф, который можно изобразить на плоскости без пересечений рёбер не по вершинам. Какое-либо конкретное изображение планарного графа на плоскости без пересечения рёбер не по вершинам называется плоским графом. Иначе говоря, планарный граф изоморфен некоторому плоскому графу, изображённому на плоскости так, что его вершины — это точки плоскости, а рёбра — кривые на плоскости, которые если и пересекаются между собой, то только по вершинам. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, называемая внешней гранью. Любой плоский граф может быть спрямлён, то есть перерисован на плоскости так, что все его рёбра будут отрезками прямых. (ru)
- Планарний граф — граф, який може бути зображений на площині без перетину ребер. Граф зображений на площині називається плоским, якщо його ребра не перетинаються. Граф називається планарним, якщо він ізоморфний деякому плоскому графу. Тобто існує відображення вершин графа на деякі точки площини і ребер графа на прості криві у площині, так що кінцями кривих є точки, що відповідають вершинам ребра і дві різні криві не мають спільних точок, окрім можливо кінцевих. (uk)
- 在圖論中，平面圖是可以画在平面上并且使得不同的邊可以互不交疊的圖。而如果一个图无论怎样都无法画在平面上，并使得不同的边互不交叠，那么这样的图不是平面图，或者称为非平面图。完全图 K5和完全二分图 K3,3（湯瑪森圖）是最“小”的非平面图。 一個將平面圖畫在平面上的方法稱為平版圖，又稱為圖的平面嵌入，更精確地說，平版圖包含一個平面圖與一個映射，此映射將平面圖的頂點對應到平面上的一點，邊對應到一條平面曲线段，滿足邊兩端點對應到線段的兩端點，並且線段之間除了在端點之外都不相交。 藉由球极投影可知一個圖可以被嵌入平面若且唯若可以被嵌入球面。圖的球面嵌入在關係中的等價類稱為平面映射。注意到一個平版圖會有外圍面，又稱無界面，但因為平面映射定義是在球面上的等價類，不會有任何一個面有這個特殊的地位。 平面圖可以被視為一個。 (zh)
- En teoria de grafs, un graf pla o planar és un graf que pot ser dibuixat en un pla sense que les arestes s'intersequin (o utilitzant una definició més formal, que aquest graf pugui ser "embegut" en un pla). Un graf no és pla si no pot ser dibuixat sobre un pla sense que les seves arestes s'intersequin. Hi ha dos grafs no plans minimals; K₅ i K3,3. Tots els grafs no plans contenen almenys un d'aquests subgrafs minimals. En canvi, el graf complet K₄ és pla, perquè pot ser redibuixat sense que les arestes es creuin, passant una de les diagonals per l'exterior. (ca)
- En teoría de grafos, un grafo plano (o planar según referencias) es un grafo que puede ser dibujado en el plano sin que ninguna arista se cruce (una definición más formal puede ser que este grafo pueda ser "incrustado" en un plano). Los grafos K5 y el K3,3 son los grafos no planos minimales, lo cual nos permitirán caracterizar el resto de los grafos no planos. (es)
- In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points. (en)
- Nella teoria dei grafi si definisce grafo planare un grafo che può essere raffigurato in un piano in modo che non si abbiano archi che si intersecano. Ad esempio sono planari i seguenti grafi: Il secondo può essere raffigurato senza archi che si intersecano spostando uno degli archi dati da una diagonale al di fuori del perimetro del quadrato. Vi sono invece grafi che posseggono solo raffigurazioni piane nelle quali si hanno coppie di archi che si intersecano. Le due seguenti figure forniscono raffigurazioni di due grafi non planari: K5 K3,3 (it)
- Inom grafteori är en planär graf en graf som kan i planet, det vill säga ritas på planet på ett sådant sätt att kanterna inte skär varandra, utan bara möts i noderna. En sådan avbildning kallas en plan graf eller planär inbäddning av grafen. En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna. Varje graf som kan avbildas på ett plan kan avbildas på en sfär och vice versa. (sv)
- Em Teoria dos Grafos, um grafo planar é um grafo que pode ser imerso no plano de tal forma que suas arestas não se cruzem, esta é uma idealização abstrata de um grafo plano, um grafo plano é um grafo planar que foi desenhado no plano sem o cruzamento de arestas. Observe os dois exemplos, ambos isomorfos entre si, ambos planares, porém apenas o que é desenhado sem cruzamento de arestas é um grafo plano. (pt)
|
