| dbo:abstract
|
- In graph theory, the degree diameter problem is the problem of finding the largest possible graph G (in terms of the size of its vertex set V) of diameter k such that the largest degree of any of the vertices in G is at most d. The size of G is bounded above by the Moore bound; for 1 < k and 2 < d only the Petersen graph, the Hoffman-Singleton graph, and possibly one more graph (not yet proven to exist) of diameter k = 2 and degree d = 57 attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound. (en)
- グラフ理論において次数直径問題とは、最大次数がdで直径がkのグラフのうち頂点数が最大となるグラフGを見つけよ、というものだ。Gの頂点数はムーア・バウンドによって上から抑えられる。1<kで2<dのときムーアバウンドに一致するグラフ（ムーアグラフ）で構成できているものはピーターセングラフとホフマンシングルトングラフである。k=2でd=57のときにムーアバウンドに一致するグラフが存在しうるが、いまだ構成されておらず未解決の問題である。一般的に最大次数と直径が与えられたときの最大頂点数はムーアバウンドよりも小さくなる。 (ja)
- Проблема размера — диаметра — задача поиска наибольшего возможного графа (в терминах размера множества его вершин ) диаметра такого, что наибольшая степень любой вершины в графе не превосходит . Размер графа ограничен сверху границей Мура. Для и только граф Петерсена, граф Хоффмана — Синглтона и, возможно, граф с диаметром и степенью достигают границу Мура. В общем случае наибольшие графы со значениями степень/диаметр имеют размер, много меньший границы Мура. Изучается также задача поиска наибольшего возможного орграфа, вместо степени графа в этом случае используется полустепень исхода. (ru)
- 度-直徑問題是圖論中一個問題，目的在定下最大直徑k及最大度數d後，找出擁有最多節點的圖。 假設圖以表示，某節點的度數以表示，節點之間的最短距離以表示，則度-直徑問題是規定了 求出圖G。G的大小（以節點數衡量）受制於，亦即節點的數目不可能多於 已知在k > 1和d > 2的情況下，只有佩特森圖和Hoffman-Singleton圖，以及一個k=2、d=57的圖能達到摩爾上限，一般情況下，圖的節點數目遠少於摩爾上限所指定。 (zh)
- Зада́ча сте́пеня — діа́метра — задача пошуку найбільшого можливого графа (в термінах розміру множини його вершин ) діаметром такого, що найбільший степінь будь-якої вершини в графі не перевищує . Розмір графа обмежений зверху межею Мура. Для і тільки граф Петерсена, граф Гофмана — Синглтона і, можливо, граф із діаметром і степенем досягають межі Мура. В загальному випадку графи з найбільшими значеннями степінь/діаметр мають розмір, значно менший від межі Мура. Вивчається також задача пошуку найбільшого можливого орграфа, замість степеня графа в цьому випадку використовують напівстепень виходу. (uk)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3544 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In graph theory, the degree diameter problem is the problem of finding the largest possible graph G (in terms of the size of its vertex set V) of diameter k such that the largest degree of any of the vertices in G is at most d. The size of G is bounded above by the Moore bound; for 1 < k and 2 < d only the Petersen graph, the Hoffman-Singleton graph, and possibly one more graph (not yet proven to exist) of diameter k = 2 and degree d = 57 attain the Moore bound. In general, the largest degree-diameter graphs are much smaller in size than the Moore bound. (en)
- グラフ理論において次数直径問題とは、最大次数がdで直径がkのグラフのうち頂点数が最大となるグラフGを見つけよ、というものだ。Gの頂点数はムーア・バウンドによって上から抑えられる。1<kで2<dのときムーアバウンドに一致するグラフ（ムーアグラフ）で構成できているものはピーターセングラフとホフマンシングルトングラフである。k=2でd=57のときにムーアバウンドに一致するグラフが存在しうるが、いまだ構成されておらず未解決の問題である。一般的に最大次数と直径が与えられたときの最大頂点数はムーアバウンドよりも小さくなる。 (ja)
- 度-直徑問題是圖論中一個問題，目的在定下最大直徑k及最大度數d後，找出擁有最多節點的圖。 假設圖以表示，某節點的度數以表示，節點之間的最短距離以表示，則度-直徑問題是規定了 求出圖G。G的大小（以節點數衡量）受制於，亦即節點的數目不可能多於 已知在k > 1和d > 2的情況下，只有佩特森圖和Hoffman-Singleton圖，以及一個k=2、d=57的圖能達到摩爾上限，一般情況下，圖的節點數目遠少於摩爾上限所指定。 (zh)
- Проблема размера — диаметра — задача поиска наибольшего возможного графа (в терминах размера множества его вершин ) диаметра такого, что наибольшая степень любой вершины в графе не превосходит . Размер графа ограничен сверху границей Мура. Для и только граф Петерсена, граф Хоффмана — Синглтона и, возможно, граф с диаметром и степенью достигают границу Мура. В общем случае наибольшие графы со значениями степень/диаметр имеют размер, много меньший границы Мура. (ru)
- Зада́ча сте́пеня — діа́метра — задача пошуку найбільшого можливого графа (в термінах розміру множини його вершин ) діаметром такого, що найбільший степінь будь-якої вершини в графі не перевищує . Розмір графа обмежений зверху межею Мура. Для і тільки граф Петерсена, граф Гофмана — Синглтона і, можливо, граф із діаметром і степенем досягають межі Мура. В загальному випадку графи з найбільшими значеннями степінь/діаметр мають розмір, значно менший від межі Мура. (uk)
|
| rdfs:label
|
- Degree diameter problem (en)
- 次数直径問題 (ja)
- Проблема размера — диаметра (ru)
- 度-直徑問題 (zh)
- Задача степеня — діаметра (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |