单星妖怪
这两天在复习《图论》，记不起谁说过，记忆材料最好的方法是书面总结和复述，所以我就写了这篇日志。我想结合生活实际介绍一些有趣的数学结论，并且仅仅对一些浅显的结论予以证明，希望即便是文科生或者对数学不感冒的人都可以看懂我在说什么，而且觉得有趣。我喜欢数学的精确，容不得半点差池，所以如有谬误，不吝赐教。
1.你有5颗五角星，要把它们放在4个不同的抽屉里，那肯定有1个抽屉里面至少有2颗五角星。
解释：情景就似上面所画，一般人想到的情形是每个抽屉里都至少有1颗星，这样明显多出来的那颗会放在某个抽屉里，这样的话那个抽屉里就有2颗星，满足条件；比较极端的做法是把5颗星全都放在1号抽屉里，那1号抽屉就有5颗星了，也满足条件哦～
证明：可以反着想（数学里称为反证法，可参见http://zh.wikipedia.org/wiki/%E5%8F%8D%E8%AF%81，一般正面进攻屡屡失败的情况下会考虑这种方法，尤其在开辟新领域且没有多少定理可用的情况下更是威力无边）：假如每个抽屉里的星星数目不超过1，那4个抽屉加起来最多也只有4颗星那，5颗放不完那亲～done！
这个问题其实可以进一步引申，若将n(r-1)+1个苹果放到n个抽屉里，至少有一个抽屉的苹果数目不少于r个，称为抽屉原理，或者鸽笼原理，由此可以引出一系列有意思的结论，想进一步了解，可移步至http://zh.wikipedia.org/wiki/%E9%B4%BF%E5%B7%A2%E5%8E%9F%E7%90%86。
2.周末约两三好友一起出游或者k歌，就有这么一个有意思的结论：在你们这一群人里，肯定会有两个人认识的朋友一样多。
解释：也就是说，不可能每个人认识的朋友数目不同。以3个人的情况为例，比如我叫一个同学A出来玩，然后我同学顺道又叫了他的同学C，而我不认识C，那我的朋友数就是1（我只认识A），而C同学的朋友数目也是1（他只认识A），这样的情况也适用于多人的情况，但是他们认识的朋友数目就未必只是1了，可能都认识2个、4个人。还有一种比较极端的情况，他们都互相不认识，比如同城豆瓣网友聚会，那因为每个人认识的人数都是0，也符合条件哦～
证明：其实这个问题可以通过画图来证明。假如你去食堂吃饭的时候，前面并排走着6个人，那这些人的关系就可以表示成下面的这幅图
顶点代表人，如果这两个人认识，那么就在他们之间拉一条线，然后就连成了这个样子，呃，看起来挺混乱的。那只看这幅图你就知道了2君和5君互相之间就是“路人”，哇，1君认识好多人哦～咳咳，这样的话每个顶点的连线数目（称为顶点的度）就是这个人朋友数目了。那就可以说图里至少有两个顶点的连线数是一样的。明显5君、3君和4君都有3个朋友，6君和2君都有4个朋友。
其实看这幅图就能知道有n的顶点的图，任何一个顶点最多的连线数目是n-1，如果每个人至少有一个朋友的话那每个人认识的朋友数目就是集合A={1,2,...,n-1}里的元素，并且不存在任何其他的可能。这样的话，每个人认识多少人就相当于这n个人放到n-1个抽屉里（每个抽屉上面编号，依次为1～n-1），根据上面的抽屉原理，那肯定就至少有两个人被放到同一个抽屉里啦！done！
3.你能不抬笔，一笔画完下面这幅图吗？
解释：相信很多人见到过这样的问题，我在小学的数学暑假作业里就做过这些题，自己做出来就很高兴，但是有些图怎么画都做不到一笔画完，这就很囧，s上次就是，哈哈！其实这幅图是可以画出来的，因为这幅图里只有2个顶点的连线数是奇数，并且如果要画出这幅图，那你的起笔和落笔肯定在这两个点上！
解答：一个可能的答案是426143521。
证明：这个问题和古老的“哥尼斯堡七桥问题”有关，话说哥尼斯堡这个公园里有七座桥，有人就问有没有一种走法可以把这七座桥都走完并且没有重复呢？1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑，也就是我今天复习的这门课的祖先，1736～2011，差不多300年的历史啊！有人说欧拉、牛瞪这些人生出来就是叫我们这些人挂科的，哈哈～
可以这么证明，如果要画完这幅图，首先可以肯定的是，除了终点和起点之外，其它的顶点都是“被经过的”，就像下面的点A，不管A点被经过之后是什么样子（图里面的那些点点段段），但是一旦要过A点必然是“有进有出”，就像箭头的方向所指的那样。如果只进不出，那就在A点停下了，A点就成终点了哦，因为“进一下”就要“出一下”，所以A点的度肯定是偶数，也就是说除起点和终点之外，其它点的度数都应该是偶数。至于起点和终点的奇偶性，没有要求，奇数可以偶数也可以，不过如果是奇数的话，只能有两个分别作起点和终点，不然的话起点和终点就有至少3个啦，明显不符合实际么，done！
这个问题的应用可以体现在景区的游览路线的制定上，下面这幅图就是杜甫草堂的游览图
关于“哥尼斯堡七桥问题”，可以进一步参见http://baike.baidu.com/view/142962.htm。
4.话说5女5男（陈奕迅，王力宏，金城武，梁朝伟，文章）相亲，但是不是一起相亲，分别约会，并且只要女方挑选到男方，那这个男的就要不顾一切地娶这个女的为妻（这样的女人好幸福），在一轮密集的相亲之后，女方都有了自己的心中的人选：
女1号中意陈奕迅，王力宏；女2号被王力宏和金城武秒杀；女3号喜欢陈奕迅和梁朝伟；女4号非金城武和文章不嫁；女5号更青睐文章和梁朝伟。那有没有一种配对的方式让每个女生都能觅得如意郎君呢？
解释：配对的方式以满足一夫一妻制，不搞三角恋，不搞暧昧，不造成女生之间的勾心斗角，掐肉抓头发为宜，嘿嘿～
解答：一种可能的配对方式是：1号——陈奕迅，2号——王力宏，3号——梁朝伟，4号——金城武，5号——文章。
其实这个问题看起来很简单，稍微在脑子里想一想就能配对成功。但是如果稍微复杂点就得借助数学的帮助了，它同样可以用画图的方式解决，就像下图一样，如果女方中意某个男方，就在他们之间牵红线。我的配对方式是图中红线所连，其实也可以看出来蓝色的连法也是可以的。
那问题就可以重新说成，找到一种连线方式，使双方的每个顶点和对面的某个顶点相连，并且每个顶点都被连到。这个问题就是图论中的完美匹配问题。这里涉及一系列比较复杂的定理，其中的一条就是对于每个顶点的连线数目相等的偶图，存在完美匹配。如果想进一步了解，可以访问http://zh.wikipedia.org/wiki/%E5%8C%B9%E9%85%8D_(%E5%9B%BE%E8%AE%BA)。
5.一共有5个药箱，每个药箱里都装了一些药品，并且每两个药箱都有一种相同的药，每种药只出现在2个药箱里，那一共有多少种药呢？
解释：明显不可能只有1种药品，这种药品就会出现在5个而不是2个药箱里，所以至少有2种药品。但是如果只有2种药品，那么根据抽屉原理，至少有3个药箱装着同样的药品，所以也不符合条件；3种药品的话……好复杂啊×..×
解答：10种。这个问题也可以用画图的方式来解决，如下图：
5个顶点代表5个药箱，假如2个药箱有相同的药品就将它们相连，因为这个问题中每2个药箱都有一种相同的药，所以全部都连接起来。那么问题就变成了在连接而成的这些边中，怎样的染色方式能保证两个顶点之间的染色后的颜色各不相同，那么一共有C_{5}^{2}=10条边，所以一共有10种颜色。
这个问题进一步引申一下，假如每种药出现在3个药箱里，一共有多少种药？答案是5种，染色方式如下图所示：
举例来说就是绿色药品出现在1、2和3号箱子里，而明显每两个箱子都有1种相同的药。
引申：这个问题引申开就是大名鼎鼎的“四色定理（4CC）（ 参见http://zh.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86）”。四色定理的表述很简单：对于任何一张地图，只要四种颜色就可以把各国的领土染上一种颜色，并且保证相邻国家的颜色不同。以下面中国地图的一部分为例（对不起，我不是有意把南海切掉的==！），就能看出这个定理的正确性。
这个问题是如此简朴以至于可以跟随便一个人在几分钟之内讲清楚，我总是被这些表述简单但是蕴含深刻数学原理的问题所吸引，就像费马大定理（参见http://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%A4%A7%E5%AE%9A%E7%90%86）一样是“会下金蛋的鹅”。它在1852年由因果大学生Guthrie向自己的老师De Morgan请教，在1976年由美国的数学家Kenneth和Wolfgang Haken用计算机证明了其成立。但是到目前为止还没有人依靠传统的方法，只用一只笔和一叠纸彻底地从理论上证明出这个问题。关于四色问题的机器证明原理可以参考王树禾编著的《图论》第二版。
——————————————————————————————————————
从下午3点到现在的8点多，这篇日志我写了5个多小时，是到目前为止花的时间最长的一篇豆瓣日志，除了第1题之外，我所描述的这些都是图论中的问题，涉及到了图论中的匹配、染色和欧拉图三个大问题，图论中的其他有意思的问题还有很多，恕篇幅有限不能一一列举。这学期所学学科中饶有趣味的就属这门课了，虽然做题时思索会很艰深，但是图论这门课不要求有多好的数学基础，只要有正常的逻辑推理能力，每个人都可以上手，我觉得初中高中都不要上，小学毕业就可以完全理解里面大部分定理的证明，实在是非常有智力乐趣的一门学科。我想说的是，数学里不只是公式和定理，它也有非常美丽的外衣，虽然我的数学也不怎么滴+..+
最后一点，题目是单星妖怪（snark graph），又称“Peterson图”，是图论中非常有名的“打假斗士”，如下图所示，
还有个双星妖怪，进一步了解请猛击链接http://zh.wikipedia.org/wiki/%E4%BD%A9%E7%89%B9%E6%A3%AE%E5%9C%96。
1.你有5颗五角星，要把它们放在4个不同的抽屉里，那肯定有1个抽屉里面至少有2颗五角星。
 |
