以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  [原创]离散大本,关于第十一章平面图,P167中定义11.3 极大平面图定义后面说明的讨论  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=60306)


--  作者:cpkug
--  发布时间:3/23/2008 11:05:00 AM

--  [原创]离散大本,关于第十一章平面图,P167中定义11.3 极大平面图定义后面说明的讨论
离散大本,关于第十一章平面图,P167中定义11.3 极大平面图定义后面说明的讨论
极大平面图的定义下面有句话,就是说“从定义不难看出,极大平面图必是连通的”

我也觉得对,但就是没推理得通,我的推理:
1> 如果G中不存在不相邻的顶点,则极大平面图必是连通的;
2> 如果G中存在不相邻的顶点u、v,有什么理由说明u、v一定是连通的呢?觉得理由就在眼前,可就是说不出来,请大家帮忙说说吧!

谢谢了!


--  作者:Logician
--  发布时间:3/23/2008 3:43:00 PM

--  
反设G是不连通的极大平面图,则存在连通支V_1。取V_2=G - V_1,它们都是平面图(从而可以嵌入某个平面),从V_1和V_2的(平面嵌入)的外边界上各取一个顶点,将它们相连,得到的仍是平面图。这与G的极大性矛盾。
--  作者:jason_00
--  发布时间:3/23/2008 4:29:00 PM

--  
版主要经常来逛逛---
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
1,844.238ms