Outerplanar graph
http://dbpedia.org/resource/Outerplanar_graph an entity of type: Software
En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un graphe G est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire.
rdf:langString
En teoría de grafos, un grafo plano exterior es un grafo que tiene una representación plana para la que todos los vértices pertenecen a la cara exterior del dibujo. Los grafos planos externos se pueden caracterizar (análogamente al teorema de Wagner para grafos planos) por los dos menores prohibidos K4 y K2,3, o por sus . Poseen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma el único ciclo hamiltoniano. Cada grafo plano externo tiene 3 colores; y y como máximo 2.
rdf:langString
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants.They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2.
rdf:langString
В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані. Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2.
rdf:langString
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани. Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера.Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырожденность и древесную ширину не больше 2.
rdf:langString
rdf:langString
Grafo plano exterior
rdf:langString
Graphe planaire extérieur
rdf:langString
Outerplanar graph
rdf:langString
Внешнепланарный граф
rdf:langString
Зовніпланарний граф
xsd:integer
352343
xsd:integer
1094649177
rdf:langString
Outplanar Graph
rdf:langString
OutplanarGraph
rdf:langString
En teoría de grafos, un grafo plano exterior es un grafo que tiene una representación plana para la que todos los vértices pertenecen a la cara exterior del dibujo. Los grafos planos externos se pueden caracterizar (análogamente al teorema de Wagner para grafos planos) por los dos menores prohibidos K4 y K2,3, o por sus . Poseen ciclos hamiltonianos si y solo si están biconectados, en cuyo caso la cara exterior forma el único ciclo hamiltoniano. Cada grafo plano externo tiene 3 colores; y y como máximo 2. Los grafos planos exteriores son un subconjunto de los grafos planos, de los subgrafos de grafos serie-paralelo y de los . Los grafos planos exteriores máximos, aquellos a los que no se les pueden añadir más aristas conservando la planaridad exterior, también son y de visibilidad.
rdf:langString
En mathématiques, et plus particulièrement en théorie des graphes, un graphe non orienté est planaire extérieur (ou, par calque de l'anglais, outer-planar) s'il peut être dessiné dans le plan sans croisements des arêtes, de telle façon que tous les sommets appartiennent à la face extérieure du tracé, autrement dit qu'aucun sommet ne soit entouré par des arêtes. On démontre qu'un graphe G est planaire extérieur si et seulement si le graphe formé en ajoutant à G un nouveau sommet et toutes les arêtes le reliant aux sommets de G est un graphe planaire.
rdf:langString
In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing. Outerplanar graphs may be characterized (analogously to Wagner's theorem for planar graphs) by the two forbidden minors K4 and K2,3, or by their Colin de Verdière graph invariants.They have Hamiltonian cycles if and only if they are biconnected, in which case the outer face forms the unique Hamiltonian cycle. Every outerplanar graph is 3-colorable, and has degeneracy and treewidth at most 2. The outerplanar graphs are a subset of the planar graphs, the subgraphs of series–parallel graphs, and the circle graphs. The maximal outerplanar graphs, those to which no more edges can be added while preserving outerplanarity, are also chordal graphs and visibility graphs.
rdf:langString
В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані. Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2. Зовніпланарні графи є підмножиною планарних графів, підграфами паралельно-послідовних графів і колових графів. Максимальний зовніпланарний граф — це граф, до якого можна додати ребро без втрати зовніпланарності. Вони також є хордальними і .
rdf:langString
В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани. Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера.Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырожденность и древесную ширину не больше 2. Внешнепланарные графы являются подмножеством планарных графов, подграфами параллельно-последовательных графов и круговых графов. Максимальный внешнепланарный граф — это граф, к которому нельзя добавить ребро без потери внешнепланарности. Они также являются хордальными и графами видимости.
xsd:nonNegativeInteger
18423