放星星 |
解释：情景就似上面所画，一般人想到的情形是每个抽屉里都至少有1颗星，这样明显多出来的那颗会放在某个抽屉里，这样的话那个抽屉里就有2颗星，满足条件；比较极端的做法是把5颗星全都放在1号抽屉里，那1号抽屉就有5颗星了，也满足条件哦～
证明：可以反着想（数学里称为反证法，可参见http://zh.wikipedia.org/wiki/%E5%8F%8D%E8%AF%81，一般正面进攻屡屡失败的情况下会考虑这种方法，尤其在开辟新领域且没有多少定理可用的情况下更是威力无边）：假如每个抽屉里的星星数目不超过1，那4个抽屉加起来最多也只有4颗星那，5颗放不完那亲～done！
这个问题其实可以进一步引申，若将n(r-1)+1个苹果放到n个抽屉里，至少有一个抽屉的苹果数目不少于r个，称为抽屉原理，或者鸽笼原理，由此可以引出一系列有意思的结论，想进一步了解，可移步至http://zh.wikipedia.org/wiki/%E9%B4%BF%E5%B7%A2%E5%8E%9F%E7%90%86。
2.周末约两三好友一起出游或者k歌，就有这么一个有意思的结论：在你们这一群人里，肯定会有两个人认识的朋友一样多。
解释：也就是说，不可能每个人认识的朋友数目不同。以3个人的情况为例，比如我叫一个同学A出来玩，然后我同学顺道又叫了他的同学C，而我不认识C，那我的朋友数就是1（我只认识A），而C同学的朋友数目也是1（他只认识A），这样的情况也适用于多人的情况，但是他们认识的朋友数目就未必只是1了，可能都认识2个、4个人。还有一种比较极端的情况，他们都互相不认识，比如同城豆瓣网友聚会，那因为每个人认识的人数都是0，也符合条件哦～
证明：其实这个问题可以通过画图来证明。假如你去食堂吃饭的时候，前面并排走着6个人，那这些人的关系就可以表示成下面的这幅图
 |
