| dbo:abstract
|
- In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross (this is called planar embedding), and the cycleconnects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it. Halin graphs are named after German mathematician Rudolf Halin, who studied them in 1971. The cubic Halin graphs – the ones in which each vertex touches exactly three edges – had already been studied over a century earlier by Kirkman. Halin graphs are polyhedral graphs, meaning that every Halin graph can be used to form the vertices and edges of a convex polyhedron, and the polyhedra formed from them have been called roofless polyhedra or domes. Every Halin graph has a Hamiltonian cycle through all its vertices, as well as cycles of almost all lengths up to their number of vertices. The Halin graphs can be recognized in linear time. Because Halin graphs have low treewidth, many computational problems that are hard on other kinds of planar graphs, such as finding Hamiltonian cycles, can also be solved quickly on Halin graphs. (en)
- En théorie des graphes, une branche des mathématiques, un graphe de Halin est un graphe planaire construit à partir d'un arbre en reliant toutes ses feuilles dans un cycle qui fait le tour de l'arbre de telle façon que l'arbre reste planaire. On exige de plus que l'arbre comporte au moins quatre sommets et ne comporte pas de sommets de degré 2. Les graphes de Halin graphs sont nommés d'après le mathématicien allemand Rudolf Halin qui les a étudiés en 1971, mais les graphes de Halin cubiques avaient déjà été étudiés plus d'un siècle auparavant par Thomas Kirkman. (fr)
- Граф Халіна у теорії графів є типом планарного графу, який будується з'єднанням листя дерева у цикл. Дерево повинне мати щонайменше чотири вершини, жодна з яких не має рівно двох сусідів; воно повинно бути намальовано в площині, так що жодні з його ребер не перетинаються (це називається плоским вкладенням), і цикл з'єднує листки за годинниковою стрілкою у цьому вкладенні. Таким чином, цикл утворює зовнішню грань графа Халіна, яка містить дерево всередині. Графи Халіна названі на честь німецького математика , який вивчав їх у 1971 році, але кубічні графи Халіна — ті, в яких кожна вершина з'єднує рівно три ребра — вже більш ніж століття тому досліджувались . Вони є багатогранними графами, що означає, що кожен граф Халіна може бути використаний для утворення вершин та ребер опуклих багатогранників, а багатогранники, утворені з них, отримали назву багатогранників без даху (англ. roofless polyhedra) або куполів (англ. domes). Кожен граф Халіна має цикл Гамільтона, що проходить через всі його вершини, а також цикли майже всіх довжин відповідно до кількості вершин. Графи Халіна можуть бути визначені за лінійний час. Оскільки графи Халіна мають невелику ширину дерева, багато обчислювальних задач, які є складними у випадку інших видів планарних графів, таких як пошук циклу Гамільтона, можуть бути швидко розв'язані на графах Халіна. (uk)
- В теории графов графом Халина называется некоторый вид планарного графа, который строится из дерева, имеющего по меньшей мере 4 вершины, ни одна из которых не имеет в точности двух соседей. Дерево рисуется на плоскости так, что никакие рёбра не пересекаются, затем добавляются рёбра, соединяющие все его листья в цикл. Графы Халина названы по имени немецкого математика Рудольфа Халина, изучавшего их в 1971 году, но кубические графы Халина изучались за столетие до этого английским математиком Томасом Киркманом. (ru)
|
| rdfs:comment
|
- En théorie des graphes, une branche des mathématiques, un graphe de Halin est un graphe planaire construit à partir d'un arbre en reliant toutes ses feuilles dans un cycle qui fait le tour de l'arbre de telle façon que l'arbre reste planaire. On exige de plus que l'arbre comporte au moins quatre sommets et ne comporte pas de sommets de degré 2. Les graphes de Halin graphs sont nommés d'après le mathématicien allemand Rudolf Halin qui les a étudiés en 1971, mais les graphes de Halin cubiques avaient déjà été étudiés plus d'un siècle auparavant par Thomas Kirkman. (fr)
- В теории графов графом Халина называется некоторый вид планарного графа, который строится из дерева, имеющего по меньшей мере 4 вершины, ни одна из которых не имеет в точности двух соседей. Дерево рисуется на плоскости так, что никакие рёбра не пересекаются, затем добавляются рёбра, соединяющие все его листья в цикл. Графы Халина названы по имени немецкого математика Рудольфа Халина, изучавшего их в 1971 году, но кубические графы Халина изучались за столетие до этого английским математиком Томасом Киркманом. (ru)
- In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle.The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross (this is called planar embedding), and the cycleconnects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it. (en)
- Граф Халіна у теорії графів є типом планарного графу, який будується з'єднанням листя дерева у цикл. Дерево повинне мати щонайменше чотири вершини, жодна з яких не має рівно двох сусідів; воно повинно бути намальовано в площині, так що жодні з його ребер не перетинаються (це називається плоским вкладенням), і цикл з'єднує листки за годинниковою стрілкою у цьому вкладенні. Таким чином, цикл утворює зовнішню грань графа Халіна, яка містить дерево всередині. (uk)
|
