Moore graph (original) (raw)
En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes.
| Property | Value |
|---|---|
| dbo:abstract | En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes. (fr) In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is d and its diameter is k, its girth must equal 2k + 1. This is true, for a graph of degree d and diameter k, if and only if its number of vertices equals an upper bound on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the degree diameter problem for their parameters. Another equivalent definition of a Moore graph G is that it has girth g = 2k + 1 and precisely n/g(m – n + 1) cycles of length g, where n and m are, respectively, the numbers of vertices and edges of G. They are in fact extremal with respect to the number of cycles whose length is the girth of the graph. Moore graphs were named by after Edward F. Moore, who posed the question of describing and classifying these graphs. As well as having the maximum possible number of vertices for a given combination of degree and diameter, Moore graphs have the minimum possible number of vertices for a regular graph with given degree and girth. That is, any Moore graph is a cage. The formula for the number of vertices in a Moore graph can be generalized to allow a definition of Moore graphs with even girth as well as odd girth, and again these graphs are cages. (en) 그래프 이론에서 무어 그래프(Moore graph)는 d , 지름 k이고 꼭짓점 개수가 인 정규 그래프이다. 이 개수는 차수와 지름이 주어졌을 때 그래프가 가질 수 있는 정점 개수의 최댓값이다. 무어 그래프의 몇 가지 동등한 정의는 다음과 같다. * 무어 그래프는 지름이 , 안둘레가 인 그래프이다. * 꼭지점 개, 변 개를 갖는 무어 그래프는 안둘레가 이고 -순환을 개 갖는 그래프이다. 이러한 순환의 개수는 그래프의 안둘레 길이에 대해 극단인 경우이다. 무어 그래프라는 이름은 앨런 호프만과 로버트 싱글턴에 의해, 이러한 그래프를 설명하고 분류하는 문제를 제기한 의 이름을 따서 명명되었다. 무어 그래프는 차수와 지름이 주어졌을 때 가능한 최대 정점 수를 가질 뿐 아니라, 차수와 둘레가 주어졌을 때 가능한 최소 정점 수를 갖는다. 즉, 모든 무어 그래프는 이다. 무어 그래프의 꼭짓점 수에 대한 공식은 짝수 둘레를 가진 무어 그래프를 허용하도록 일반화될 수 있고, 이러한 그래프 역시 케이지이다. (ko) グラフ理論においてムーアグラフとは、次数d、直径kの正則グラフで、頂点数が以下の上限に一致するものである。 直径k、内周2k+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2k+1のときに長さgのサイクルをちょうど個含むようなグラフと定義することもできる。ここでnは頂点数、mは辺の数である。実際、内周に一致するサイクルを上記の条件のように含むグラフが頂点数最小のグラフとなる。 ムーアグラフという名前はにちなんで1960年にホフマンとシングルトンによって名付けられた。 次数と直径が与えられたとき最大の頂点数を持つものがムーアグラフであるが、これは次数と内周が与えられたときに最小の頂点数をもつグラフでもある。すなわちムーアグラフはケージである。通常の定義ではムーアグラフの内周は必ず奇数になるが、ムーアグラフの頂点数、次数、直径の満たす関係式から出発して内周を偶数を許すように拡張することができる。そのような拡張されたムーアグラフはまたケージとなる。 (ja) Em Teoria dos Grafos, um Grafo de Moore é um Grafo regular de grau d e distância k o qual o número de vértices é igual ao limitante superior Uma definição equivalente de um grafo de Moore é que ele é um grafo de distância k com cintura 2k + 1. Uma outra definição equivalente de um grafo de Moore G é que ele tem cintura g = 2k+1 e precisamente ciclos de comprimento g, onde n,m é o número de vértices e arestas, respectivamentes, de G. Eles são de fatos extremos em relação ao número de ciclos cujo comprimento é a cintura do grafo. Grafos de Moore foram nomeados por em homenagem à Edward F. Moore, pessoa que botou em questão descrever e classificar esses grafos. Além de ter o maior número possível de vértices para uma combinação dada de ângulo e diâmetro, Grafos de Moore tem o menor número possível de vértices para um grafo regular com dado ângulo e cintura. Isto é, qualquer e todo Grafo de Moore é uma. A fórmula para o número de vértices num grafo de Moore pode ser generalizada para permitir uma descrição de grafos de Moore tanto com cintura par quanto impar, e, novamente, esses grafos são jaulas. (pt) Граф Мура — регулярный граф степени и диаметром , число вершин которого равно верхней границе Эквивалентное определение графа Мура — это граф диаметра с обхватом . Ещё одно эквивалентное определение графа Мура — это граф с обхватом , имеющий в точности циклов длины , где , — число вершин и рёбер графа . Графы, фактически, экстремальны по отношению к числу циклов, длина которых равна обхвату графа. Графы названы и Робертом Синглтоном именем Эдварда Мура, который поставил вопрос описания и классификации таких графов. Имея максимально возможное число вершин для заданной комбинации степени и диаметра, графы Мура имеют минимально возможное число вершин для регулярных графов с заданной степенью и обхватом. Таким образом, любой граф Мура является клеткой. Формула для числа вершин графа Мура может быть обобщена для возможности определения графов Мура с чётным обхватом, и эти графы снова являются клетками. (ru) Граф Мура — регулярний граф степеня і діаметра , число вершин якого дорівнює верхній межі Еквівалентне визначення графа Мура — це граф діаметра з обхватом . Ще одне еквівалентне визначення графа Мура — це граф із обхватом , що має рівно циклів довжини , де , — число вершин і ребер графа . Графи, фактично, екстремальні щодо числа циклів, довжина яких дорівнює обхвату графа. і Роберт Сінглтон назвали граф ім'ям Едварда Мура, який поставив питання опису та класифікації таких графів. Маючи максимально можливе число вершин для заданої комбінації степеня і діаметра, графи Мура мають мінімально можливе число вершин для регулярних графів із заданими степенем і обхватом. Таким чином, будь-який граф Мура є кліткою. Формулу для числа вершин графа Мура можна узагальнити для можливості визначення графів Мура з парним обхватом, і ці графи знову ж є клітками. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Petersen-as-Moore.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math-inst.hu/~p_erdos/1966-06.pdf https://web.archive.org/web/20160309214909/http:/www.math-inst.hu/~p_erdos/1966-06.pdf https://web.archive.org/web/20120424231252/http:/repository.dl.itc.u-tokyo.ac.jp/dspace/handle/2261/6123 https://upcommons.upc.edu/bitstream/2117/127212/1/monster%2818oct2017-rev30dec2018%29.pdf http://homepages.cwi.nl/~aeb/math/ipm/ipm.pdf http://repository.dl.itc.u-tokyo.ac.jp/dspace/handle/2261/6123 |
| dbo:wikiPageID | 4112719 (xsd:integer) |
| dbo:wikiPageLength | 11672 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096680615 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_families dbr:Regular_graph dbr:Cycle_(graph_theory) dbr:Upper_bound dbr:Vertex-transitive_graph dbr:Degree_(graph_theory) dbr:Degree_diameter_problem dbc:Regular_graphs dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Generalized_polygon dbr:Petersen_graph dbr:Edward_F._Moore dbr:Girth_(graph_theory) dbr:Andries_Brouwer dbr:Cage_(graph_theory) dbr:Heawood_graph dbr:Linear_Algebra_and_Its_Applications dbr:American_Mathematical_Monthly dbr:Cycle_graph dbr:Diameter_(graph_theory) dbr:Graduate_Texts_in_Mathematics dbr:Graph_theory dbr:Journal_of_Graph_Theory dbr:Hoffman–Singleton_graph dbr:Vertex_(graph_theory) dbr:Tutte–Coxeter_graph dbr:Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree dbr:Springer-Verlag dbr:Breadth_first_search dbr:File:Petersen-as-Moore.svg |
| dbp:title | Hoffman-Singleton Theorem (en) Moore Graph (en) |
| dbp:urlname | Hoffman-SingletonTheorem (en) MooreGraph (en) |
| dbp:wikiPageUsesTemplate | dbt:MathWorld2 dbt:Citation dbt:Harvtxt dbt:Math dbt:Mvar dbt:Reflist dbt:Sfnp dbt:Sfrac dbt:Short_description dbt:Sub dbt:Sup dbt:Unsolved |
| dcterms:subject | dbc:Graph_families dbc:Regular_graphs |
| rdf:type | yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes. (fr) 그래프 이론에서 무어 그래프(Moore graph)는 d , 지름 k이고 꼭짓점 개수가 인 정규 그래프이다. 이 개수는 차수와 지름이 주어졌을 때 그래프가 가질 수 있는 정점 개수의 최댓값이다. 무어 그래프의 몇 가지 동등한 정의는 다음과 같다. * 무어 그래프는 지름이 , 안둘레가 인 그래프이다. * 꼭지점 개, 변 개를 갖는 무어 그래프는 안둘레가 이고 -순환을 개 갖는 그래프이다. 이러한 순환의 개수는 그래프의 안둘레 길이에 대해 극단인 경우이다. 무어 그래프라는 이름은 앨런 호프만과 로버트 싱글턴에 의해, 이러한 그래프를 설명하고 분류하는 문제를 제기한 의 이름을 따서 명명되었다. 무어 그래프는 차수와 지름이 주어졌을 때 가능한 최대 정점 수를 가질 뿐 아니라, 차수와 둘레가 주어졌을 때 가능한 최소 정점 수를 갖는다. 즉, 모든 무어 그래프는 이다. 무어 그래프의 꼭짓점 수에 대한 공식은 짝수 둘레를 가진 무어 그래프를 허용하도록 일반화될 수 있고, 이러한 그래프 역시 케이지이다. (ko) グラフ理論においてムーアグラフとは、次数d、直径kの正則グラフで、頂点数が以下の上限に一致するものである。 直径k、内周2k+1のグラフで頂点数が最小のもの、とムーアグラフを定義することもできる。また内周が2k+1のときに長さgのサイクルをちょうど個含むようなグラフと定義することもできる。ここでnは頂点数、mは辺の数である。実際、内周に一致するサイクルを上記の条件のように含むグラフが頂点数最小のグラフとなる。 ムーアグラフという名前はにちなんで1960年にホフマンとシングルトンによって名付けられた。 次数と直径が与えられたとき最大の頂点数を持つものがムーアグラフであるが、これは次数と内周が与えられたときに最小の頂点数をもつグラフでもある。すなわちムーアグラフはケージである。通常の定義ではムーアグラフの内周は必ず奇数になるが、ムーアグラフの頂点数、次数、直径の満たす関係式から出発して内周を偶数を許すように拡張することができる。そのような拡張されたムーアグラフはまたケージとなる。 (ja) In graph theory, a Moore graph is a regular graph whose girth (the shortest cycle length) is more than twice its diameter (the distance between the farthest two vertices). If the degree of such a graph is d and its diameter is k, its girth must equal 2k + 1. This is true, for a graph of degree d and diameter k, if and only if its number of vertices equals an upper bound on the largest possible number of vertices in any graph with this degree and diameter. Therefore, these graphs solve the degree diameter problem for their parameters. (en) Em Teoria dos Grafos, um Grafo de Moore é um Grafo regular de grau d e distância k o qual o número de vértices é igual ao limitante superior Uma definição equivalente de um grafo de Moore é que ele é um grafo de distância k com cintura 2k + 1. Uma outra definição equivalente de um grafo de Moore G é que ele tem cintura g = 2k+1 e precisamente ciclos de comprimento g, onde n,m é o número de vértices e arestas, respectivamentes, de G. Eles são de fatos extremos em relação ao número de ciclos cujo comprimento é a cintura do grafo. (pt) Граф Мура — регулярный граф степени и диаметром , число вершин которого равно верхней границе Эквивалентное определение графа Мура — это граф диаметра с обхватом . Ещё одно эквивалентное определение графа Мура — это граф с обхватом , имеющий в точности циклов длины , где , — число вершин и рёбер графа . Графы, фактически, экстремальны по отношению к числу циклов, длина которых равна обхвату графа. Графы названы и Робертом Синглтоном именем Эдварда Мура, который поставил вопрос описания и классификации таких графов. (ru) Граф Мура — регулярний граф степеня і діаметра , число вершин якого дорівнює верхній межі Еквівалентне визначення графа Мура — це граф діаметра з обхватом . Ще одне еквівалентне визначення графа Мура — це граф із обхватом , що має рівно циклів довжини , де , — число вершин і ребер графа . Графи, фактично, екстремальні щодо числа циклів, довжина яких дорівнює обхвату графа. і Роберт Сінглтон назвали граф ім'ям Едварда Мура, який поставив питання опису та класифікації таких графів. (uk) |
| rdfs:label | Graphe de Moore (fr) ムーアグラフ (ja) Moore graph (en) 무어 그래프 (ko) Grafo de Moore (pt) Граф Мура (ru) Граф Мура (uk) |
| owl:sameAs | freebase:Moore graph yago-res:Moore graph wikidata:Moore graph dbpedia-fa:Moore graph dbpedia-fr:Moore graph dbpedia-ja:Moore graph dbpedia-ko:Moore graph dbpedia-pt:Moore graph dbpedia-ru:Moore graph dbpedia-uk:Moore graph https://global.dbpedia.org/id/2tUUp |
| prov:wasDerivedFrom | wikipedia-en:Moore_graph?oldid=1096680615&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Petersen-as-Moore.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Moore_graph |
| is dbo:wikiPageRedirects of | dbr:Moore_bound |
| is dbo:wikiPageWikiLink of | dbr:Regular_graph dbr:Degree_diameter_problem dbr:Sierpiński_curve dbr:Complete_bipartite_graph dbr:Generalized_polygon dbr:Small-world_network dbr:Petersen_graph dbr:Edward_F._Moore dbr:Glossary_of_graph_theory dbr:Cop_number dbr:Cage_(graph_theory) dbr:McGee_graph dbr:McKay–Miller–Širáň_graph dbr:Distance-regular_graph dbr:Moore_neighborhood dbr:Alan_J._Hoffman dbr:Hoffman–Singleton_graph dbr:Strongly_regular_graph dbr:List_of_unsolved_problems_in_mathematics dbr:Tutte–Coxeter_graph dbr:Turán_graph dbr:Table_of_the_largest_known_graphs_of_a_given_diameter_and_maximal_degree dbr:Moore_bound |
| is dbp:properties of | dbr:Hoffman–Singleton_graph dbr:Tutte–Coxeter_graph |
| is foaf:primaryTopic of | wikipedia-en:Moore_graph |