6个小孩一起去吃饭 |
顶点代表人，如果这两个人认识，那么就在他们之间拉一条线，然后就连成了这个样子，呃，看起来挺混乱的。那只看这幅图你就知道了2君和5君互相之间就是“路人”，哇，1君认识好多人哦～咳咳，这样的话每个顶点的连线数目（称为顶点的度）就是这个人朋友数目了。那就可以说图里至少有两个顶点的连线数是一样的。明显5君、3君和4君都有3个朋友，6君和2君都有4个朋友。
其实看这幅图就能知道有n的顶点的图，任何一个顶点最多的连线数目是n-1，如果每个人至少有一个朋友的话那每个人认识的朋友数目就是集合A={1,2,...,n-1}里的元素，并且不存在任何其他的可能。这样的话，每个人认识多少人就相当于这n个人放到n-1个抽屉里（每个抽屉上面编号，依次为1～n-1），根据上面的抽屉原理，那肯定就至少有两个人被放到同一个抽屉里啦！done！
3.你能不抬笔，一笔画完下面这幅图吗？
 |
一笔画 |
解释：相信很多人见到过这样的问题，我在小学的数学暑假作业里就做过这些题，自己做出来就很高兴，但是有些图怎么画都做不到一笔画完，这就很囧，s上次就是，哈哈！其实这幅图是可以画出来的，因为这幅图里只有2个顶点的连线数是奇数，并且如果要画出这幅图，那你的起笔和落笔肯定在这两个点上！
解答：一个可能的答案是426143521。
证明：这个问题和古老的“哥尼斯堡七桥问题”有关，话说哥尼斯堡这个公园里有七座桥，有人就问有没有一种走法可以把这七座桥都走完并且没有重复呢？1736年29岁的欧拉向圣彼得堡科学院递交了《哥尼斯堡的七座桥》的论文，在解答问题的同时，开创了数学的一个新的分支——图论与几何拓扑，也就是我今天复习的这门课的祖先，1736～2011，差不多300年的历史啊！有人说欧拉、牛瞪这些人生出来就是叫我们这些人挂科的，哈哈～
可以这么证明，如果要画完这幅图，首先可以肯定的是，除了终点和起点之外，其它的顶点都是“被经过的”，就像下面的点A，不管A点被经过之后是什么样子（图里面的那些点点段段），但是一旦要过A点必然是“有进有出”，就像箭头的方向所指的那样。如果只进不出，那就在A点停下了，A点就成终点了哦，因为“进一下”就要“出一下”，所以A点的度肯定是偶数，也就是说除起点和终点之外，其它点的度数都应该是偶数。至于起点和终点的奇偶性，没有要求，奇数可以偶数也可以，不过如果是奇数的话，只能有两个分别作起点和终点，不然的话起点和终点就有至少3个啦，明显不符合实际么，done！
 |
