Dimension (graph theory)
http://dbpedia.org/resource/Dimension_(graph_theory)
Размерность графа — наименьшее целое n такое, что существует «классическое представление» графа в евклидовом пространстве размерности n с единичными длинами рёбер. В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться. Размерность графа G записывается как . Например, граф Петерсена может быть нарисован с единичными рёбрами в , но не в , его размерность поэтому равна 2 (см. рисунок справа). Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям Татт. Она обобщает концепцию графа единичных расстояний для размерностей более 2.
rdf:langString
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).
rdf:langString
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).
rdf:langString
rdf:langString
Dimension (graph theory)
rdf:langString
Dimension (théorie des graphes)
rdf:langString
Размерность графа
xsd:integer
39179243
xsd:integer
1082329557
rdf:langString
border:solid 1px #aaa
rdf:langString
Proof
rdf:langString
left
rdf:langString
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.
rdf:langString
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 .
rdf:langString
Размерность графа — наименьшее целое n такое, что существует «классическое представление» графа в евклидовом пространстве размерности n с единичными длинами рёбер. В классическом представлении все вершины должны быть различны, но рёбра могут пересекаться. Размерность графа G записывается как . Например, граф Петерсена может быть нарисован с единичными рёбрами в , но не в , его размерность поэтому равна 2 (см. рисунок справа). Концепцию предложили в 1965 году Пал Эрдёш, Фрэнк Харари и Уильям Татт. Она обобщает концепцию графа единичных расстояний для размерностей более 2.
xsd:nonNegativeInteger
9201
