计算机科学论坛--[图论]一道课后题

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

>>计算机科学论坛<<

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → [图论]一道课后题

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 36899 个阅读者　　

*	贴子主题： [图论]一道课后题	举报打印推荐 IE收藏夹
	本主题类别:

lalalalalala

  等级：大一(猛啃高等数学)
  文章：10
  积分：141
  门派：XML.ORG.CN
  注册：2006/3/30

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第21楼

以下是引用Logician在2006-8-14 15:43:00的发言：
[quote]以下是引用lalalalalala在2006-8-14 3:10:00的发言：
  我是这么考虑的：
  首先找出满足下面三条性质的平面图，
  1。连通。
  2。无桥。
  3。存在度数不超过4的顶点。
  然后在这个范围内进行讨论。
  命题：“这类图”是4-可着色的。
  证明：
  对n作归纳。
  (1)n <= 4时，显然成立。
  (2)设n = k(k >= 4)时成立，当n = k + 1时，
  G中显然存在度数不超过4的顶点v，设G_1 = G - v,
  G_1是k阶图，由归纳假设知，G_1是4-可着色的，
  下面证G。
  。。。
[/quote]
你的倒数第二句：“G_1是k阶图，由归纳假设知，G_1是4-可着色的”是错的。
我再问一遍，你的“归纳假设”是什么（请完整叙述）？
我再叙述一下“归纳法”原理。
归纳法原理是把待证看成一个与自然数一一对应的命题序列P(1),P(2),....
以本题为例，归纳法是把原题所成这样一个命题序列。
P(1):如果一个1阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。
P(2):如果一个2阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。
......
P(n):如果一个n阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。
你需要做的是：
首先证明P(1)。这是简单的。
然后证明P(n)=>P(n+1)。你在证明"P(n)=>P(n+1)"时，你所能使用的“归纳前提”是P(n)，也即，“如果一个n阶简单平面图中含有度数不超过4的顶点，那么这个图是4可着色的。”而你却说“G_1是k阶图，由归纳假设知，G_1是4-可着色的，”。请问，“由归纳假设”如何能从“G_1是k阶图”推出“G_1是4-可着色的”？

[此贴子已经被作者于2006-8-14 22:03:22编辑过]

我错了。:(
我的归纳假设是：
具有1, 2, 3这3个性质的平面图是4-可着色的。
我把“含有不超过4度的顶点”放在G的前面，
是想把它当作G的一个性质来使用，
但问题在于，不能保证在G - v中仍有4度顶点，
那么G - v就不再具有这个性质了，
也就不能使用归纳假设了。
这两天，我在考虑如果可以证明：
所有的简单平面图中都至少
存在一个不超过4度的顶点，
就可以用归纳假设了。
不过不久就发现了正20面体这个5-正则的平面图。:(
对于“G*是4-可着色的”这个命题，
也没有想出其它思路来证明。

2006/8/16 17:10:00

lalalalalala

  等级：大一(猛啃高等数学)
  文章：10
  积分：141
  门派：XML.ORG.CN
  注册：2006/3/30

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第22楼

以下是引用Logician在2006-8-14 15:54:00的发言：
[quote]以下是引用lalalalalala在2006-8-14 3:18:00的发言：
  知道“G - v”是k阶的以后，
  由归纳假设就可以得出G - v的每个连通分支是5-可着色的了，
  为什么还要知道“G - v的每个连通分支中都还有度数不超过5的顶点”？
[/quote]
我不知道你是怎么理解“数学归纳法”的。
虽然我们证明时，我们只做两件事：
（1）证明“基底”（即P(1)为真）。
（2）证明“归纳步骤”（即P(n)=>P(n+1)）。
但我们在理解这个证明时，可以从“动态”的角度来理解。
一个很好的类比是“递归函数”。
我们用递归函数求阶乘只有2句话：F(0)=1,F(n)=n*F(n-1)。
但我们实际求F(100)时，函数要运行101次，一直求到F(0)=1为止。
同理，Heawood定理的证明构造性的。如果我给你一个20阶简单平面图G，你是可以按Heawood定理的证明来找出一个5着色方案的。如果你试着做一下，就会明白为什么要为什么还要知道“G - v的每个连通分支中都还有度数不超过5的顶点”了。

我发现我对“数学归纳法”的理解
只是停留在“使用”这个阶段，
并没有从动态的角度去考虑过。
这个“递归”的类比真是不错。
对于Heawood定理，
我现在才有了一个比较清晰的理解：
实际上对于所有的自然数n，
都要证明这个n阶平面图是5可着色的。
只不过用归纳法把它简化成2步了。
但对于一个具体图的着色，还是一个从n到0的过程。
考虑20阶的平面图，要证明它是5-可着色的，
那么在G - v的每个连通分支中，
都要证明对于这些较小的n来说，命题是成立的。
这个过程一直向下推到“基底”。
我现在明白了，为什么在G - v的每个连通分支中
还需要5度顶点了，谢谢。:)

2006/8/16 17:12:00

lalalalalala

  等级：大一(猛啃高等数学)
  文章：10
  积分：141
  门派：XML.ORG.CN
  注册：2006/3/30

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第23楼

以下是引用carroty在2006-8-13 12:59:00的发言：
我的思路:
考虑所有符合题设的平面图,如果有一个图是5色的,那么因为n<4时为4色的,所以比存在,一个极小的满足题设的5色图.它去掉一个顶点就是4色图,这时去掉哪个度数小于4的顶点,仿照heawood的定理的证明可以证明G是4色的.所以这个极小的图是不存在的.所以所有满足题设的图都是4色的.
大致思路如此.灵感来自搜到的一篇文章,但是现在找不到.
:)