A点屡次被经过 |
这个问题的应用可以体现在景区的游览路线的制定上，下面这幅图就是杜甫草堂的游览图
 |
杜甫草堂游览图 |
关于“哥尼斯堡七桥问题”，可以进一步参见http://baike.baidu.com/view/142962.htm。
4.话说5女5男（陈奕迅，王力宏，金城武，梁朝伟，文章）相亲，但是不是一起相亲，分别约会，并且只要女方挑选到男方，那这个男的就要不顾一切地娶这个女的为妻（这样的女人好幸福），在一轮密集的相亲之后，女方都有了自己的心中的人选：
女1号中意陈奕迅，王力宏；女2号被王力宏和金城武秒杀；女3号喜欢陈奕迅和梁朝伟；女4号非金城武和文章不嫁；女5号更青睐文章和梁朝伟。那有没有一种配对的方式让每个女生都能觅得如意郎君呢？
解释：配对的方式以满足一夫一妻制，不搞三角恋，不搞暧昧，不造成女生之间的勾心斗角，掐肉抓头发为宜，嘿嘿～
解答：一种可能的配对方式是：1号——陈奕迅，2号——王力宏，3号——梁朝伟，4号——金城武，5号——文章。
其实这个问题看起来很简单，稍微在脑子里想一想就能配对成功。但是如果稍微复杂点就得借助数学的帮助了，它同样可以用画图的方式解决，就像下图一样，如果女方中意某个男方，就在他们之间牵红线。我的配对方式是图中红线所连，其实也可以看出来蓝色的连法也是可以的。
 |
