Fokszám-átmérő probléma

A matematika, azon belül a gráfelmélet területén az 1960-as évek óta vizsgált fokszám-átmérő probléma (degree diameter problem) vagy (∆,D)-probléma annak a V csúcshalmaz mérete szerinti lehető legnagyobb G gráf megkeresésének problémája, melynek átmérője k, fokszáma pedig legfeljebb d. A G méretének felső korlátját a Moore-gráfok adják; 1 < k és 2 < d paraméterek mellett csak a Petersen-gráf, a Hoffman–Singleton-gráf és létezése esetén egy k = 2 átmérőjű és d = 57 fokszámú gráf éri el a Moore-korlátot. Általában a legnagyobb, adott fokszámú és átmérőjű gráfok sokkal kisebbek a Moore-korlátnál.

Képlet

Ha $n_{d,k}$ az adott d fokszám és k átmérő mellett elérhető maximális csúcsszám, akkor $n_{d,k}\leq M_{d,k}$, ahol $M_{d,k}$ a Moore-korlát:

$M_{d,k}={\begin{cases}1+d{\frac {(d-1)^{k}-1}{d-2}}&{\text{ ha }}d>2\\2k+1&{\text{ ha }}d=2\end{cases}}$

Az egyenlőség nagyon kevés gráf esetében teljesül, ezért inkább azt érdemes vizsgálni, hogy a Moore-korláthoz mennyire közel létezhetnek gráfok. Vizsgálták a (∆, D, −δ)-gráfokat, tehát a legfeljebb D átmérőjű, ∆ maximális fokszámú gráfok, melyek δ defektussal maradnak el a Moore-korláttól – elsősorban a −1 és −2 defektusokat.

Az aszimptotikus viselkedés vizsgálatához megjegyzendő, hogy $M_{d,k}=d^{k}+O(d^{k-1})$.

Különböző gráfosztályok

A fokszám-átmérő problémát irányítatlan gráfok mellett irányított gráfokon és vegyes gráfokon is megvizsgálták.

Irányítatlan gráfok

Az irányítatlan gráfokon belül a következő gráfosztályokat vizsgálták meg: csúcstranzitív gráfok, Cayley-gráfok, Abel-csoportok Cayley-gráfjai; páros gráfok; különböző felületekbe ágyazott (síkbarajzolható, tóruszra rajzolható) gráfok.

Irányított gráfok

Irányított gráfok esetében csak triviális (d=1 vagy k=1) Moore-digráfok léteznek.

Az irányított gráfokon belül a következő gráfosztályokat vizsgálták meg: csúcstranzitív gráfok, Cayley-gráfok; síkbarajzolható gráfok.

Vegyes gráfok

Az irányított, illetve irányítatlan Moore-gráfok felfoghatók az általánosabb vegyes („részben irányított”) Moore-gráfok speciális eseteiként.

Kapcsolódó problémák

Bollobás hasonló jellegű problémát vetett fel: adott átmérő és maximális fokszám mellett keressük meg a lehetséges legkevesebb élű gráfot. Gómez és Escudero megvizsgálták az olyan gráfok konstruálásának lehetőségeit, melyek sok csúccsal, adott D átmérővel és ∆ maximális fokszámmal rendelkeznek, továbbá éleiket pontosan p színnel lehet színezni. Táblázatukban megadják az ilyen irányított gráfokat a D ≤ 10 és p ≤ 16 esetekre.

• Fokszám/bőség probléma: adott d > 2 és g > 3 természetes számokra keressük meg a legkevesebb csúcsú reguláris gráfot, melynek fokszáma d, girthparamétere (bősége) g.
• Rend/fokszám probléma: adott n és ∆ természetes számok, keressük meg a lehetséges legkisebb D_n,∆ átmérőt egy n rendű és ∆ maximális fokszámú gráfban.
• Rend/átmérő probléma: adott n és D természetes számok, keressük meg a lehetséges legkisebb ∆_n,D maximális fokszámot egy n rendű és D átmérőjű gráfban.

A fenti problémák irányított változatában fokszám helyett ki-fokszám szerepel.

• adott n, D, D′ és s, határozzuk meg az n csúcsú, D átmérőjű gráf éleinek minimális számát, ha tudjuk, hogy a gráfból s vagy kevesebb él eltávolítása után legfeljebb D′ átmérőjű gráfot kapunk
• MaxDDBS probléma: adott irányítatlan összefüggő G gráf, keressük a legnagyobb összefüggő S részgráfot, melynek maximális fokszáma ≤ ∆ és átmérője ≤ D. Kellően nagy teljes gráfot választva G-nek látható, hogy ennek a problémának egyik speciális esete a fokszám-átmérő probléma.

Ismert korlátok

Az irányítatlan fokszám-átmérő probléma legnagyobb ismert gráfjainak rendjei

