主题
Search

图兰图

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本
TuranGraph

图兰图，有时被称为极大饱和图（Zykov 1952，Chao 和 Novacky 1982），具有正整数参数 n 和 k，是由图兰 (Turán) (1941) 最初考虑的一种 极图，其顶点数为 n。不幸的是，对于指标 k，存在两种不同的约定。

在更标准的术语（以及此处采用的术语）中，(n,k)-图兰图，有时也称为 K-图，并且有多种不同的表示方法，如 T(n,k)、 T_(n,k) (Gross 和 Yellen 2006, p. 476)、 D(n,k) (Chao 和 Novacky 1982) 或 T_k(n) (Pach 和 Agarwal 1995, p. 120)，是指在 n 个 图顶点 上的 极图，且对于 1<=k<=n，它不包含 (k+1)-团 (Chao 和 Novacky 1982；Diestel 1997, p. 149；Bollobás 1998, p. 108)。换句话说，图兰图在所有不包含 完全图 K_(k+1) 的 n 顶点图中，具有最大可能的 图边 数。图兰图也是在 n 个顶点上的完全 k 部图，其各部分的顶点数尽可能相等 (Gross 和 Yellen 2006, p. 476)。

不幸的是，包括 Skiena (1990, pp. 143-144)、Aigner (1995) 以及 Pemmaraju 和 Skiena (2003, pp. 247-248) 在内的一些作者，使用 (n,k)-图兰图不包含 k-团（而不是 (k+1)-团）的约定，这意味着这些作者的 T(n,k)-图兰图是上述定义的 (n,k-1)-图兰图。

在 n 个顶点上不包含 完全图 K_(k+1) 的图兰图可以使用 Wolfram 语言 生成，命令如下：TuranGraph[n, k]，预计算属性可以使用以下命令获取：GraphData[{"Turan", {n, k}}].

图兰图可以通过将 图顶点 集 {1,...,n} 分成 k 个两两不相交的子集来获得，这些子集具有 图顶点，其度数分别为 n_1, ..., n_k，满足

n=n_1+...+n_k,
(1)

并且当且仅当两个 图顶点 位于不同的 图顶点 集中时，它们是连接的。这样的 图 有时表示为 K_(n_1,...,n_k)。

它们可以直接通过对顶点进行编号 0, 1, ..., n-1 并连接顶点来构造，当且仅当顶点模 k 不同余时（König 1936，Chao 和 Novacky 1982）。

图兰定理 给出了 (n,k)-图兰图的边数 t(n,k)，如下所示：

t(n,k)=|_((k-1)n^2)/(2k)_|,
(2)

其中 |_x_| 表示 向下取整函数。这给出了三角形

0 0 1 0 2 3 0 4 5 6 0 6 8 9 10 0 9 12 13 14 15
(3)

（OEIS A193331）。

图兰图是 色唯一的（Chao 和 Novacky 1982）。如果 k|n，则图兰图 T_(n,k) 总是 强正则的（但即使 kn 也可能是正则的）。

图兰图 T_(n,k) 的 色数 为 k（Chao 和 Novacky 1982）。

下表总结了图兰图的特殊情况。

图类图兰图
完全图 K_n(n,n)
K_n-e(n,n-1)
完全二部图 K_(n,n)(2n,2)
n-鸡尾酒会图(2n,n)
完全三部图 K_(n,n,n)(3n,3)
空图 K^__n(n,1)

图兰图 T(n,[n/3]) 具有 3^a2^b 个极大团，其中 3a+2b=n 且 b<=2，这是所有 n 顶点图中可能的最大数量 (Moon 和 Moser 1965)。

另请参阅

二部图, 团, 完全二部图, 完全图, 完全 k-部图, k-部图, 极图, 极图理论, 图兰定理

在 Wolfram|Alpha 中探索

参考文献

Aigner, M. "Turán's Graph Theorem." Amer. Math. Monthly 102, 808-816, 1995.Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bollobás, B. Modern Graph Theory. New York: Springer-Verlag, 1998.Chao, C. Y. and Novacky, G. A. Jr. "On Maximally Saturated Graphs." Disc. Math. 41, 139-143, 1982.Diestel, R. Graph Theory, 3rd ed. New York: Springer-Verlag, 1997.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 476-477, 2006.König, D. Theorie der endlichen under unendlichen Graphen. Leipzig, Germany: Akademic Verlag, 1936.Moon, J. W. and Moser, L. "On Cliques in Graphs." Israel J. Math. 3, 23-28, 1965.Pach, J. and Agarwal, P. K. Combinatorial Geometry. New York: Wiley, 1995.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 247-248, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 143 and 218, 1990.Sloane, N. J. A. Sequence A193331 in "The On-Line Encyclopedia of Integer Sequences."Turán, P. "On an Extremal Problem in Graph Theory." Mat. Fiz. Lapok 48, 436-452, 1941.Zykov, A. A. "On Some Properties of Linear Complexes." Mat. Sbornik N.S. 24, 163-188, 1949. Translation in Amer. Math. Soc. Transl., No. 79, 1-33, 1952.

在 Wolfram|Alpha 上被引用

图兰图

请引用为

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

主题分类