二分图的独立数与香农容量相等性证明及相关推导疑问咨询
二分图的独立数与香农容量相等性证明及相关推导疑问咨询
各位图论领域的大佬们好,我最近碰到一个问题卡壳了,想请教下大家:
设 $\alpha(G)$ 表示图 $G$ 的独立数,$S(G)$ 表示图 $G$ 的香农容量。请证明:对于每一个二分图 $G$,$\alpha(G)=S(G)$。
我直觉上觉得这个结论是对的,但就是不知道该怎么给出严谨的证明过程,有没有人能帮我梳理下思路或者提供一些证明方向呀?非常感谢!
另外我突然想到一个点,想顺便问问:
这个结论是不是可以从**柯尼希定理(König's Theorem)**推导出来呢?
备注:内容来源于stack exchange,提问作者Piglet
相关产品推荐
相关产品推荐

