主题
Search

简单有向图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
SimpleDigraphs

简单有向图是没有重边或环的有向图（对应于对角线上为 0 的二进制邻接矩阵）。对于 n 个节点的简单有向图的数量，对于 n=1, 2, ... 分别是 1, 3, 16, 218, 9608, ... (OEIS A000273)，其由下式给出NumberOfDirectedGraphs[n] 在 Wolfram 语言 包中Combinatorica`。 n 个节点上的有向图可以枚举为ListGraphs[n,Directed] 在 Wolfram 语言 包中Combinatorica` .

具有 n 个节点的简单有向图可能具有 0 到 n(n-1) 条边。具有 n 个节点和 m 条边的简单有向图的数量可以由下式给出NumberOfDirectedGraphs[n, m] 在 Wolfram 语言 包中Combinatorica`。具有 n 个节点（行）和 m 条边（列）的图的三角形计数如下所示 (OEIS A052283)。

nm=0, 1, 2, ...
11
21, 1, 1
31, 1, 4, 4, 4, 1, 1
41, 1, 5, 13, 27, 38, 48, 38, 27, 13, 5, 1, 1

完全图，其中每条边都是双向的，称为完全有向图。没有对称有向边对（即，没有双向边）的有向图称为定向图。完全定向图（即，每对节点都由具有唯一方向的单条边连接的有向图）称为竞赛图。

多项式

d_p(x)=sum_(q)d_(pq)x^q
(1)

枚举了具有 p 个节点的不同简单有向图的数量（其中 g_(pq) 是具有 p 个节点和 q 条边的有向图的数量）可以通过应用 Pólya 枚举定理找到。这给出了具有 p 个点的有向图的计数多项式，如下所示

d_p(x)=Z(S_p^([2]),1+x),
(2)

其中 S_p^([2]) 是作用于 {1,2,...,p} 的 2-子集的缩减有序对群，由下式给出

Z(S_p^([2]))=1/(p!)sum_((j))(p!)/(product_(k=1)^(p)k^(j_k)j_k!)a_k^((k-1)j_k+2k(j_k; 2))product_(q=1)^pproduct_(r=q+1)^pa_(LCM(q,r))^(j_qj_rGCD(q,r))
(3)

(Harary 1994, p. 186)。这里，|_x_| 是向下取整函数，(n; m) 是二项式系数，LCM 是最小公倍数，GCD 是最大公约数，和 (j) 遍布循环指标的所有指数向量，并且 h_(j) 是 j_p 项的系数在 Z(S_p^([2])) 中。前几个循环指标 Z(S_p^([2])) 是

S_2^([2])=1/2a_1^2+1/2a_2
(4)
S_3^([2])=1/6a_1^6+1/2a_2^3+1/3a_3^2
(5)
S_4^([2])=1/(24)x_1^(12)+1/4x_2^5x_1^2+1/8x_2^6+1/3x_3^4+1/4x_4^3
(6)
S_5^([2])=1/(120)x_1^(20)+1/(12)x_2^7x_1^6+6/x_3^6x_1^2+1/8x_2^(10)+1/4x_4^5+1/5x_5^4+1/6x_2x_3^2x_6^2.
(7)

设置 a_n=1+x^n 给出具有 n 个节点和 k 条边的有向图数量的生成函数，

d_1=x
(8)
d_2=x^2+x+1
(9)
d_3=x^6+x^5+4x^4+4x^3+4x^2+x+1.
(10)

参见

无环有向图, 有向图, 定向图, 简单图, 强连通有向图, 竞赛图, 弱连通有向图

使用 Wolfram|Alpha 探索

参考文献

Harary, F. "Digraphs." Ch. 16 in 图论。 Reading, MA: Addison-Wesley, pp. 10, 186, and 198-211, 1994.Sloane, N. J. A. 序列 A000273/M3032 和 A052283，收录于“整数数列线上大全”。

在 Wolfram|Alpha 上引用

简单有向图

请引用为

Weisstein, Eric W. "简单有向图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/SimpleDirectedGraph.html

学科分类