| http://dbpedia.org/ontology/abstract
|
En mathématiques, plus particulièrement en … 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.e graphe est qualifié de graphe allumette.
, 単位距離グラフとは、グラフ理論のグラフの一種であり、ユークリッド平面上に、すべての辺の長さを単位長さとして描画できるグラフである。辺同士が交差してもよい（その場合平面グラフではなくなる）。平面グラフでもある単位距離グラフは、と呼ばれる。 は、単位距離グラフの彩色数についての問題である。彩色数が5である単位距離グラフが存在する一方、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の次数の上限はいくつか？がある。
, Графом одиничних відстаней у теорії графів … Графом одиничних відстаней у теорії графів називається граф, утворений точками на евклідовій площині, у якому ребрами з'єднані кожні дві вершини, відстань між якими дорівнює точно одиниці. Ребра графів одиничних відстаней іноді перетинаються, тож графи одиничних відстаней не завжди планарні. Граф одиничних відстаней без перетинів називається сірниковим графом. Проблема Нельсона — Ердеша — Гадвігера стосується хроматичного числа графів одиничних відстаней. Відомо, що існують графи одиничних відстаней, що вимагають 4 кольори для правильного розфарбування і що всі такі графи можна розфарбувати не більш ніж у 7 кольорів. Інше важливе відкрите питання стосовно графів одиничних відстаней звучить так: «скільки ребер може мати такий граф відносно числа вершин?».е мати такий граф відносно числа вершин?».
, In mathematics, particularly geometric gra … 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.e for the existential theory of the reals.
, В теории графов графом единичных расстояни … В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом. Проблема Нелсона — Эрдёша — Хадвигера касается хроматического числа графов единичных расстояний. Известно, что существуют графы единичных расстояний, требующие 5 цветов для правильной раскраски и что все такие графы можно раскрасить не более чем в 7 цветов. Другая важная открытая задача, касающаяся графов единичных расстояний, спрашивает, сколько рёбер может иметь такой граф по отношению к числу вершин.ть такой граф по отношению к числу вершин.
, Ein Einheitsdistanz-Graph ist ein geometri … 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.nis von Kanten- zu Knotenanzahl sein kann.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Unit_distance_16_40.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
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 +
, https://www.combinatorics.org/Volume_15/Abstracts/v15i1r107.html +
, https://m.tau.ac.il/~nogaa/PDFS/ramsey10.pdf +
, http://cs.smith.edu/~jorourke/TOPP/P39.html +
|
| http://dbpedia.org/ontology/wikiPageID
|
7158665
|
| http://dbpedia.org/ontology/wikiPageLength
|
33229
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
1124841185
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://dbpedia.org/resource/Tree_%28graph_theory%29 +
, http://dbpedia.org/resource/Relative_neighborhood_graph +
, http://dbpedia.org/resource/Discrete_Applied_Mathematics +
, http://dbpedia.org/resource/Algebraic_number +
, http://dbpedia.org/resource/Golomb_graph +
, http://dbpedia.org/resource/Euclidean_plane +
, http://dbpedia.org/resource/SIAM_Journal_on_Computing +
, http://dbpedia.org/resource/Penny_graph +
, http://dbpedia.org/resource/Strong_product_of_graphs +
, http://dbpedia.org/resource/Geometric_graph_theory +
, http://dbpedia.org/resource/Category:Geometric_graphs +
, http://dbpedia.org/resource/Paul_Erd%C5%91s +
, http://dbpedia.org/resource/Triangle-free_graph +
, http://dbpedia.org/resource/Dense_graph +
, http://dbpedia.org/resource/Aequationes_Mathematicae +
, http://dbpedia.org/resource/Journal_of_Combinatorial_Theory +
, http://dbpedia.org/resource/American_Mathematical_Monthly +
, http://dbpedia.org/resource/Discrete_Mathematics_%28journal%29 +
, http://dbpedia.org/resource/Science_%28journal%29 +
, http://dbpedia.org/resource/Lower_bound +
, http://dbpedia.org/resource/Complex_number +
, http://dbpedia.org/resource/De_Bruijn%E2%80%93Erd%C5%91s_theorem_%28graph_theory%29 +
, http://dbpedia.org/resource/Crown_graph +
, http://dbpedia.org/resource/Absolute_value +
, http://dbpedia.org/resource/Triangular_prism +
, http://dbpedia.org/resource/M%C3%B6bius%E2%80%93Kantor_graph +
, http://dbpedia.org/resource/Up_to +
, http://dbpedia.org/resource/Biconnected_graph +
, http://dbpedia.org/resource/Euclidean_plane_isometry +
, http://dbpedia.org/resource/Congruence_%28geometry%29 +
, http://dbpedia.org/resource/Cactus_graph +
, http://dbpedia.org/resource/Regular_hexagon +
, http://dbpedia.org/resource/NP-hard +
, http://dbpedia.org/resource/Beckman%E2%80%93Quarles_theorem +
, http://dbpedia.org/resource/Szemer%C3%A9di%E2%80%93Trotter_theorem +
, http://dbpedia.org/resource/Graph_coloring +
, http://dbpedia.org/resource/Existential_theory_of_the_reals +
, http://dbpedia.org/resource/Euclidean_space +
, http://dbpedia.org/resource/Complete_graph +
, http://dbpedia.org/resource/Upper_bound +
, http://dbpedia.org/resource/Grid_graph +
, http://dbpedia.org/resource/Additive_group +
, http://dbpedia.org/resource/Euclidean_distance +
, http://dbpedia.org/resource/Isometry +
, http://dbpedia.org/resource/Axiom_of_choice +
, http://dbpedia.org/resource/Generalized_Petersen_graph +
, http://dbpedia.org/resource/Mathematika +
, http://dbpedia.org/resource/Undirected_graph +
, http://dbpedia.org/resource/Geombinatorics +
, http://dbpedia.org/resource/Heawood_graph +
, http://dbpedia.org/resource/Complete_bipartite_graph +
, http://dbpedia.org/resource/Graph_automorphism +
, http://dbpedia.org/resource/Forbidden_graph_characterization +
, http://dbpedia.org/resource/Path_graph +
, http://dbpedia.org/resource/Pattern_matching +
, http://dbpedia.org/resource/Vertex_%28graph_theory%29 +
, http://dbpedia.org/resource/Induced_subgraph +
, http://dbpedia.org/resource/Graph_isomorphism +
, http://dbpedia.org/resource/Degree_%28graph_theory%29 +
, http://dbpedia.org/resource/Hereditary_property +
, http://dbpedia.org/resource/Edge_%28graph_theory%29 +
, http://dbpedia.org/resource/Regular_polygon +
, http://dbpedia.org/resource/Unit_disk_graph +
, http://dbpedia.org/resource/Mathematics +
, http://dbpedia.org/resource/Hadwiger%E2%80%93Nelson_problem +
, http://dbpedia.org/resource/Root_of_unity +
, http://dbpedia.org/resource/Graphs_and_Combinatorics +
, http://dbpedia.org/resource/Extremal_graph_theory +
, http://dbpedia.org/resource/Cartesian_product_of_graphs +
, http://dbpedia.org/resource/Chromatic_number +
, http://dbpedia.org/resource/Finitely_generated_subgroup +
, http://dbpedia.org/resource/File:Unit_distance_16_40.svg +
, http://dbpedia.org/resource/Triangle_graph +
, http://dbpedia.org/resource/Discrete_&_Computational_Geometry +
, http://dbpedia.org/resource/Big_O_notation +
, http://dbpedia.org/resource/Structural_rigidity +
, http://dbpedia.org/resource/Electronic_Journal_of_Combinatorics +
, http://dbpedia.org/resource/Petersen_graph +
, http://dbpedia.org/resource/NP-complete +
, http://dbpedia.org/resource/Hypercube_graph +
, http://dbpedia.org/resource/Crossing_number_inequality +
, http://dbpedia.org/resource/Planar_graph +
, http://dbpedia.org/resource/Matchstick_graph +
, http://dbpedia.org/resource/Cycle_graph +
, http://dbpedia.org/resource/Iterated_logarithm +
, http://dbpedia.org/resource/File:Hadwiger-Nelson.svg +
, http://dbpedia.org/resource/Hamiltonian_cycle +
, http://dbpedia.org/resource/Wheel_graph +
, http://dbpedia.org/resource/Ackermann_function +
, http://dbpedia.org/resource/Proceedings_of_the_American_Mathematical_Society +
, http://dbpedia.org/resource/Hamming_graph +
, http://dbpedia.org/resource/Moser_spindle +
, http://dbpedia.org/resource/Graph_%28discrete_mathematics%29 +
|
| http://dbpedia.org/property/authorlink
|
Paul Erdős
|
| http://dbpedia.org/property/caption
|
The hypercube graph has 16 vertices and 32 unit distances
, The Möbius–Kantor graph as a subgraph of a unit distance graph
, The Hamming graph has 27 vertices and 81 unit distances
, The Petersen graph as a unit distance graph
|
| http://dbpedia.org/property/first
|
Paul
|
| http://dbpedia.org/property/image
|
Petersen graph, unit distance.svg
, Hypercubestar.svg
, Hamming33UnitDistance.gif
, Möbius–Kantor unit distance.svg
|
| http://dbpedia.org/property/last
|
Erdős
|
| http://dbpedia.org/property/mode
|
cs2
|
| http://dbpedia.org/property/title
|
Unit-Distance Graph
|
| http://dbpedia.org/property/totalWidth
|
480
, 400
|
| http://dbpedia.org/property/urlname
|
Unit-DistanceGraph
|
| http://dbpedia.org/property/wikiPageUsesTemplate
|
http://dbpedia.org/resource/Template:See_also +
, http://dbpedia.org/resource/Template:Refbegin +
, http://dbpedia.org/resource/Template:Refend +
, http://dbpedia.org/resource/Template:Unsolved +
, http://dbpedia.org/resource/Template:Sfnp +
, http://dbpedia.org/resource/Template:Short_description +
, http://dbpedia.org/resource/Template:Harvtxt +
, http://dbpedia.org/resource/Template:Citation +
, http://dbpedia.org/resource/Template:Multiple_image +
, http://dbpedia.org/resource/Template:Good_article +
, http://dbpedia.org/resource/Template:Harvs +
, http://dbpedia.org/resource/Template:OEIS +
, http://dbpedia.org/resource/Template:Mathworld +
, http://dbpedia.org/resource/Template:As_of +
, http://dbpedia.org/resource/Template:Reflist +
, http://dbpedia.org/resource/Template:Bi +
, http://dbpedia.org/resource/Template:Main +
|
| http://dbpedia.org/property/year
|
1946
|
| http://purl.org/dc/terms/subject
|
http://dbpedia.org/resource/Category:Geometric_graphs +
|
| http://purl.org/linguistics/gold/hypernym
|
http://dbpedia.org/resource/Graph +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://en.wikipedia.org/wiki/Unit_distance_graph?oldid=1124841185&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Unit_distance_16_40.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/M%C3%B6bius%E2%80%93Kantor_unit_distance.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Petersen_graph%2C_unit_distance.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Hadwiger-Nelson.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Hamming33UnitDistance.gif +
, http://commons.wikimedia.org/wiki/Special:FilePath/Hypercubestar.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://en.wikipedia.org/wiki/Unit_distance_graph +
|
| owl:sameAs |
http://dbpedia.org/resource/Unit_distance_graph +
, http://yago-knowledge.org/resource/Unit_distance_graph +
, http://www.wikidata.org/entity/Q745378 +
, http://ta.dbpedia.org/resource/%E0%AE%85%E0%AE%B2%E0%AE%95%E0%AF%81_%E0%AE%A4%E0%AF%8A%E0%AE%B2%E0%AF%88%E0%AE%B5%E0%AF%81_%E0%AE%95%E0%AF%8B%E0%AE%9F%E0%AF%8D%E0%AE%9F%E0%AF%81%E0%AE%B0%E0%AF%81 +
, http://uk.dbpedia.org/resource/%D0%93%D1%80%D0%B0%D1%84_%D0%BE%D0%B4%D0%B8%D0%BD%D0%B8%D1%87%D0%BD%D0%B8%D1%85_%D0%B2%D1%96%D0%B4%D1%81%D1%82%D0%B0%D0%BD%D0%B5%D0%B9 +
, http://rdf.freebase.com/ns/m.0h79tw +
, https://global.dbpedia.org/id/4uWHN +
, http://hu.dbpedia.org/resource/Egys%C3%A9gt%C3%A1vols%C3%A1ggr%C3%A1f +
, http://ru.dbpedia.org/resource/%D0%93%D1%80%D0%B0%D1%84_%D0%B5%D0%B4%D0%B8%D0%BD%D0%B8%D1%87%D0%BD%D1%8B%D1%85_%D1%80%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B9 +
, http://vi.dbpedia.org/resource/%C4%90%E1%BB%93_th%E1%BB%8B_c%E1%BA%A1nh_%C4%91%C6%A1n_v%E1%BB%8B +
, http://ja.dbpedia.org/resource/%E5%8D%98%E4%BD%8D%E8%B7%9D%E9%9B%A2%E3%82%B0%E3%83%A9%E3%83%95 +
, http://fr.dbpedia.org/resource/Graphe_distance-unit%C3%A9 +
, http://de.dbpedia.org/resource/Einheitsdistanz-Graph +
|
| rdf:type |
http://dbpedia.org/ontology/Software +
, http://dbpedia.org/class/yago/Abstraction100002137 +
, http://dbpedia.org/class/yago/WikicatGraphFamilies +
, http://dbpedia.org/class/yago/SocialGroup107950920 +
, http://dbpedia.org/class/yago/Unit108189659 +
, http://dbpedia.org/class/yago/Group100031264 +
, http://dbpedia.org/class/yago/Organization108008335 +
, http://dbpedia.org/class/yago/YagoLegalActorGeo +
, http://dbpedia.org/class/yago/YagoLegalActor +
, http://dbpedia.org/class/yago/Family108078020 +
, http://dbpedia.org/class/yago/YagoPermanentlyLocatedEntity +
|
| rdfs:comment |
En mathématiques, plus particulièrement en … 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.e graphe est qualifié de graphe allumette.
, В теории графов графом единичных расстояни … В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром, если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом.з пересечений называется спичечным графом.
, Ein Einheitsdistanz-Graph ist ein geometri … 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.chneidungen wird Streichholzgraph genannt.
, Графом одиничних відстаней у теорії графів … Графом одиничних відстаней у теорії графів називається граф, утворений точками на евклідовій площині, у якому ребрами з'єднані кожні дві вершини, відстань між якими дорівнює точно одиниці. Ребра графів одиничних відстаней іноді перетинаються, тож графи одиничних відстаней не завжди планарні. Граф одиничних відстаней без перетинів називається сірниковим графом.з перетинів називається сірниковим графом.
, 単位距離グラフとは、グラフ理論のグラフの一種であり、ユークリッド平面上に、すべての辺の長さを単位長さとして描画できるグラフである。辺同士が交差してもよい（その場合平面グラフではなくなる）。平面グラフでもある単位距離グラフは、と呼ばれる。 は、単位距離グラフの彩色数についての問題である。彩色数が5である単位距離グラフが存在する一方、少なくとも7色で塗り分けられることが知られている。同様に重要な未解決問題に、単位距離グラフの頂点の次数の上限はいくつか？がある。
, In mathematics, particularly geometric gra … 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.raphs are non-strict unit distance graphs.
|
| rdfs:label |
Граф одиничних відстаней
, Graphe distance-unité
, 単位距離グラフ
, Unit distance graph
, Einheitsdistanz-Graph
, Граф единичных расстояний
|
| rdfs:seeAlso |
http://dbpedia.org/resource/Erd%C5%91s_distinct_distances_problem +
|