相亲 |
那问题就可以重新说成，找到一种连线方式，使双方的每个顶点和对面的某个顶点相连，并且每个顶点都被连到。这个问题就是图论中的完美匹配问题。这里涉及一系列比较复杂的定理，其中的一条就是对于每个顶点的连线数目相等的偶图，存在完美匹配。如果想进一步了解，可以访问http://zh.wikipedia.org/wiki/%E5%8C%B9%E9%85%8D_(%E5%9B%BE%E8%AE%BA)。
5.一共有5个药箱，每个药箱里都装了一些药品，并且每两个药箱都有一种相同的药，每种药只出现在2个药箱里，那一共有多少种药呢？
解释：明显不可能只有1种药品，这种药品就会出现在5个而不是2个药箱里，所以至少有2种药品。但是如果只有2种药品，那么根据抽屉原理，至少有3个药箱装着同样的药品，所以也不符合条件；3种药品的话……好复杂啊×..×
解答：10种。这个问题也可以用画图的方式来解决，如下图：
 |
药品的分布 |
5个顶点代表5个药箱，假如2个药箱有相同的药品就将它们相连，因为这个问题中每2个药箱都有一种相同的药，所以全部都连接起来。那么问题就变成了在连接而成的这些边中，怎样的染色方式能保证两个顶点之间的染色后的颜色各不相同，那么一共有C_{5}^{2}=10条边，所以一共有10种颜色。
这个问题进一步引申一下，假如每种药出现在3个药箱里，一共有多少种药？答案是5种，染色方式如下图所示：
 |
另一种情况 |
举例来说就是绿色药品出现在1、2和3号箱子里，而明显每两个箱子都有1种相同的药。
引申：这个问题引申开就是大名鼎鼎的“四色定理（4CC）（ 参见http://zh.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86）”。四色定理的表述很简单：对于任何一张地图，只要四种颜色就可以把各国的领土染上一种颜色，并且保证相邻国家的颜色不同。以下面中国地图的一部分为例（对不起，我不是有意把南海切掉的==！），就能看出这个定理的正确性。
 |
中国地图 |
这个问题是如此简朴以至于可以跟随便一个人在几分钟之内讲清楚，我总是被这些表述简单但是蕴含深刻数学原理的问题所吸引，就像费马大定理（参见http://zh.wikipedia.org/wiki/%E8%B4%B9%E9%A9%AC%E5%A4%A7%E5%AE%9A%E7%90%86）一样是“会下金蛋的鹅”。它在1852年由因果大学生Guthrie向自己的老师De Morgan请教，在1976年由美国的数学家Kenneth和Wolfgang Haken用计算机证明了其成立。但是到目前为止还没有人依靠传统的方法，只用一只笔和一叠纸彻底地从理论上证明出这个问题。关于四色问题的机器证明原理可以参考王树禾编著的《图论》第二版。
——————————————————————————————————————
从下午3点到现在的8点多，这篇日志我写了5个多小时，是到目前为止花的时间最长的一篇豆瓣日志，除了第1题之外，我所描述的这些都是图论中的问题，涉及到了图论中的匹配、染色和欧拉图三个大问题，图论中的其他有意思的问题还有很多，恕篇幅有限不能一一列举。这学期所学学科中饶有趣味的就属这门课了，虽然做题时思索会很艰深，但是图论这门课不要求有多好的数学基础，只要有正常的逻辑推理能力，每个人都可以上手，我觉得初中高中都不要上，小学毕业就可以完全理解里面大部分定理的证明，实在是非常有智力乐趣的一门学科。我想说的是，数学里不只是公式和定理，它也有非常美丽的外衣，虽然我的数学也不怎么滴+..+
最后一点，题目是单星妖怪（snark graph），又称“Peterson图”，是图论中非常有名的“打假斗士”，如下图所示，
 |
snark graph |
还有个双星妖怪，进一步了解请猛击链接http://zh.wikipedia.org/wiki/%E4%BD%A9%E7%89%B9%E6%A3%AE%E5%9C%96。
