主题
Search

古德曼公式

一个 完全图 K_n 的双色着色，恰好包含最少数量的 单色强制三角形（即，最少 R+B，其中 R 和 B 分别是红色和蓝色 三角形 的数量），被称为 极图。Goodman (1959) 证明了对于一个极图，

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

Schwenk (1972) 将方程改写为如下形式

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

其中 (n; k) 是一个 二项式系数，而 |_x_|\ 是 向下取整函数。

参见

蓝色空图, 极图, 单色强制三角形

使用 探索

参考文献

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.

在 中被引用

古德曼公式

请引用为

Weisstein, Eric W. "Goodman's Formula." 来自 —— 资源。 https://mathworld.net.cn/GoodmansFormula.html

学科分类