对于这个思路，
我开始想用G中那个次数不超过4的面，
根据Heawood定理的思路，
来归纳证明G是4-面可着色的。
但实际上它和“证明G*是4-可着色”的错误是一样的。
把这个面收缩掉后，就无法找到次数不超过4的面了。
又仔细看了一下，发现没看懂。
思路中是在说G，还是G*呢？
从“度数小于4的顶点”来看是在说G*，
而前面“所有符合题设的平面图”好像又在说G。
还有“仿照Heawood的定理的证明”，
能不能具体的说一下，
我现在对这句话特别敏感，呵呵。

2006/8/16 17:14:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第24楼

我突然发现，carroty的证明也有同样的问题……
证明中的“它去掉一个顶点就是4色图”是不成立的……
晕倒……
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2006/8/16 17:47:00

carroty

  等级：大四(GRE考了1600分!)
  文章：153
  积分：1257
  门派：IEEE.ORG.CN
  注册：2006/4/4

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第25楼

以下是引用lalalalalala在2006-8-16 17:14:00的发言：
[quote]以下是引用carroty在2006-8-13 12:59:00的发言：
我的思路:
  考虑所有符合题设的平面图,如果有一个图是5色的,那么因为n<4时为4色的,所以比存在,一个极小的满足题设的5色图.它去掉一个顶点就是4色图,这时去掉哪个度数小于4的顶点,仿照heawood的定理的证明可以证明G是4色的.所以这个极小的图是不存在的.所以所有满足题设的图都是4色的.
  大致思路如此.灵感来自搜到的一篇文章,但是现在找不到.
  :)
[/quote]
对于这个思路，
我开始想用G中那个次数不超过4的面，
根据Heawood定理的思路，
来归纳证明G是4-面可着色的。
但实际上它和“证明G*是4-可着色”的错误是一样的。
把这个面收缩掉后，就无法找到次数不超过4的面了。
又仔细看了一下，发现没看懂。
思路中是在说G，还是G*呢？
从“度数小于4的顶点”来看是在说G*，
而前面“所有符合题设的平面图”好像又在说G。
还有“仿照Heawood的定理的证明”，
能不能具体的说一下，
我现在对这句话特别敏感，呵呵。

我的意思就是先把他转化成G*,然后对G*进行讨论
所谓的仿照heawood的证明只是仿照它对5度顶点的讨论,对4度顶点的讨论也是成立的.

2006/8/17 18:15:00

carroty

  等级：大四(GRE考了1600分!)
  文章：153
  积分：1257
  门派：IEEE.ORG.CN
  注册：2006/4/4

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第26楼

以下是引用Logician在2006-8-16 17:47:00的发言：
我突然发现，carroty的证明也有同样的问题……
证明中的“它去掉一个顶点就是4色图”是不成立的……
晕倒……

我觉得证明使用的是归谬法,所以,不需要去掉一个4度顶点后还有4度顶点.另外,可以把假设做的更确切一些,比如去掉一个4度顶点以后是4色图,而这样的四色图肯定是存在的.
你的想法呢?我不是很懂你的意思~
:)

2006/8/17 18:20:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第27楼

以下是引用carroty在2006-8-17 18:20:00的发言：
我觉得证明使用的是归谬法,所以,不需要去掉一个4度顶点后还有4度顶点.另外,可以把假设做的更确切一些,比如去掉一个4度顶点以后是4色图,而这样的四色图肯定是存在的.
你的想法呢?我不是很懂你的意思~
:)

    你把你的证明完整地写出来（后面“仿Heawood”的部分就不用写了）试试？：）
    我理解的你的证法是这样：
    设 S = { G | G是简单平面图，且G中有不超过4度的顶点，且G不是4可着色的}。下面证明 S 是空集。反设S不是空集，那么令H是S中顶点数最小的一个图。设v是H中度数不超过4的一个顶点。则“H-v必是4可着色的”（但这句话不对，你可以根据“H是S中顶点数最少的一个图”推出“H-v必然不属于S”，但没法接着推出“H-v必是4可着色的”）。
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
                            - Bertrand Russell

2006/8/17 21:45:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第28楼

以下是引用carroty在2006-8-17 18:20:00的发言：
我觉得证明使用的是归谬法,所以,不需要去掉一个4度顶点后还有4度顶点.另外,可以把假设做的更确切一些,比如去掉一个4度顶点以后是4色图,而这样的四色图肯定是存在的.
你的想法呢?我不是很懂你的意思~
:)

你的证明方法其实是“数学归纳法”的另一种形式（即，利用“良序集的非空子集必有最小元”的性质，通过证明“该子集没有最小元”来证明“该子集为空”。我们知道，它和“归纳法原理”是完全等价的）。
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2006/8/17 21:49:00

carroty

  等级：大四(GRE考了1600分!)
  文章：153
  积分：1257
  门派：IEEE.ORG.CN
  注册：2006/4/4

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第29楼

恩,是的,再想想~

2006/8/19 12:39:00

chyl

  等级：大一(高数修炼中)
  文章：12
  积分：120
  门派：XML.ORG.CN
  注册：2006/8/2

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第30楼

呵呵终于看到这一章了，一直看你们讨论的这么热烈。想看看到底是什么题。
不过这道题真的证得出来吗？我好像找到了反例。。。请看看对不对。
因为G为连通的简单的平面图，所以G的平面嵌入为地图。要证明G是4-面可着色的，即证明G的对偶图G*为4-可着色的。还有一个条件就是δ(G*)<=4。
完全图K5好像完全满足G*的条件啊，但是K5的色数为5啊，这是怎么回事？

2006/8/21 15:58:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/5/4 6:44:52

本主题贴数38，分页： [1] [2] [3] [4]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


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