|
以文本方式查看主题 - 计算机科学论坛 (http://bbs.xml.org.cn/index.asp) -- 『 计算机考研交流 』 (http://bbs.xml.org.cn/list.asp?boardid=67) ---- [求助]离散定理13.10证明问题~ (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=54304) |
|
-- 作者：fgffggfg -- 发布时间：10/25/2007 1:43:00 PM -- [求助]离散定理13.10证明问题~ 北大离散教材p196页 定理13.10证明过程中证明G*-V`是不交完全图之并时这样写到: 否则,设G*-V`有连同分支Gi不是完全图,则存在u,v,w属于V(Gi),使得(u,v),(v,w)属于E(G*),而(u,w)不属于E(G*). 又因为v不属于V`,所以dG*(v)<=n-2,所以存在x属于V(G*-V`),使得(v,x)不属于E(G*). 请问红色字的推导部分是怎么来的? 谢谢 |
|
-- 作者：fgffggfg -- 发布时间：10/25/2007 8:06:00 PM -- 都忙着复习么,怎么没人回答啊!? |
|
-- 作者：williamsg -- 发布时间：10/25/2007 8:12:00 PM -- 哦，是这样的，因为如果v不是<=n-2,那只能是n-1,也就是与所有的其他顶点相邻，而这样的顶点应该已经被作为V'的元素被扣除掉了，所以v肯定不能等于n-1,只能<=n-2。也就是说至少有一个其他顶点不与v相邻 而V'中的所有顶点都是与v相邻的（因为度数都是n-1），所以必然有一个不属于V'的其他顶点与v不相邻，也就是V(G*-V')中的一个顶点 |
|
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
31.250ms |