You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

二分图的独立数与香农容量相等性证明及相关推导疑问咨询

二分图的独立数与香农容量相等性证明及相关推导疑问咨询

各位图论领域的大佬们好,我最近碰到一个问题卡壳了,想请教下大家:

设 $\alpha(G)$ 表示图 $G$ 的独立数,$S(G)$ 表示图 $G$ 的香农容量。请证明:对于每一个二分图 $G$,$\alpha(G)=S(G)$。

我直觉上觉得这个结论是对的,但就是不知道该怎么给出严谨的证明过程,有没有人能帮我梳理下思路或者提供一些证明方向呀?非常感谢!

另外我突然想到一个点,想顺便问问:

这个结论是不是可以从**柯尼希定理(König's Theorem)**推导出来呢?

备注:内容来源于stack exchange,提问作者Piglet

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.04.23 11:59:13