以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  《图论》定理问题，Logican。。。  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=57113)

--  作者：zshao
--  发布时间：12/23/2007 11:22:00 PM

--  《图论》定理问题，Logican。。。
RT：

1：离散大本，P169。

定理11.8，
"G是连通平面图，G的各面次数至少为L(L>=3),则m<=L/(L-2)*(n-2)."。

定理11.9
"G是是含有p个连通分支的平面图（p>=2），G的各面次数至少为L(L>=3),则m<=L/(L-2)*(n-p-1)."。

定理11.10
"G是简单平面图(n>=3),则m<=3*(n-2)."。

问题如下：
   我认为这三个定理，应该合并成一个。定理11.10=（定理11.8+定理11.9）。
不知道为什么分开论述？

我的理由：

G是连通平面图，G的各面次数至少为L(L>=3),能否推出G是简单图？
G是含有p个连通分支的平面图（p>=2），G的各面次数至少为L(L>=3),能否推出G是简单图？

答：能。因为L》=3，所以不存在环和平行边。
     （如果你认为G不是简单图，请给出反例？）


--  作者：gradxixi
--  发布时间：12/23/2007 11:47:00 PM

--  
G是连通平面图,若L=4,则m<=2(m-2),这个结果比定理11.10可强.

你的意思是说前两个定理可以推出定理11.10吧,而定理11.10的证明恰是如此.

--  作者：zshao
--  发布时间：12/24/2007 10:54:00 PM

--  
en
--  作者：buddha
--  发布时间：12/25/2007 12:43:00 PM

--  
这三个定理都可以合并为定理11.9,这是这三定理更具普遍意义的形式.其他的只是在定理11.9上的延伸.
而定理11.8和定理11.10只是为解某一类问题更方便.一些结论可以直接拿来用而不必事先推导.
确切的说应该是定理11.9包含定理11.10包含定理11.8吧.
举个例子,比如只包含定理11.10无法证明K3,3是非平面图,而用定理11.8就可以.
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 60.059ms