今天中午，和几个小伙伴一起吃鸡公煲，我们要的大煲，肉很多很香很好吃。锅里面有洋葱、芹菜等各种蔬菜，芹菜在锅里不能煮太久要不该不脆不好吃了，洋葱可以多煮会儿，入味的洋葱很好吃。

鸡公煲的飘香气味愈发浓烈，大家也变得情绪高涨起来并开始聊天，后来不知道谁聊到了考大学这个话题，一个苏州小伙伴对着另外一个上海小伙伴说道，上海的高中生压力最小，很容易考上上海本地的好大学。而上海的小伙伴表示不服，他表示上海的小伙伴高中很努力，周末也去上课或者补课，虽然好大学多，但是大家都在努力往更好发展并不会懈怠。然后他们又讨论了学校资源，结论是本地考生享受本地学校的更多名额很合理，有些地区没有好大学只能怪这个地区发展不行。等等讨论，总之很好玩。

我一边安静地吃着美味一边听着他们聊天，在他们聊天过程中，我自己悄悄地吃了很多鸡肉，很开心。鸡公煲被我吃的差不多了，只剩菜了的时候，我也加入了他们的聊天。

我说了下我的个人观点，我觉得上海的高中生确实比很多地区高中生优质，上海的大学本地录取名额多也是不争的事实。大学毕业会看到，上海的学生和外地的学生，发展的都很好，这也说明大学多招上海本地学生是对的，毕竟学生也优质。

然后我举了两个发生在我身边的例子，来证明上海学生确实很优质：
1. 高中时候的我才华横溢，经常诗兴大发，放荡不羁的我去参加新概念作文大赛，成绩不咋地，当时一等奖的上海学生占比很大。
2. 我从小就喜欢数学，背数字1到100，背的可快了，而且数字从来不遗漏！高中去参加了数学冬令营，成绩不咋地，当时上海六个同学，全部是一等奖，完胜全国其他所有省份。

饭后，我突然回忆起来，数学冬令营时候有很多大学自主招生，因为冬令营学生不多资源有限，有的大学会面试问几道题，有的大学甚至连问都不问直接签合同就好。面试也很随意，大家都住宾馆，直接坐床上就开始面试。当时复旦数学院副院长面试我，问了一个比较有趣的题目，是关于图论的，我一分钟就回答完了。

我很喜欢图论，因为没有太多数字和公式，解题过程往往就是画来画去，所以我想写关于图论的博客，这篇就算是入门吧。希望通过写关于图论的博客，来提升自己的画画能力吧~！哈哈哈哈，开玩笑的！

试题描述

大街上有六个人，请证明他们之中至少存在三个人，这三个人要不互相认识，要不互相不认识。

思路

首先，通过题目很难想到会用什么公式，可是呢，还不得不承认它是一道数学题。这，就是图论的魅力！那么，我们怎么解呢，既然在讲图论，当然用图论的方法解了。
这里需要注意一点，也是我自己领悟出来的，自我感觉很牛逼的一句话：

这句话的意思就是，图是否漂亮、是否完美不重要，重要的是画的过程，图论高手心中有的只是画图的动作与过程，而最终图是什么样子，根本不重要。我在解图论类的题目时，笔尖在纸上的每一次滑动，都是灵魂的一次触动，有时候在解同一道题目时，两次画出来的图甚至不一样。

图的要素

上面已经提到了，图论不是美术，对于没有思考帮助的东西，我们不要画，比如街景。
具体的实物，我们也不要画的复杂，比如小人，我们完全可以用个点代替，如果有多个小人想区分名字，我们可以画个圈圈，并在圈里写字母区分即可。
总之，不要画成这个样子：

图的要素，有两个，一个是点（也可以是圈），代表实物，另一个则是线，代表实物与实物的联系。

转化

这道题目可以转化成另一种问法，问至少需要多少人，才能保证他们之间有三个人相互认识、或者相互不认识。
同理，更深入的问题，对于任意整数m（m >= 3），需要多少人，可以保证有m人相互认识、或者相互不认识。

好了，现在开始证明，如果要求有三个人互相认识/不认识，至少需要六个人。

指定任意两个人，那么他们的关系只有两种情况，要么互相认识，要么互相不认识。对于认识，我们用蓝色实线表示认识，用红色虚线表示不认识。

当有三个人时，比如这个图，代表三个人互相都认识。也可以全部是红色虚线，就是三个人互相都不认识。这种三角形，暂且称它为纯色三角形吧。

那么，这道题就变成了，在纸上画一些圈，每个圈之间可以用红色或者蓝色线连接，至少需要六个圈才一定存在纯色三角形！怎么样，题目转换成了一个画图问题，哈哈，好玩不！

至少要六个，那么就要否定小于六的场景。我分别画3个圈、4个圈、5个圈的图，并保证这些图都可以没有纯色三角形，就可以啦！很好画的，如图：

最后的证明

好了，接下来开始证明六个圈，一定存在纯色三角形。我们用反证法，只要证明我们无法画出不含纯色三角形的图即可。

我们先画一个点A，然后还剩五个点，点A和这五个点连成五条边，假设这五条边都是蓝色（也可以是红色，证明同理），会发现这五条边的颜色目前对答案并没有任何帮助。

我们只看A与B、C、D这四个点，由于A与B、C、D都是蓝色线，如果B和C是蓝色，那么就出现了纯色三角形，命题成立了，所以B和C不能用蓝色，我们只能用红色，才能保证没有纯色三角形。同理，C与D、B与D也只能是红色。这下又尴尬了，B、C、D这三货又变成了纯色三角形，命题还是成立。

若想命题不成立，那么就不允许A和B、C、D用蓝色连起来。更通俗地讲，就是A不允许和三个点用相同颜色连起来。从图中可以看到，从A出发有五条线，每条线只有两种颜色可选，不论我们怎么选择，都会有一种颜色出现至少三次，所以无论怎么画，都不可避免同色三角形的出现。

至此，证明命题成立。

图论的价值

正如这道题目的解题思路，怎么画、下一笔画什么，勾勒出了图论的精髓。图论是数学的一个分支，在计算机应用中有着极大的价值和用途。

比如六位分割理论，你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过六个人你就能够认识任何一个陌生人。

总之，没事多画画圈和线，让现实世界的逻辑转换为纸上的图，这是另一番思维的享受！