主题
Search

正则图

下载 Mathematica 笔记本下载 Wolfram 笔记本

如果一个 图 的所有 局部度数 都是相同的数字 r，则称该图为度为 r 的正则图。0-正则图是空图，1-正则图由不连通的边组成，而2-正则图由一个或多个（不连通的）环组成。因此，第一个有趣的例子是 3-正则图，称为立方图 (Harary 1994, pp. 14-15)。最常见的是，“立方图”用来表示“连通立方图”。请注意，n-弧传递图 有时也称为 “n-正则图” (Harary 1994, p. 174)。

在一个顶点数为奇数的图中，如果除一个顶点的度数为 delta+1 外，每个顶点的度数都是相同的奇数 delta，则该图可以称为准正则图 (Bozóki et al. 2020)。

可以使用以下方法生成半随机 (k,n)-正则图：RegularGraph[k, n] 在 Wolfram 语言 包中Combinatorica` .

下表列出了低阶 d-正则图的名称。

dd-正则图的名称
3立方图
4四次图
5五次图
6六次图
7七次图
8八次图

下表总结了一些度数大于 5 的正则图。

rr-正则图
6Gray 配置的门格尔对偶, 一半 Foster 图, Hoffman-Singleton 图 减星, Kummer 图, Perkel 图, Reye 图, Shrikhande 图, 16-胞图
7双重截断 Witt 图, Hoffman-Singleton 图 的二部双图, Hoffman-Singleton 图, Klein 图
824-胞图, 正二十面体图的线图
10Conway-Smith 图, Gewirtz 图 的二部双图, Gewirtz 图, Hall-Janko 近似八边形
12Hoffman-Singleton 图的线图, 正二十面体图补图与全 1 矩阵 J_2 的克罗内克积, 600-胞图
14Klein 图的距离-2 图, U_3(3) 图
15截断 Witt 图
16M_(22) 图的二部双图, M_(22) 图, Schläfli 图
20Brouwer-Haemers 图, Petersen 线图补图与全 1 矩阵 J_2 的克罗内克积
22Higman-Sims 图的二部双图, Higman-Sims 图
27Gosset 图
30大型 Witt 图
36Hall-Janko 图
42Hoffman-Singleton 图补图
56局部 McLaughlin 图
100G_2(4) 图
112McLaughlin 图
416Suzuki 图
RegularConnectedGraphs

阶数为 n=1, 2, ... 的非同构连通正则图的数量为 1, 1, 1, 2, 2, 5, 4, 17, 22, 167, ... (OEIS A005177; Steinbach 1990)。

对于一个有 n 个节点的 r-正则图，

m=1/2nr,

其中 m 是边数。令 N(n,r) 表示有 n 个顶点的连通 r-正则图的数量。那么 0<=r<=n-1, N(n,r)=N(n,n-1-r), 并且当 n 和 r 都是奇数时，N(n,r)=0。Zhang 和 Yang (1989) 给出了 N(p,r)，其中 p<=12，Meringer 提供了类似的表格，包括低阶的完整枚举。

下表给出了节点数 n 较小时的连通 r-正则图的数量 N(n,r) (Meringer 1999, Meringer)。

SloaneA002851A006820A006821A006822A014377A014378A014381A014382A014384
类别cubicquarticquinticsexticsepticoctic
nN(n,3)N(n,4)N(n,5)N(n,6)N(n,7)N(n,8)N(n,9)N(n,10)N(n,11)N(n,12)
41000000000
50100000000
62110000000
70201000000
85631100000
901604010000
1019596021511000
1102650266060100
12851544784878491547949110
13010778036786001078601001
145098816834593832160930021609301345938688193540131
15080549101470293675014702936760805579017
16406080374182585136675258513674180377964207
17086221634000086223660
1841301985870522
1900000
20510489
2100000
227319447
2300000
24117940535
2500000
262094480864
nN(n,13)N(n,14)N(n,15)N(n,16)N(n,17)N(n,18)N(n,19)N(n,20)N(n,21)N(n,22)
130000000000
141000000000
150100000000
1621110000000
1702501000000
1898588387342110331100000
190039010000
205163444911000
21000600100
22737392473110
2300008801
241185735921101
2500000130
262103205738

通常，只发布 r<n/2 时，在 n 个顶点上的连通 r-正则图的数量，这是因为所有其他数量都可以通过简单的组合数学推导出来，基于以下事实：

1. 在 n 个顶点上的非必要连通 r-正则图的数量可以从在 m<=n 个顶点上的连通 r-正则图的数量中获得。

2. 在 n 个顶点上的非必要连通 r-正则图的数量等于在 n 个顶点上的非必要连通 (n-r-1)-正则图的数量（因为构建互补图定义了两个集合之间的双射）。

3. 对于 r>n/2，在 n 个顶点上不存在任何不连通的 r-正则图。

RegularGraphs

上面说明的，具有 n 个节点的非同构非必要连通正则图的数量为 1, 2, 2, 4, 3, 8, 6, 22, 26, 176, ... (OEIS A005176; Steinbach 1990)。

另请参阅

(0,2)-Graph, Cage Graph, Complete Graph, Completely Regular Graph, Configuration, Cubic Graph, Distance-Regular Graph, Irregular Graph, Local Degree, Moore Graph, Octic Graph, Quartic Graph, Quasi-Regular Graph, Quintic Graph, Septic Graph, Sextic Graph, Strongly Regular Graph, Superregular Graph, Two-Regular Graph, Weakly Regular Graph

此条目的部分内容由 Markus Meringer 贡献

使用 探索

WolframAlpha

更多尝试

参考文献

Bozóki S.; Szadoczki1, Z.; and Tekile, H. A. "Filling in Pattern Designs for Incomplete Pairwise Comparison Matrices: (Quasi-)Regular Graphs With Minimal Diameter." 13 May 2020. https://arxiv.org/abs/2006.01127.Chartrand, G. Introductory Graph Theory. New York: Dover, p. 29, 1985.Colbourn, C. J. and Dinitz, J. H. (Eds.). CRC Handbook of Combinatorial Designs. Boca Raton, FL: CRC Press, p. 648, 1996.Comtet, L. "Asymptotic Study of the Number of Regular Graphs of Order Two on N." §7.3 in Advanced Combinatorics: The Art of Finite and Infinite Expansions, rev. enl. ed. Dordrecht, Netherlands: Reidel, pp. 273-279, 1974.Faradzev, I. A. "Constructive Enumeration of Combinatorial Objects." In Problèmes combinatoires et théorie des graphes (Orsay, 9-13 Juillet 1976). Colloq. Internat. du C.N.R.S. Paris: Centre Nat. Recherche Scient., pp. 131-135, 1978.Gropp, H. "Enumeration of Regular Graphs 100 Years Ago." Discrete Math. 101, 73-85, 1992.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 14 and 62, 1994.Meringer, M. "Connected Regular Graphs." http://www.mathe2.uni-bayreuth.de/markus/reggraphs.html#CRG.Meringer, M. "Fast Generation of Regular Graphs and Construction of Cages." J. Graph Th. 30, 137-146, 1999.Petersen, J. "Die Theorie der regulären Graphs." Acta Math. 15, 193-220, 1891.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, 1998.Sachs, H. "On Regular Graphs with Given Girth." In Theory of Graphs and Its Applications: Proceedings of the Symposium, Smolenice, Czechoslovakia, 1963 (Ed. M. Fiedler). New York: Academic Press, 1964.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 159, 1990.Sloane, N. J. A. Sequences A005176/M0303, A005177/M0347, A006820/M1617, A006821/M3168, A006822/M3579, A014377, A014378, A014381, A014382, A014384, and A051031 in "The On-Line Encyclopedia of Integer Sequences."Steinbach, P. Field Guide to Simple Graphs. Albuquerque, NM: Design Lab, 1990.Wormald, N. "Generating Random Regular Graphs." J. Algorithms 5, 247-280, 1984.Zhang, C. X. and Yang, Y. S. "Enumeration of Regular Graphs." J. Dailan Univ. Tech. 29, 389-398, 1989.

在 中被引用

正则图

引用为

Meringer, Markus 和 Weisstein, Eric W. “正则图。”来自 —— 资源。 https://mathworld.net.cn/RegularGraph.html

主题分类