Keressük az adott maximális fokszám és átmérő mellett lehetséges legnagyobb irányítatlan gráf csúcsainak számát (rendjét). A Moore-korlát felső határt szab a csúcsok számának, de a matematikusok ennél precízebb választ keresnek. Az alábbi táblázat bemutatja a probléma jelenlegi állását (nem számítva a 2 fokszám esetét, ahol a legnagyobb gráfok a páratlan számú csúcsból álló körök, és a triviális ∆ = 1, D = 1 esetet).

Az alábbi táblázatban találhatók a legnagyobb (2008 októberében) ismert gráfok csúcsszámai az irányítatlan fokszám-átmérő problémára, 3 ≤ d ≤ 16 fokszámra és 2 ≤ k ≤ 10 átmérőre. A táblázatban csak néhány gráf optimális (aláhúzással jelölve), tehát a lehetséges legnagyobb. A többi szám csak az eddig felfedezett legnagyobb gráfot jelenti, tehát a Moore-korláthoz közelebb álló, nagyobb gráf keresése ezeknél nyitott kérdés. A táblázat d és k értékein kívül eső számokra is ismertek konstrukciók.

k d	2	3	4	5	6	7	8	9	10
3	10	20	38	70	132	196	336	600	1250
4	15	41	96	364	740	1 320	3 243	7 575	17 703
5	24	72	210	624	2 772	5 516	17 030	57 840	187 056
6	32	110	390	1404	7 917	19 383	76 461	307 845	1 253 615
7	50	168	672	2 756	11 988	52 768	249 660	1 223 050	6 007 230
8	57	253	1 100	5 060	39 672	131 137	734 820	4 243 100	24 897 161
9	74	585	1 550	8 200	75 893	279 616	1 686 600	12 123 288	65 866 350
10	91	650	2 286	13 140	134 690	583 083	4 293 452	27 997 191	201 038 922
11	104	715	3 200	19 500	156 864	1 001 268	7 442 328	72 933 102	600 380 000
12	133	786	4 680	29 470	359 772	1 999 500	15 924 326	158 158 875	1 506 252 500
13	162	851	6 560	40 260	531 440	3 322 080	29 927 790	249 155 760	3 077 200 700
14	183	916	8 200	57 837	816 294	6 200 460	55 913 932	600 123 780	7 041 746 081
15	186	1 215	11 712	76 518	1 417 248	8 599 986	90 001 236	1 171 998 164	10 012 349 898
16	198	1 600	14 640	132 496	1 771 560	14 882 658	140 559 416	2 025 125 476	12 951 451 931

A táblázat színkódjait a következőképpen lehet értelmezni:

Szín	Részletek
*	A Petersen- és a Hoffman–Singleton-gráf.
*	Optimális gráfok, melyek nem Moore-gráfok.
*	James Allwright által megtalált gráf.
*	G. Wegner által megtalált gráf.
*	Graphs found by Geoffrey Exoo által megtalált gráf.
*	Brendan D. McKay, Mirka Miller és Jozef Širáň által megtalált gráfcsalád. További részletek a szerzők tanulmányában.
*	J. Gómez által megtalált gráf.
*	Mitjana M. és Francesc Comellas által megtalált gráf. Tőlük függetlenül Michael Sampels is megtalálta.
*	Fiol, M.A. és Yebra, J.L.A által megtalált gráf.
*	Francesc Comellas és J. Gómez által megtalált gráf.
*	Brendan D. McKay, Mirka Miller és Jozef Širáň által megtalált gráfcsalád. További részletek a szerzők tanulmányában.
*	Eyal Loz által megtalált gráfok. További részletek Eyal Loz és Jozef Širáň tanulmányában.
*	Michael Sampels által megtalált gráfok.
*	Michael J. Dinneen és Paul Hafner által megtalált gráfok. További részletek a szerzők tanulmányában.
*	Marston Conder által megtalált gráf.

Az irányított fokszám-átmérő probléma legnagyobb ismert csúcsszimmetrikus gráfjainak rendjei

Az alábbi táblázatban találhatók a legnagyobb (2008 októberében) ismert gráfok csúcsszámai az irányított fokszám-átmérő problémára, a csúcstranzitív digráfokra szűkítve, 2 ≤ d ≤ 13 fokszámra és 2 ≤ k ≤ 11 átmérőre.

