主題
Search

極圖

一般來說，極圖是不包含給定圖 G 作為子圖的具有最大階數 n 的圖 (Skiena 1990, p. 143)。Turán 研究了不包含完全圖 K_p 作為子圖的極圖。

一種備受研究的極圖型別是對完全圖 K_n 的 n 個節點的雙色著色，其中恰好包含數量 N=(R+B)_(min) 的單色強制三角形，且不再多（即，最少 R+B，其中 R 和 B 是紅色和藍色三角形的數量）。Goodman (1959) 表明，對於這種型別的極圖，

N(n)={1/3m(m-1)(m-2) for n=2m; 1/32m(m-1)(4m+1) for n=4m+1; 1/32m(m+1)(4m-1) for n=4m+3.
(1)

這有時被稱為 Goodman 公式。Schwenk (1972) 將其改寫為形式

N(n)=(n; 3)-|_1/2n|_1/4(n-1)^2_|_|,
(2)

有時被稱為 Schwenk 公式，其中 |_x_| 是向下取整函式。N(n) 對於 n=1, 2, ... 的前幾個值是 0, 0, 0, 0, 0, 2, 4, 8, 12, 20, 28, 40, 52, 70, 88, ... (OEIS A014557)。

另請參閱

雙色圖, 藍色空圖, 極圖理論, Goodman 公式, 單色強制三角形, Schwenk 公式, Turán 圖

使用 探索

參考資料

Goodman, A. W. "On Sets of Acquaintances and Strangers at Any Party." Amer. Math. Monthly 66, 778-783, 1959.Schwenk, A. J. "Acquaintance Party Problem." Amer. Math. Monthly 79, 1113-1117, 1972.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 143, 1990.Sloane, N. J. A. Sequence A014557 in "The On-Line Encyclopedia of Integer Sequences."

在 上引用

極圖

引用為

Weisstein, Eric W. "極圖。" 來自 網路資源。 https://mathworld.tw/ExtremalGraph.html

主題分類