| dbo:abstract
|
- Ein Einheitsdistanz-Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist.Kanten eines Einheitsdistanz-Graphen dürfen sich überschneiden, d. h. der Graph muss nicht immer planar sein. Ein Einheitsdistanz-Graph ohne Überschneidungen wird Streichholzgraph genannt. Das Problem von Hadwiger und Nelson beschäftigt sich mit der chromatischen Zahl des Graphen. Jeder Einheitsdistanz-Graph kann mit höchstens sieben Farben eingefärbt werden, bekanntlich existieren aber auch einige Graphen, die mindestens vier Farben benötigen. Ein anderes bekanntes offenes Problem befasst sich mit der Frage, wie hoch das Verhältnis von Kanten- zu Knotenanzahl sein kann. (de)
- En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette. (fr)
- In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs. An unsolved problem of Paul Erdős asks how many edges a unit distance graph on vertices can have. The best known lower bound is slightly above linear in —far from the upper bound, proportional to . The number of colors required to color unit distance graphs is also unknown (the Hadwiger–Nelson problem): some unit distance graphs require five colors, and every unit distance graph can be colored with seven colors. For every algebraic number there is a unit distance graph with two vertices that must be that distance apart. According to the Beckman–Quarles theorem, the only plane transformations that preserve all unit distance graphs are the isometries. It is possible to construct a unit distance graph efficiently, given its points. Finding all unit distances has applications in pattern matching, where it can be a first step in finding congruent copies of larger patterns. However, determining whether a given graph can be represented as a unit distance graph is NP-hard, and more specifically complete for the existential theory of the reals. (en)
- 単位距離グラフとは、グラフ理論のグラフの一種であり、ユークリッド平面上に、すべての辺の長さを単位長さとして描画できるグラフである。辺同士が交差してもよい（その場合平面グラフではなくなる）。平面グラフでもある単位距離グラフは、と呼ばれる。 は、単位距離グラフの彩色数についての問題である。彩色数が5である単位距離グラフが存在する一方、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の次数の上限はいくつか？がある。 (ja)
- В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом. Проблема Нелсона — Эрдёша — Хадвигера касается хроматического числа графов единичных расстояний. Известно, что существуют графы единичных расстояний, требующие 5 цветов для правильной раскраски и что все такие графы можно раскрасить не более чем в 7 цветов. Другая важная открытая задача, касающаяся графов единичных расстояний, спрашивает, сколько рёбер может иметь такой граф по отношению к числу вершин. (ru)
- Графом одиничних відстаней у теорії графів називається граф, утворений точками на евклідовій площині, у якому ребрами з'єднані кожні дві вершини, відстань між якими дорівнює точно одиниці. Ребра графів одиничних відстаней іноді перетинаються, тож графи одиничних відстаней не завжди планарні. Граф одиничних відстаней без перетинів називається сірниковим графом. Проблема Нельсона — Ердеша — Гадвігера стосується хроматичного числа графів одиничних відстаней. Відомо, що існують графи одиничних відстаней, що вимагають 4 кольори для правильного розфарбування і що всі такі графи можна розфарбувати не більш ніж у 7 кольорів. Інше важливе відкрите питання стосовно графів одиничних відстаней звучить так: «скільки ребер може мати такий граф відносно числа вершин?». (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 33229 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:authorlink
| |
| dbp:caption
|
- The Petersen graph as a unit distance graph (en)
- The Möbius–Kantor graph as a subgraph of a unit distance graph (en)
- The Hamming graph has 27 vertices and 81 unit distances (en)
- The hypercube graph has 16 vertices and 32 unit distances (en)
|
| dbp:first
| |
| dbp:image
|
- Hamming33UnitDistance.gif (en)
- Hypercubestar.svg (en)
- Möbius–Kantor unit distance.svg (en)
- Petersen graph, unit distance.svg (en)
|
| dbp:last
| |
| dbp:mode
| |
| dbp:title
| |
| dbp:totalWidth
|
- 400 (xsd:integer)
- 480 (xsd:integer)
|
| dbp:urlname
| |
| dbp:wikiPageUsesTemplate
| |
| dbp:year
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- En mathématiques, plus particulièrement en théorie des graphes, un graphe distance-unité est un graphe s'obtenant à partir d'un ensemble de points du plan euclidien en reliant par une arête toutes les paires de points étant à une distance de 1. Les arêtes peuvent se croiser si bien qu'un graphe distance-unité n'est pas nécessairement un graphe planaire. S'il n'y a pas de croisement entre les arêtes, alors le graphe est qualifié de graphe allumette. (fr)
- 単位距離グラフとは、グラフ理論のグラフの一種であり、ユークリッド平面上に、すべての辺の長さを単位長さとして描画できるグラフである。辺同士が交差してもよい（その場合平面グラフではなくなる）。平面グラフでもある単位距離グラフは、と呼ばれる。 は、単位距離グラフの彩色数についての問題である。彩色数が5である単位距離グラフが存在する一方、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の次数の上限はいくつか？がある。 (ja)
- Ein Einheitsdistanz-Graph ist ein geometrischer Graph, bei dem jede Kante gleich lang ist.Kanten eines Einheitsdistanz-Graphen dürfen sich überschneiden, d. h. der Graph muss nicht immer planar sein. Ein Einheitsdistanz-Graph ohne Überschneidungen wird Streichholzgraph genannt. (de)
- In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs. (en)
- В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом. (ru)
- Графом одиничних відстаней у теорії графів називається граф, утворений точками на евклідовій площині, у якому ребрами з'єднані кожні дві вершини, відстань між якими дорівнює точно одиниці. Ребра графів одиничних відстаней іноді перетинаються, тож графи одиничних відстаней не завжди планарні. Граф одиничних відстаней без перетинів називається сірниковим графом. (uk)
|
| rdfs:label
|
- Einheitsdistanz-Graph (de)
- Graphe distance-unité (fr)
- 単位距離グラフ (ja)
- Unit distance graph (en)
- Граф единичных расстояний (ru)
- Граф одиничних відстаней (uk)
|
| rdfs:seeAlso
| |
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:properties
of | |
| is foaf:primaryTopic
of | |
