Unit distance graph (original) (raw)
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.
| Property | Value |
|---|---|
| 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 | wiki-commons:Special:FilePath/Unit_distance_16_40.svg?width=300 |
| dbo:wikiPageExternalLink | http://cs.smith.edu/~jorourke/TOPP/P39.html https://www.combinatorics.org/Volume_15/Abstracts/v15i1r107.html https://m.tau.ac.il/~nogaa/PDFS/ramsey10.pdf https://books.google.com/books%3Fid=tmORL-UYOyEC&pg=PA475 https://www.science.org/content/article/amateur-mathematician-cracks-decades-old-math-problem https://users.renyi.hu/~p_erdos/1965-09.pdf |
| dbo:wikiPageID | 7158665 (xsd:integer) |
| dbo:wikiPageLength | 33229 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1124841185 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Beckman–Quarles_theorem dbr:Root_of_unity dbr:Electronic_Journal_of_Combinatorics dbr:Moser_spindle dbr:Dense_graph dbr:Hypercube_graph dbc:Geometric_graphs dbr:Path_graph dbr:Paul_Erdős dbr:Regular_hexagon dbr:Regular_polygon dbr:Undirected_graph dbr:Upper_bound dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Degree_(graph_theory) dbr:Induced_subgraph dbr:Penny_graph dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Complex_number dbr:Crossing_number_inequality dbr:Crown_graph dbr:Mathematics dbr:Generalized_Petersen_graph dbr:Geometric_graph_theory dbr:Petersen_graph dbr:Strong_product_of_graphs dbr:Chromatic_number dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:NP-hard dbr:Congruence_(geometry) dbr:SIAM_Journal_on_Computing dbr:Lower_bound dbr:Cactus_graph dbr:Hadwiger–Nelson_problem dbr:Proceedings_of_the_American_Mathematical_Society dbr:Mathematika dbr:Additive_group dbr:Tree_(graph_theory) dbr:Triangle-free_graph dbr:Wheel_graph dbr:Heawood_graph dbr:Absolute_value dbr:Algebraic_number dbr:American_Mathematical_Monthly dbr:Cycle_graph dbr:Edge_(graph_theory) dbr:Euclidean_space dbr:Forbidden_graph_characterization dbr:Discrete_&_Computational_Geometry dbr:Discrete_Applied_Mathematics dbr:Discrete_Mathematics_(journal) dbr:Golomb_graph dbr:Graph_automorphism dbr:Graph_isomorphism dbr:Graphs_and_Combinatorics dbr:Iterated_logarithm dbr:Journal_of_Combinatorial_Theory dbr:Structural_rigidity dbr:Hamming_graph dbr:Isometry dbr:Ackermann_function dbr:Aequationes_Mathematicae dbr:Biconnected_graph dbr:Big_O_notation dbr:Hereditary_property dbr:Szemerédi–Trotter_theorem dbr:Axiom_of_choice dbr:Planar_graph dbr:Cartesian_product_of_graphs dbr:Matchstick_graph dbr:Pattern_matching dbr:Relative_neighborhood_graph dbr:Science_(journal) dbr:Unit_disk_graph dbr:Vertex_(graph_theory) dbr:Up_to dbr:Triangular_prism dbr:Euclidean_distance dbr:Euclidean_plane dbr:Euclidean_plane_isometry dbr:Extremal_graph_theory dbr:Existential_theory_of_the_reals dbr:Möbius–Kantor_graph dbr:Geombinatorics dbr:Triangle_graph dbr:File:Hadwiger-Nelson.svg dbr:Finitely_generated_subgroup dbr:Hamiltonian_cycle dbr:Grid_graph dbr:File:Unit_distance_16_40.svg |
| dbp:authorlink | Paul Erdős (en) |
| 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 | Paul (en) |
| dbp:image | Hamming33UnitDistance.gif (en) Hypercubestar.svg (en) Möbius–Kantor unit distance.svg (en) Petersen graph, unit distance.svg (en) |
| dbp:last | Erdős (en) |
| dbp:mode | cs2 (en) |
| dbp:title | Unit-Distance Graph (en) |
| dbp:totalWidth | 400 (xsd:integer) 480 (xsd:integer) |
| dbp:urlname | Unit-DistanceGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:As_of dbt:Citation dbt:Good_article dbt:Harvtxt dbt:Main dbt:Mathworld dbt:Multiple_image dbt:OEIS dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Sfnp dbt:Short_description dbt:Harvs dbt:Bi dbt:Unsolved |
| dbp:year | 1946 (xsd:integer) |
| dcterms:subject | dbc:Geometric_graphs |
| gold:hypernym | dbr:Graph |
| rdf:type | owl:Thing dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| 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 | dbr:Erdős_distinct_distances_problem |
| owl:sameAs | freebase:Unit distance graph yago-res:Unit distance graph wikidata:Unit distance graph dbpedia-de:Unit distance graph dbpedia-fr:Unit distance graph dbpedia-hu:Unit distance graph dbpedia-ja:Unit distance graph dbpedia-ru:Unit distance graph http://ta.dbpedia.org/resource/அலகு_தொலைவு_கோட்டுரு dbpedia-uk:Unit distance graph dbpedia-vi:Unit distance graph https://global.dbpedia.org/id/4uWHN |
| prov:wasDerivedFrom | wikipedia-en:Unit_distance_graph?oldid=1124841185&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Möbius–Kantor_unit_distance.svg wiki-commons:Special:FilePath/Hypercubestar.svg wiki-commons:Special:FilePath/Hadwiger-Nelson.svg wiki-commons:Special:FilePath/Petersen_graph,_unit_distance.svg wiki-commons:Special:FilePath/Hamming33UnitDistance.gif wiki-commons:Special:FilePath/Unit_distance_16_40.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Unit_distance_graph |
| is dbo:wikiPageDisambiguates of | dbr:Unit_distance |
| is dbo:wikiPageRedirects of | dbr:Unit-distance_graph |
| is dbo:wikiPageWikiLink of | dbr:Beckman–Quarles_theorem dbr:Moser_spindle dbr:Hypercube_graph dbr:Path_graph dbr:Rhombille_tiling dbr:De_Bruijn–Erdős_theorem_(graph_theory) dbr:Penny_graph dbr:Crown_graph dbr:Generalized_Petersen_graph dbr:Geometric_graph_theory dbr:Petersen_graph dbr:Friendship_graph dbr:Core_(graph_theory) dbr:Erdős_distinct_distances_problem dbr:Erdős–Diophantine_graph dbr:Star_(graph_theory) dbr:Hadwiger–Nelson_problem dbr:Butterfly_graph dbr:Wheel_graph dbr:Hashiwokakero dbr:Heawood_graph dbr:Lattice_graph dbr:Cycle_graph dbr:Golomb_graph dbr:Hajós_construction dbr:Hamming_graph dbr:Ladder_graph dbr:Laves_graph dbr:Holt_graph dbr:Diamond_graph dbr:Dimension_(graph_theory) dbr:Bull_graph dbr:Carolyn_Mahoney dbr:Cartesian_product_of_graphs dbr:Matchstick_graph dbr:Unit_disk_graph dbr:Unit_distance dbr:List_of_unsolved_problems_in_mathematics dbr:Existential_theory_of_the_reals dbr:Möbius–Kantor_graph dbr:Nauru_graph dbr:Triangle_graph dbr:Unit-distance_graph |
| is dbp:properties of | dbr:Moser_spindle dbr:Hypercube_graph dbr:Path_graph dbr:Friendship_graph dbr:Star_(graph_theory) dbr:Butterfly_graph dbr:Cycle_graph dbr:Golomb_graph dbr:Ladder_graph dbr:Diamond_graph dbr:Bull_graph dbr:Möbius–Kantor_graph dbr:Triangle_graph |
| is foaf:primaryTopic of | wikipedia-en:Unit_distance_graph |
