Størrelsesproblem - diameter

Størrelse-diameter- problemet er problemet med at finde den størst mulige graf (i form af størrelsen af dens toppunktsæt ) med en diameter , således at den største grad af ethvert toppunkt i grafen ikke overstiger [1] . Størrelsen af grafen er afgrænset ovenfra af Moore-grænsen . For og kun Petersen -grafen , Hoffman-Singleton-grafen og muligvis grafen med diameter og grad når Moore-grænsen. Generelt er de største grafer med grad/diameter-værdier meget mindre end Moore-grænsen. $G$ $V$ $k$ $G$ $d$ $G$ $1<k$ $2<d$ $k=2$ $d=57$

Vi studerer også problemet med at finde den størst mulige digraf , i stedet for graden af grafen, i dette tilfælde bruges graden af udfaldet [2] .

Formel

Lad være det maksimalt mulige antal grafens hjørnepunkter med en grad, der ikke overstiger , og diameter , så hvor er Moore-grænsen : ${\displaystyle n_{d,k))$ $d$ $k$ ${\displaystyle n_{d,k}\leq M_{d,k))$ ${\displaystyle M_{d,k))$

M_{d,k}={\begin{cases}1+d{\frac {(d-1)^{k}-1}{d-2}}&d\geqslant 2\\2k+1&d =2\end{sager}}

Denne grænse nås i meget sjældne tilfælde, så undersøgelsen gik i retning af, hvor tæt grafer eksisterer på Moore-grænsen.

Mængden kaldes graffejlen (her antallet af hjørner i grafen). En graf siges at have en lille defekt, hvis [3] . Der er en formodning om, at der for grader ikke er nogen -grafer med defekt 2. Man ved kun lidt om grafer med defekt større end 2 [4] . $\delta =M_{d,k}-|V|$ $|V|$ $\delta \leqslant d$ $d\geqslant 6$ $(d,2)$

For asymptotisk adfærd, bemærk at . $M_{d,k}=d^{k}+O(d^{k-1})$

For parameteren blev det formodet, at for alle ; ved hvad og hvad . ${\displaystyle \mu _{k}=\liminf _{d\to \infty }{\frac {n_{d,k}}{d^{k))))$ $\mu _{k}=1$ $k$ $\mu _{1}=\mu _{2}=\mu _{3}=\mu _{5}=1$ $\mu _{4}\geq 1/4$

MaxDDBS

Givet en forbundet værtsgraf[ klargør ] , en øvre grænse for graden og en øvre grænse for diameteren , søges den største undergraf i grafen med en maksimal grad, der ikke overstiger og en diameter, der ikke overstiger . Dette problem kaldes MaxDDBS, og det indeholder størrelse-diameter-problemet som et specialtilfælde (nemlig hvis vi tager en tilstrækkelig stor komplet graf som værtsgraf). Problemet er NP-hårdt . $G$ $d$ $k$ $S$ $G$ $d$ $k$

Noter

↑ Molodtsov, 2004 , s. 109.
↑ Miller, 2010 , s. 341.
↑ Miller, 2010 , s. 337.
↑ Miller, 2010 , s. 338.

Litteratur

Molodtsov S. G. Største grafer med diameter 2 og grad 6 // Diskret analyse og operationsforskning: Abstracts. - Novosibirsk, Akademgorodok: Institut for Matematik. S.L. Sobolev SO RAN, 2004. - Udgave. 28. juni - 2. juli 2004 . - S. 109 .
Bannai E., Ito T. Om Moore-grafer // J. Fac. sci. Univ. Tokyo Ser. A. - 1973. - T. 20 . — S. 191–208 .
Hoffman Alan J., Singleton Robert R. Moore grafer med diameter 2 og 3 // IBM Journal of Research and Development. - 1960. - V. 5 , no. 4 . — S. 497–504 . - doi : 10.1147/rd.45.0497 .
Singleton Robert R. Der er ingen uregelmæssig Moore-graf // American Mathematical Monthly . - 1968. - T. 75 , no. 1 . — S. 42–43 . - doi : 10.2307/2315106 . — .
Miller Mirka, Siran Jozef. Moore-grafer og videre: En undersøgelse af graden/diameterproblemet // Electronic Journal of Combinatorics . - 2005. - T. Dynamisk undersøgelse . — S. DS14 .
CombinatoricsWiki - Grad/diameterproblemet . (ubestemt)
Møller Mirka. En oversigt over grad/diameterproblemet for dirigerede, urettede og blandede grafer // Udvidede abstracts af IWONT. - Barcelona, 2010, 2010. - S. 335-346 .
Dekker A., Perez-Roses H., Pineda-Villavicencio G., Watters P. The Maximum Degree & Diameter-Bounded Subgraph and its Applications // Journal of Mathematical Modeling and Algorithms. - 2012. - doi : 10.1007/s10852-012-9182-8 .
Miller M., Perez-Roses H., Ryan J. Den maksimale grad og diameter afgrænset undergraf i nettet. Diskret anvendt matematik. - 2012. - doi : 10.1016/j.dam.2012.03.035 .