主题
Search

标记图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
LabeledGraphTypes

一个标记图 G=(V,E) 是一个有限序列的 图顶点 V，带有一组 图边 E，它是 V 的2-子集。给定一个 图顶点 集合 V_n={1,2,...,n}，顶点标记图的数量由 2^(n(n-1)/2) 给出。如果存在一个 置换 p，使得 {u,v} 在 图边 E(G) 集合中当且仅当 {p(u),p(v)} 在 图边 E(H) 集合中，则称两个图 G 和 H 具有 图顶点 V_n={1,2,...,n} 是 同构的。

LabeledGraphs

当不加限定地使用术语“标记图”时，它指的是每个节点都以不同方式（但任意地）标记的图，因此出于枚举的目的，所有节点都被认为是不同的。对于 n=1, 2, ...，总数（不一定连通）的标记 n 节点图由 1, 2, 8, 64, 1024, 32768, ... 给出 (OEIS A006125; 如上所示)，而 n 节点上的连通标记图的数量由前述序列的 对数变换 给出，为 1, 1, 4, 38, 728, 26704, ... (OEIS A001187; Sloane 和 Plouffe 1995, p. 19)。

所有 n=1, 2, ... 阶的标记图中图顶点的数量为 1, 4, 24, 256, 5120, 196608, ... (OEIS A095340)，其中边的数量为 0, 1, 12, 192, 5120, 245760, ... (OEIS A095351)，后者具有闭式形式

e(n)=n(n-1)2^(n(n-1)/2-2).

参见

15 拼图, A-亲切图, 连通图, 亲切图, 边优美图, 优雅图, 公平图, 优美图, 图, h-亲切图, 调和图, 标记有向图, 标记树, 幻图, 定向图, 泰勒条件, 未标记图, 加权树

使用 Wolfram|Alpha 探索

参考文献

Cahit, I. "图标记问题和新结果的主页。" http://www.emu.edu.tr/~cahit/CORDIAL.htm.Gallian, J. "图标记动态调查。" Elec. J. Combin. DS6. 2018年12月21日。 https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gilbert, E. N. "标记图的枚举。" Canad. J. Math. 8, 405-411, 1956.Harary, F. "标记图。" 图论。 Reading, MA: Addison-Wesley, pp. 10 和 178-180, 1994.Harary, F. 和 Palmer, E. M. "标记枚举。" Ch. 1 in 图形枚举。 New York: Academic Press, pp. 1-31, 1973.Sloane, N. J. A. 序列 A001187/M3671, A006125/M1897, A095340 和 A095351，在 "整数序列在线百科全书" 中。Sloane, N. J. A. 和 Plouffe, S. 整数序列百科全书。 San Diego, CA: Academic Press, 1995.

在 Wolfram|Alpha 上被引用

标记图

以此引用

Weisstein, Eric W. "标记图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/LabeledGraph.html

主题分类