主题
Search

度序列

给定一个 无向图，度序列是其 图的顶点 的 顶点度数 （化合价）的单调非增序列。给定阶数的图的度序列数量与 图划分 密切相关。由于每条边连接两个顶点，因此被计算两次，所以图的度序列的元素之和始终为偶数（Skiena 1990，第 157 页）。

图 G 中的最小顶点度表示为 delta(G)，最大顶点度表示为 Delta(G) (Skiena 1990, p. 157)。度序列仅包含单个整数的多个副本的图称为正则图。可以使用 Wolfram 语言 构建与给定度序列 d 对应的图，使用RandomGraph[DegreeGraphDistribution[d]]。

GraphicalPartitions22211

拓扑结构不同的图可能具有相同的度序列。此外，两个不同的凸多面体甚至可以具有相同的骨架度序列，例如 三角锥 和 三侧锥十二面体 约翰逊多面体，它们都具有 8 个面，9 个顶点，15 条边，以及度序列 (3, 3, 3, 3, 3, 3, 4, 4, 4)。

具有唯一度序列的图可以称为单图或“唯一图”（Tyshkevich 2000，Barrus等人 2023）。

对于 n=1, 2, ... 个节点的图，不同的度序列的数量由 1, 2, 4, 11, 31, 102, 342, 1213, 4361, ... 给出 (OEIS A004251)，而具有 n 个图的顶点的非同构简单无向图的总数为 1, 2, 4, 11, 34, 156, 1044, ... (OEIS A000088)。因此，度序列数量少于非同构图数量的第一个阶数为 n=5。对于上面说明的图，度序列在下表中给出。

1{0}
2{0,0}, {1,1}
3{0,0,0}, {1,1,0}, {2,1,1}, {2,2,2}
4{0,0,0,0}, {1,1,0,0}, {2,1,1,0}, {2,2,2,0},
{3,2,2,1}, {3,3,2,2}, {3,3,3,3}, {1,1,1,1},
{2,2,1,1}, {2,2,2,2}, {3,1,1,1}

阶数为 n 的度序列的元素可能总和为 0, 2, 4, 6, ..., n(n-1)。

如果存在一些与度序列对应的 k-连通图，则度序列被称为 k-连通的。例如，虽然度序列 {1,2,1} 是 1-连通但不是 2-连通的，{2,2,2} 是 2-连通的。

另请参阅

度集合, 可图序列, 图划分, k-连通图, 正则图, 单图, 不可交换图, 顶点度

使用 Wolfram|Alpha 探索

参考文献

Barrus, M. D.; Trenk, A. N.; 和 Whitman, R. "单图的遗传闭包。" 2023 年 8 月 23 日。 https://arxiv.org/abs/2308.12190Ruskey, F. "关于度序列的信息。" http://www.theory.csc.uvic.ca/~cos/inf/nump/DegreeSequences.html。Ruskey, F.; Cohen, R.; Eades, P.; 和 Scott, A. "寻找好住所的 Alley CATs。" Congres. Numer. 102, 97-110, 1994.Skiena, S. "实现度序列。" §4.4.2 在 实现离散数学：使用 Mathematica 的组合数学和图论。 Reading, MA: Addison-Wesley, pp. 157-160, 1990.Sloane, N. J. A. 序列 A004251/M1250 在 "整数序列在线百科全书" 中。Tyshkevich, R. "图序列和单图的分解。" Disc. Math. 220, 201-238, 2000.

在 Wolfram|Alpha 上引用

度序列

请引用本文为

Weisstein, Eric W. "度序列。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/DegreeSequence.html

主题分类