以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  图论小问题（2）  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=37155)

--  作者：Supremgoooo
--  发布时间：8/24/2006 2:57:00 PM

--  图论小问题（2）
（1）习题11.3：证明多面体图（柏拉图图）有且仅有5种。给点提示吧？
（2）习题11.6：画出所有6阶连通的简单非同构的非平面图。我算25种，对下答案。
（3）习题12.5：设G是n阶k-正则图，证明X(G)>=n/(n-k)。小书给出如下证明：
证明：设v为G中任意一顶点，因为d（v）=k，因而至多有n-k个顶点可以与v涂相同颜色，于是至少需要[n/（n-k）]种颜色给G的顶点着色，所以X(G)>=[n/(n-k)]>=n/(n-k)。
(其中[x]表示不小于x的最小整数）
为啥：于是至少需要[n/（n-k）]种颜色给G的顶点着色？


ps：我第2题的答案是：
考虑K5：设其顶点顺时针方向依次为：v1，v2，v3，v4，v5
1。在v1v5中加一点v
2。在v1v5中加一点v，连接vv3
3。在v1v5中加一点v，连接vv2
4。在v1v5中加一点v，连接vv3，vv2
5。在v1v5中加一点v，连接vv3，vv2，vv4

6。在v5v2中加一点v
7。在v5v2中加一点v，连接vv1
8。在v5v2中加一点v，连接vv4
9。在v5v2中加一点v，连接vv1，vv4
10。在v5v2中加一点v，连接vv1，vv4，vv3

11。在k5外取一点v，连接vv1
12。在k5外取一点v，连接vv1，vv2
13。在k5外取一点v，连接vv1，vv3
14。在k5外取一点v，连接vv1，vv3，vv2
15。在k5外取一点v，连接vv1，vv3，vv4
16。在k5外取一点v，连接vv1，vv3，vv4，vv2
17。在k5外取一点v，连接vv1，vv3，vv4，vv2，vv5，即K6

考虑k3，3，设其顶点为a1,a2,a3,b1,b2,b3.其中ai与bi间有一条边
18。K3，3
19。K3，3，再连接a1a2
20。K3，3，再连接a1a2，a1a3
21。K3，3，再连接a1a2，a2a3
22。K3，3，再连接a1a2，b2b3
23。K3，3，再连接a1a2，a2a3，b1b2
24。K3，3，再连接a1a2，a2a3，a1a3
25。K3，3，再连接a1a2，a1a3，b2b3

--  作者：yangling_1985
--  发布时间：8/24/2006 4:02:00 PM

--  
设多面体G的顶点数为n,边数m,面数r，每个面的次数均l ,顶点度数为k.
由题意，2m=l*r=k*n
又由欧拉公式，n-m+r=2.代入得，
2m/k-m+2m/l=2
1/k+1/l=1/m+1/2
利用k>=3,l>=3讨论易得l,k至少有一个等于3。(m>0)
(1)
若k=3,则
1/l-1/m=1/6.由m>0.得1/l>1/6,所以l<6,所以3<=l<6,分别对l的取值讨论即可。
(2)l=3时同理
--  作者：yangling_1985
--  发布时间：8/24/2006 4:15:00 PM

--  
（3）因为如果存在图G的k-着色（k<[n/(n-k)]），由于每种颜色至多可以对n-k个顶点着色，则（G中至多有n-k个顶点同色），故有k*(n-k)>=n,又k*(n-k)<[n/(n-k)]*(n-k)<=n。矛盾！
--  作者：Supremgoooo
--  发布时间：8/24/2006 9:01:00 PM

--  
明白了。第2个方法真好！多谢杨兄！
--  作者：yangling_1985
--  发布时间：8/26/2006 6:47:00 PM

--  
不客气！
--  作者：Supremgoooo
--  发布时间：8/31/2006 6:36:00 PM

--  
第二个错了！答案是17：
考虑K5：设其顶点顺时针方向依次为：v1，v2，v3，v4，v5
1。在v1v5中加一点v
2。在v1v5中加一点v，连接vv3
3。在v1v5中加一点v，连接vv2
4。在v1v5中加一点v，连接vv3，vv2
5。在v1v5中加一点v，连接vv3，vv2，vv4

    在v5v2中加一点v，与1同构
    在v5v2中加一点v，连接vv1，与2同构
    在v5v2中加一点v，连接vv4，与3同构
    在v5v2中加一点v，连接vv1，vv4，与4同构
    在v5v2中加一点v，连接vv1，vv4，vv3，与5同构

6。在k5外取一点v，连接vv1
7。在k5外取一点v，连接vv1，vv2
8。在k5外取一点v，连接vv1，vv3
9。在k5外取一点v，连接vv1，vv3，vv2
10。在k5外取一点v，连接vv1，vv3，vv4
11。在k5外取一点v，连接vv1，vv3，vv4，vv2
12。在k5外取一点v，连接vv1，vv3，vv4，vv2，vv5，即K6

考虑k3，3，设其顶点为a1,a2,a3,b1,b2,b3.其中ai与bi间有一条边
13。K3，3
14。K3，3，再连接a1a2
15。K3，3，再连接a1a2，a1a3
      K3，3，再连接a1a2，a2a3，与15同构
16。K3，3，再连接a1a2，b2b3
       K3，3，再连接a1a2，a2a3，b1b2，与2同构
17。K3，3，再连接a1a2，a2a3，a1a3
      K3，3，再连接a1a2，a1a3，b2b3，与2同构

--  作者：borlong
--  发布时间：9/19/2006 4:25:00 PM

--  
3楼的方法真妙！！！！这就是图论的精髓所在！！！！我的506577965，有空我们交流一下！ok?
--  作者：apolor
--  发布时间：9/21/2006 11:31:00 PM

--  
（3）习题12.5：设G是n阶k-正则图，证明X(G)>=n/(n-k)。
证明：因为G是n阶k-正则图，对任意v属于V(G)，d(v)=k，于是G中与v同色顶点至少只有n-k-1个，即G中同色顶点至多只有n-k个。所以(n-k)X(G)>=n。即X(G)>=n/(n-k)。#
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 64.453ms