主題
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-部圖, 極圖, 極圖理論, 圖蘭定理

在 中探索

參考文獻

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.

在 上被引用

圖蘭圖

請引用為

Weisstein, Eric W. "圖蘭圖。" 來自 Web 資源。 https://mathworld.tw/TuranGraph.html

主題分類