Distance-regular graph (original) (raw)
In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w. Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group.
| Property | Value |
|---|---|
| dbo:abstract | In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w. Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. (en) En théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets distants de , et pour tous entiers naturels , il y a toujours le même nombre de sommets qui sont à la fois à distance de et à distance de . De manière équivalente, un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance de et le nombre de sommets voisins de à distance de ne dépendent que de et de la distance entre et . Formellement, tels que et où est l’ensemble des sommets à distance de , et .La séquence forme un vecteur appelé vecteur d'intersection du graphe. (fr) 수학에서 거리 정규 그래프(영어: distance-regular graph)는 임의의 두 꼭짓점 v, w 에 대해 v와의 거리가 j이고 w와의 거리가 k인 꼭짓점 수가 j, k 및 v와 w 사이의 거리에만 의존하는 정규 그래프이다. 모든 는 거리 정규 그래프이다. 실제로, 거리 정규 그래프는 거리 전이 그래프의 일반화로서 도입되었고, 반드시 큰 자기동형군을 갖지 않고도 거리 전이 그래프의 수치적인 규칙성을 갖는다. (ko) No campo da matemática da teoria dos grafos, um grafo distância-regular é um grafo regular tal que para quaisquer dois vértices v e w a uma distância i o número de vértices adjacentes a w e à distância j a partir de v é o mesmo. Todo grafo distância-transitivo é distância regular. Com efeito, grafos distância-regular foram introduzidos como uma generalização combinatória de grafos distância-transitivos, tendo as propriedades de regularidade numérica do último, sem ter necessariamente um grande grupo de automorfismo. Alternativamente, um grafo distância-regular é um grafo para o qual existem inteiros bi,ci,i=0,...,d tais que para quaisquer dois vértices x, y em G e distância i=d(x,y), há exatamente ci vizinhos de y em Gi-1(x) e bi vizinhos de y em Gi+1(x), onde Gi(x) é o conjunto de vértices y de G com d(x,y)=i (Brouwer et al. 1989, p. 434). O array de inteiros caracterizando um grafo distância regular é conhecido como o seu array de interseção. Um grafo distância-regular com diâmetro 2 é fortemente regular, e reciprocamente (a menos que o grafo seja desconexo). (pt) Дистанційно-регулярний граф (англ. distance-regular graph) — це такий регулярний граф, у якого для двох будь-яких вершин і , розташованих на однаковій відстані одна від одної, кількість вершин інцидентних до , і при цьому розташованих на відстані від вершини , залежить тільки від відстані між вершинами і ; більш того кількість інцидентних до вершин, розташованих на відстані від вершини , також залежить тільки від відстані . (uk) Дистанционно-регулярный граф (англ. distance-regular graph) — такой регулярный граф, у которого для двух любых вершин и , расположенных на одинаковом расстоянии друг от друга, справедливо, что количество вершин, инцидентных к и при этом находящихся на расстоянии от вершины , зависит только от расстояния между вершинами и ; более того, количество вершин, инцидентных к и находящихся на расстоянии от вершины , также зависит только от расстояния . Дистанционно-регулярные графы были введены Н. Биггсом в 1969 году на конференции в Оксфорде, хотя сам термин появился гораздо позже. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Klein-map.png?width=300 |
| dbo:wikiPageID | 7768943 (xsd:integer) |
| dbo:wikiPageLength | 6119 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1119300721 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Desargues_graph dbc:Graph_families dbr:Regular_graph dbr:Cubic_graph dbr:Degree_(graph_theory) dbc:Regular_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Petersen_graph dbr:Moore_graph dbr:Pappus_graph dbc:Algebraic_graph_theory dbr:Distance-transitive_graph dbr:Heawood_graph dbr:Spectral_graph_theory dbr:Adjacency_matrix dbr:Cycle_graph dbr:Foster_graph dbr:Graph_automorphism dbr:Graph_theory dbr:Coxeter_graph dbr:Biggs–Smith_graph dbr:Distance_(graph_theory) dbr:Dodecahedral_graph dbr:Graph_Union dbr:Odd_graph dbr:Strongly_regular_graph dbr:Vertex_(graph_theory) dbr:Near_polygon dbr:Sylvester_graph dbr:Tutte_12-cage dbr:Tutte–Coxeter_graph dbr:Wells_graph dbr:Mathematical dbr:Tetrahedral_graph dbr:Cubical_graph dbr:File:Klein-map.png |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Mvar dbt:Refimprove dbt:Reflist dbt:Short_description dbt:Graph_families_defined_by_their_automorphisms |
| dct:subject | dbc:Graph_families dbc:Regular_graphs dbc:Algebraic_graph_theory |
| rdf:type | yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w. Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. (en) 수학에서 거리 정규 그래프(영어: distance-regular graph)는 임의의 두 꼭짓점 v, w 에 대해 v와의 거리가 j이고 w와의 거리가 k인 꼭짓점 수가 j, k 및 v와 w 사이의 거리에만 의존하는 정규 그래프이다. 모든 는 거리 정규 그래프이다. 실제로, 거리 정규 그래프는 거리 전이 그래프의 일반화로서 도입되었고, 반드시 큰 자기동형군을 갖지 않고도 거리 전이 그래프의 수치적인 규칙성을 갖는다. (ko) Дистанційно-регулярний граф (англ. distance-regular graph) — це такий регулярний граф, у якого для двох будь-яких вершин і , розташованих на однаковій відстані одна від одної, кількість вершин інцидентних до , і при цьому розташованих на відстані від вершини , залежить тільки від відстані між вершинами і ; більш того кількість інцидентних до вершин, розташованих на відстані від вершини , також залежить тільки від відстані . (uk) Дистанционно-регулярный граф (англ. distance-regular graph) — такой регулярный граф, у которого для двух любых вершин и , расположенных на одинаковом расстоянии друг от друга, справедливо, что количество вершин, инцидентных к и при этом находящихся на расстоянии от вершины , зависит только от расстояния между вершинами и ; более того, количество вершин, инцидентных к и находящихся на расстоянии от вершины , также зависит только от расстояния . Дистанционно-регулярные графы были введены Н. Биггсом в 1969 году на конференции в Оксфорде, хотя сам термин появился гораздо позже. (ru) En théorie des graphes, un graphe régulier est dit distance-régulier si pour tous sommets distants de , et pour tous entiers naturels , il y a toujours le même nombre de sommets qui sont à la fois à distance de et à distance de . De manière équivalente, un graphe est distance-régulier si pour tous sommets , le nombre de sommets voisins de à distance de et le nombre de sommets voisins de à distance de ne dépendent que de et de la distance entre et . Formellement, tels que et (fr) No campo da matemática da teoria dos grafos, um grafo distância-regular é um grafo regular tal que para quaisquer dois vértices v e w a uma distância i o número de vértices adjacentes a w e à distância j a partir de v é o mesmo. Todo grafo distância-transitivo é distância regular. Com efeito, grafos distância-regular foram introduzidos como uma generalização combinatória de grafos distância-transitivos, tendo as propriedades de regularidade numérica do último, sem ter necessariamente um grande grupo de automorfismo. (pt) |
| rdfs:label | Distance-regular graph (en) Graphe distance-régulier (fr) 거리 정규 그래프 (ko) Grafo distância-regular (pt) Дистанционно-регулярный граф (ru) Дистанційно-регулярний граф (uk) |
| owl:sameAs | freebase:Distance-regular graph yago-res:Distance-regular graph wikidata:Distance-regular graph dbpedia-fr:Distance-regular graph dbpedia-hu:Distance-regular graph dbpedia-ko:Distance-regular graph dbpedia-pt:Distance-regular graph dbpedia-ru:Distance-regular graph dbpedia-uk:Distance-regular graph https://global.dbpedia.org/id/2tSui |
| prov:wasDerivedFrom | wikipedia-en:Distance-regular_graph?oldid=1119300721&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Klein-map.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Distance-regular_graph |
| is dbo:wikiPageRedirects of | dbr:Intersection_Array dbr:Intersection_array dbr:Distance-regular_graphs dbr:Distance_regular_graph |
| is dbo:wikiPageWikiLink of | dbr:Bipartite_half dbr:Desargues_graph dbr:Algebraic_graph_theory dbr:Regular_dodecahedron dbr:Regular_icosahedron dbr:Cube dbr:13_(number) dbr:Crown_graph dbr:Perkel_graph dbr:Petersen_graph dbr:Graph_(discrete_mathematics) dbr:Grassmann_graph dbr:Continuous-time_quantum_walk dbr:Chris_Godsil dbr:Pappus's_hexagon_theorem dbr:Pappus_graph dbr:Distance-transitive_graph dbr:Heawood_graph dbr:Johnson_graph dbr:Locally_linear_graph dbr:Shrikhande_graph dbr:Spectral_graph_theory dbr:5 dbr:Folded_cube_graph dbr:Foster_graph dbr:Gosset_graph dbr:Graph_automorphism dbr:Halved_cube_graph dbr:Hamming_graph dbr:Italo_Jose_Dejter dbr:Coxeter_graph dbr:Tetrahedron dbr:Biggs–Smith_graph dbr:Hoffman_graph dbr:Association_scheme dbr:Odd_graph dbr:Klein_graphs dbr:Strongly_regular_graph dbr:Near_polygon dbr:Tutte–Coxeter_graph dbr:Walk-regular_graph dbr:Intersection_Array dbr:Intersection_array dbr:Distance-regular_graphs dbr:Distance_regular_graph |
| is dbp:properties of | dbr:Desargues_graph dbr:Regular_dodecahedron dbr:Regular_icosahedron dbr:Cube dbr:Pappus_graph dbr:Heawood_graph dbr:Gosset_graph dbr:Hamming_graph dbr:Coxeter_graph dbr:Tetrahedron dbr:Biggs–Smith_graph dbr:Tutte–Coxeter_graph |
| is foaf:primaryTopic of | wikipedia-en:Distance-regular_graph |
