rdfs:comment
| - 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. (fr)
- 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. (es)
- 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. (en)
- В теорії графів зовніпланарний граф — це граф, що допускає планарну діаграму, в якій усі вершини належать зовнішній грані. Зовніпланарні графи можна схарактеризувати (аналогічно теоремі Вагнера для планарних графів) двома забороненими мінорами K4 і K2,3, або їх інваріантами Колен де Вердьєра. Ці графи мають гамільтонові цикли тоді й лише тоді, коли вони двозв'язні, і в цьому випадку зовнішня грань утворює єдиний гамільтонів цикл. Будь-який зовніпланарний граф можна розфарбувати в 3 кольори і він має виродження і деревну ширину не більше 2. (uk)
- В теории графов outerplanar graph — это граф, допускающий планарную диаграмму, в которой все вершины принадлежат внешней грани. Внешнепланарные графы можно охарактеризовать (аналогично теореме Вагнера для планарных графов) двумя запрещёнными минорами K4и K2,3, или их инвариантами Колен де Вердьера.Эти графы имеют гамильтоновы циклы тогда и только тогда, когда они двусвязны, и в этом случае внешняя грань образует единственный гамильтонов цикл. Любой внешнепланарный граф раскрашиваем в 3 цвета и имеет вырожденность и древесную ширину не больше 2. (ru)
|