Dimension (graph theory) (original) (raw)

About DBpedia

Размерность графа — наименьшее целое n такое, что существует «классическое представление» графа в евклидовом пространстве размерности n с единичными длинами рёбер. В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться. Размерность графа G записывается как . Например, граф Петерсена может быть нарисован с единичными рёбрами в , но не в , его размерность поэтому равна 2 (см. рисунок справа). Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям Татт. Она обобщает концепцию графа единичных расстояний для размерностей более 2.

thumbnail

Property Value
dbo:abstract In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n with all the edges having unit length. In a classical representation, the vertices must be distinct points, but the edges may cross one another. The dimension of a graph G is written: . For example, the Petersen graph can be drawn with unit edges in , but not in : its dimension is therefore 2 (see the figure to the right). This concept was introduced in 1965 by Paul Erdős, Frank Harary and William Tutte. It generalises the concept of unit distance graph to more than 2 dimensions. (en) En mathématiques, et plus particulièrement dans la théorie des graphes, la dimension d'un graphe est le plus petit nombre entier tel qu'une représentation classique du graphe dans l'espace affine euclidien de dimension ne comporte que des segments de longueur 1. Dans cette définition, les sommets doivent être distincts, mais il n'y a pas de contraintes sur le croisement des arêtes. On note la dimension d'un graphe ainsi : . Par exemple, le graphe de Petersen peut être tracé avec des segments de longueur 1 sur le plan euclidien , mais pas sur la droite : sa dimension est 2 (figure). Cette notion a été introduite en 1965 par Paul Erdős, Frank Harary et William Tutte. Elle généralise à une dimension quelconque la notion de graphe distance-unité du plan . (fr) Размерность графа — наименьшее целое n такое, что существует «классическое представление» графа в евклидовом пространстве размерности n с единичными длинами рёбер. В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться. Размерность графа G записывается как . Например, граф Петерсена может быть нарисован с единичными рёбрами в , но не в , его размерность поэтому равна 2 (см. рисунок справа). Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям Татт. Она обобщает концепцию графа единичных расстояний для размерностей более 2. (ru)
dbo:thumbnail wiki-commons:Special:FilePath/Petersen_graph,_unit_distance.svg?width=300
dbo:wikiPageID 39179243 (xsd:integer)
dbo:wikiPageLength 9201 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1082329557 (xsd:integer)
dbo:wikiPageWikiLink dbr:Paul_Erdős dbr:Unit_distance_graph dbr:Degree_(graph_theory) dbc:Graph_invariants dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Mathematics dbr:Petersen_graph dbr:Chromatic_number dbr:Frank_Harary dbc:Geometric_graph_theory dbr:NP-hard dbr:Miklós_Simonovits dbr:Simplex dbr:Star_(graph_theory) dbr:Wheel_graph dbr:Alexander_Soifer dbr:Euclidean_space dbr:Graph_theory dbr:Immersion_(mathematics) dbr:Existential_theory_of_the_reals dbr:William_Tutte dbr:File:AlmostWheel3D.svg dbr:File:AlmostWheel3DFolded.svg dbr:File:CompleteBipartite3D.svg dbr:File:Intercpunetstar.png dbr:File:Petersen_graph,_unit_distance.svg dbr:File:Tetrahedron.svg
dbp:style border:solid 1px #aaa (en)
dbp:title Proof (en)
dbp:toggle left (en)
dbp:wikiPageUsesTemplate dbt:Hidden_begin dbt:Hidden_end dbt:Mvar dbt:Reflist dbt:Math_theorem
dct:subject dbc:Graph_invariants dbc:Geometric_graph_theory
rdfs:comment Размерность графа — наименьшее целое n такое, что существует «классическое представление» графа в евклидовом пространстве размерности n с единичными длинами рёбер. В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться. Размерность графа G записывается как . Например, граф Петерсена может быть нарисован с единичными рёбрами в , но не в , его размерность поэтому равна 2 (см. рисунок справа). Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям Татт. Она обобщает концепцию графа единичных расстояний для размерностей более 2. (ru) In mathematics, and particularly in graph theory, the dimension of a graph is the least integer n such that there exists a "classical representation" of the graph in the Euclidean space of dimension n with all the edges having unit length. In a classical representation, the vertices must be distinct points, but the edges may cross one another. The dimension of a graph G is written: . For example, the Petersen graph can be drawn with unit edges in , but not in : its dimension is therefore 2 (see the figure to the right). (en) En mathématiques, et plus particulièrement dans la théorie des graphes, la dimension d'un graphe est le plus petit nombre entier tel qu'une représentation classique du graphe dans l'espace affine euclidien de dimension ne comporte que des segments de longueur 1. Dans cette définition, les sommets doivent être distincts, mais il n'y a pas de contraintes sur le croisement des arêtes. On note la dimension d'un graphe ainsi : . Par exemple, le graphe de Petersen peut être tracé avec des segments de longueur 1 sur le plan euclidien , mais pas sur la droite : sa dimension est 2 (figure). (fr)
rdfs:label Dimension (graph theory) (en) Dimension (théorie des graphes) (fr) Размерность графа (ru)
owl:sameAs freebase:Dimension (graph theory) yago-res:Dimension (graph theory) wikidata:Dimension (graph theory) dbpedia-fr:Dimension (graph theory) dbpedia-ru:Dimension (graph theory) https://global.dbpedia.org/id/Lpm4
prov:wasDerivedFrom wikipedia-en:Dimension_(graph_theory)?oldid=1082329557&ns=0
foaf:depiction wiki-commons:Special:FilePath/Tetrahedron.svg wiki-commons:Special:FilePath/Petersen_graph,_unit_distance.svg wiki-commons:Special:FilePath/AlmostWheel3D.svg wiki-commons:Special:FilePath/AlmostWheel3DFolded.svg wiki-commons:Special:FilePath/CompleteBipartite3D.svg wiki-commons:Special:FilePath/Intercpunetstar.png
foaf:isPrimaryTopicOf wikipedia-en:Dimension_(graph_theory)
is dbo:wikiPageDisambiguates of dbr:Dimension_(disambiguation)
is dbo:wikiPageWikiLink of dbr:Paul_Erdős dbr:Dimension_(disambiguation) dbr:Existential_theory_of_the_reals
is foaf:primaryTopic of wikipedia-en:Dimension_(graph_theory)