k d	2	3	4	5	6	7	8	9	10	11
2	6	10	20	27	72	144	171	336	504	737
3	12	27	60	165	333	1 152	2 041	5 115	11 568	41 472
4	20	60	168	465	1 378	7 200	14 400	42 309	137 370	648 000
5	30	120	360	1 152	3 775	28 800	86 400	259 200	1 010 658	5 184 000
6	42	210	840	2 520	9 020	88 200	352 800	1 411 200	5 184 000	27 783 000
7	56	336	1 680	6 720	20 160	225 792	1 128 960	5 644 800	27 783 000	113 799 168
8	72	504	3 024	15 120	60 480	508 032	3 048 192	18 289 152	113 799 168	457 228 800
9	90	720	5 040	30 240	151 200	1 036 800	7 257 600	50 803 200	384 072 192	1 828 915 200
10	110	990	7 920	55 400	332 640	1 960 200	15 681 600	125 452 800	1 119 744 000	6 138 320 000
11	132	1 320	11 880	95 040	665 280	3 991 680	31 152 000	282 268 800	2 910 897 000	18 065 203 200
12	156	1 716	17 160	154 440	1 235 520	8 648 640	58 893 120	588 931 200	6 899 904 000	47 703 427 200
13	182	2 184	24 024	240 240	2 162 160	17 297 280	121 080 960	1 154 305 152	15 159 089 098	115 430 515 200

A táblázat színkódjait a következőképpen lehet értelmezni:

Szín	Részletek
*	W.H.Kautz által megtalált gráfcsalád. További részletek a szerző tanulmányában.
*	V.Faber és J.W.Moore által megtalált gráfcsalád. További részletek más szerzőktől is hozzáférhetők.
*	V.Faber és J.W.Moore által megtalált gráf. A rendhez tartozó összes Cayley-digráfot Eyal Loz találta meg.
*	Francesc Comellas és M. A. Fiol által megtalált digráfok. További részletek a szerzők tanulmányában.
*	Michael J. Dinneen által megtalált Cayley-digráfok. További részletek a szerző tanulmányában.
*	Michael J. Dinneen által megtalált Cayley-digráfok. A rendhez tartozó összes Cayley-digráfot Eyal Loz találta meg.
*	Paul Hafner által megtalált Cayley-digráfok. További részletek a szerző tanulmányában.
*	Paul Hafner által megtalált Cayley-digráfok. A rendhez tartozó összes Cayley-digráfot Eyal Loz találta meg.
*	J. Gómez által megtalált digráfok.
*	Eyal Loz által megtalált Cayley-digráfok. További részletek Eyal Loz és Jozef Širáň tanulmányában.

Kapcsolódó szócikkek

• Cage (gráfelmélet)
• Részgráf fokszám-átmérő problémája (MaxDDBS)

Fordítás

• Ez a szócikk részben vagy egészben a Degree diameter problem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
• Ez a szócikk részben vagy egészben a Table of the largest known graphs of a given diameter and maximal degree című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
• Ez a szócikk részben vagy egészben a Table of vertex-symmetric digraphs című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

• Bannai, E. & Ito, T. (1973), "On Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208

• Hoffman, Alan J. & Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, doi:10.1147/rd.45.0497, <http://www.research.ibm.com/journal/rd/045/ibmrd0405H.pdf>

• Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly (Mathematical Association of America) 75 (1): 42–43, DOI 10.2307/2315106

• CombinatoricsWiki - The Degree/Diameter Problem, <http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem>

• J. Dinneen, Michael & Hafner, Paul R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, DOI 10.1002/net.3230240702

• McKay, Brendan D.; Miller, Mirka & Širáň, Jozef (1998), "A note on large graphs of diameter two and given maximum degree", Journal of Combinatorial Theory Series B 74 (4): 110–118, doi:10.1006/jctb.1998.1828, <http://portal.acm.org/citation.cfm?id=299331>

• Pineda-Villavicencio, Guillermo; Gómez, José & Miller, Mirka et al. (2006), "New Largest Graphs of Diameter 6", Electronic Notes in Discrete Mathematics 24: 153–160, DOI 10.1016/j.endm.2006.06.044

• Loz, Eyal & Širáň, Jozef (2008), "New record graphs in the degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80, <http://ajc.maths.uq.edu.au/pdf/41/ajc_v41_p063.pdf>

• Kautz, W.H. (1969), "Design of optimal interconnection networks for multiprocessors", Architecture and Design of Digital Computers, Nato Advanced Summer Institute: 249–272

• Faber, V. & Moore, J.W. (1988), "High-degree low-diameter interconnection networks with vertex symmetry:the directed case", Technical Report LA-UR-88-1051, Los Alamos National Laboratory

• Comellas, F. & Fiol, M.A. (1995), "Vertex-symmetric digraphs with small diameter", Discrete Applied Mathematics 58 (1): 1–12, DOI 10.1016/0166-218X(93)E0145-O

• Miller, Mirka & Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics, Dynamic survey D, <http://www.combinatorics.org/Surveys/ds14.pdf>. Hozzáférés ideje: 2017-03-29 Archiválva 2012. január 18-i dátummal a Wayback Machine-ben

További információk

• Vertex-symmetric Digraphs online table.
• The Degree - Diameter Problem on CombinatoricsWiki.org.
• Eyal Loz's Degree-Diameter problem page.