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