有2n+1个人，他们的朋友关系满足这样一种奇特的性质：任选n个人，则在剩下的人中总能找到一个人，他和这n个人都是朋友。求证，存在这样一个人，他和所有人都是朋友。我们假设朋友关系是双向的，也就是说如果A是B的朋友，那么B一定是A的朋友。

    这明显可以转化为一个图论问题。选出两个互为朋友的人。我们得到了一个大小为2的团（一个“团”就是一个所有结点两两相连的子图，或者干脆说是完全图形状的子图）。和另外n-2个人并在一起，则存在一个人和他们都是朋友（当然和那两个人也就是朋友了）。把这个人加进刚才那个团里，于是我们得到了一个大小为3的团。又随便取n-3个人和这3个并在一起，则有一个人和所有这些人都是朋友，于是我们继续扩展出一个大小为4的团。反复进行这个操作，直到我们得到一个大小为n+1的团，此时团的大小已经不能再继续扩展了。但是，一旦注意到此时不属于团的人只剩n个了时，我们发现问题已经解决了：在团里面存在一个人P，他和不属于这个团的那n个人都是朋友。而P本身在一个大小为n+1的团里面，他和团里的其余n个人都是朋友。因此，P和所有人都是朋友。

来源：http://www.cut-the-knot.org/arithmetic/combinatorics/Clique.shtml

    n个人中每两个人之间都进行过一次比赛。假设比赛不可能出现平局。证明，一定能找出这样的一个人，对于其它任何一人p，他击败了p或者击败了某个打败了p的人。

    一句话证明：赢的次数最多的那个人显然满足我们的条件。反证，假设被他打败的所有人的集合为P，万一有个人既没有输给他，也没有输给P里面的任何一人，那这个人至少赢了|P|+1次，成了获胜次数更多的人，矛盾。我故意在这里多写一句话，目的是想说明前面的空白有多短。在Ctrl+A之前，不妨试试看自己能否想到如此简单的证明。

来源：http://www.cut-the-knot.org/arithmetic/combinatorics/RoundRobinTournament.shtml

查看更多 »

  
    Cayley公式是说，一个完全图K_n有n^(n-2)棵生成树，换句话说n个节点的带标号的无根树有n^(n-2)个。今天我学到了Cayley公式的一个非常简单的证明，证明依赖于Prüfer编码，它是对带标号无根树的一种编码方式。
    给定一棵带标号的无根树，找出编号最小的叶子节点，写下与它相邻的节点的编号，然后删掉这个叶子节点。反复执行这个操作直到只剩两个节点为止。由于节点数n>2的树总存在叶子节点，因此一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。下面我们只需要说明，任何一个长为n-2、取值范围在1到n之间的数列都唯一地对应了一棵n个节点的无根树，这样我们的带标号无根树就和Prüfer编码之间形成一一对应的关系，Cayley公式便不证自明了。
查看更多 »

  
    接下来，我们用图论方法来证明：一个由小矩形拼接而成的大矩形，若每个小矩形都有至少一条整数长的边，则大矩形也有至少一条整数长的边。考虑图中每个矩形的每个顶点，把它们作为图G的顶点集（相邻矩形重合的顶点并作一个点）；对于每一个小矩形，把它整数边方向的两对顶点分别用一条边连接起来（相邻矩形公共边上的重边不合并）。如果哪个小矩形四条边都是整数，无妨随意把它当作横向整数边的或者纵向整数边的，连接任一种方向上的边。这样的话，每个矩形恰好产生两条边。注意这个图的一些很显然的性质：度为1的点只有4个（大矩形的四个角），其余的顶点的度都是偶数（只能是2或者4）。下面，我们把这个矩形放在平面坐标系上，大矩形的左下角对齐原点(0,0)。从原点开始沿着图G的边走（每条边最多走一次，不走走过的边），显然走到的每个点都满足这个性质：它的两个坐标均为整数。但我们的出发点是一个度为1的点，在走到另一个度为1的点之前，我们遇到的所有顶点的度都是偶数。因此只要没走到另一个度为1的点，我们就不可能走死。但是，图G总的边数有限，总有一个时候我们将不能再走。因此，这次旅程的终点必然落在另一个度为1的点上。这个终点是大矩形的另一个角，它的两个坐标值均为整数。命题得证。

    以上两个证明均来自http://www.cs.toronto.edu/~mackay/rectangles/

查看更多 »

    Ubigraph是一个全新的图论动画生成软件，利用它你可以快速生成图论模型的图形和动画，直观地展示出各种图论模型的三维结构，演示各种图论算法的过程，非常适合用于研究和教学。之前本Blog曾经介绍过一个类似的软件graphviz，但这里提到的Ubigraph显然更强大一些。上面的动画就是由Ubigraph生成的二叉查找树演示动画（高清版here），看上去相当的酷。值得一提的是，Ubigraph也是相当易用的。graphviz有它自己的语法规则，而Ubigraph则直接支持Python, Ruby, PHP, Java, C, C++等几乎所有主流语言，因此不管你原先使用的是什么语言，你都可以很快地融入到Ubigraph来。例如，在C语言中包含一个头文件UbigraphAPI.h，你便可以像往常一样用循环语句“画”一个环。

#include <UbigraphAPI.h>
 
int main(int const argc, const char ** const argv)
{
int i;
for (i=0; i < 10; ++i)
ubigraph_new_vertex_w_id(i);
 
for (i=0; i < 10; ++i)
ubigraph_new_edge(i, (i+1)%10);
 
sleep(2);
 
ubigraph_clear();
}

    你可以在这里下载这个软件。目前该软件暂时没有Windows版。

    以色列数学家Avraham Trakhtman最近解决了一个非常有名的数学难题——公路涂色问题(Road Coloring Problem)。这是图论中的一个著名猜想，最早由Benjamin Weiss和Roy Adler在1970年提出。63岁的Avraham用铅笔草草写下了仅仅8页的证明过程，出人意料地解决了这个问题。该问题的解决对道路规划等很多现实社会中的问题都有帮助。
    给定一个有向图G（即图中的每一条边都单向地从某个顶点指向另一个顶点），其中每一个点的出度（向外走的边的条数）都为k。假设我们用k种颜色对图G中的所有边进行染色，使得每个点的k条出边的颜色都不相同，并且对于每一个顶点v，总存在一个颜色序列，使得不管你从哪里出发，按照这个颜色序列不断走下去，最终都能到达顶点v。我们称满足这些条件的涂色方案叫做一个同步着色(synchronizing coloring)。Benjamin Weiss和Roy Adler猜想，如果一个有向图是强连通的（任两点间都可互相到达）并且是非周期性的（所有环的长度的最大公约数为1），则该图一定存在同步着色方案。例如，右面这个图就是一个合法的同步着色方案，每个点的两条出边恰好一红一蓝。我们可以找几个点简单验证一下：不管你在哪里，按“蓝-红-红”走最终总会到那个黄色的点；类似地，不断按“蓝-蓝-红”走，不管出发点在哪里你最后总会走到绿色的点。

    这个猜想的完整证明过程可以在这篇论文里找到。论文只有几页，估计我应该能看懂，看懂了的话我会更新出来的。

查看更多：来源1  来源2

    今天在回访网站流量来源时看到了一个很牛B的东西，和大家分享一下。
    给定一个顶点数为100000的图G，问是否存在Hamilton回路。现在，A宣称自己已经找到了一个Hamilton回路，但B不信，要A证明给他看。你能否想出一个办法使得，A可以让B相信自己有了正确的答案，但B依然不知道答案是什么。这种方法既科学又有趣，整个过程不需要第三者参与，仅仅靠AB两人之间的交流即可。这种方法可以让B有充分的理由相信A找到了Hamilton回路，但能保证B仍然得不到任何与正确答案有关的线索。






































    首先，A生成一个100000的全排列P，然后用这个排列P把原图G的顶点标号打乱（对标号进行置换），这样就得到了一个同构的图G'。然后A把图G'告诉给B。注意，目前判断两个图是否同构还没有有效的P算法，因此除非A把排列P也告诉了B，否则B不知道G'和G是不是真的同构。接下来B从下面这两个问题中随机抽一个问题让A作答：叫A证明G与G'同构（即叫A给出排列P，确保他没有作假），或者叫A指出G'中的一条Hamilton回路。反复进行“构造G'—抽问”的过程，每次A答对后B都会更加确信A确实找到了原图G的Hamilton回路，来个十几二十次后A作假的嫌疑基本上可以被排除了。这是因为，如果A不知道原图G中的Hamilton回路，这两个问题他是不可能同时答对的，既然B是抽查的，A不可能每次总能答对。同时，除非B同时知道了两个问题的答案，否则B永远不知道原图G的Hamilton回路是什么。仅仅知道G'的Hamilton回路是没有用的，因为此时B连G和G'是否同构都不知道，更别提找出它们之间的对应关系了。

来源：http://www.zju88.cn/cgi-bin/bbstcon?board=Algorithm&file=M.1200769543

    似乎MM都很喜欢拼图游戏。如果MM过生日你不知道送她什么，送她一副拼图是一个不错的选择（事实上原来我也曾干过这事）。如果你失恋了，或者挂科了，或者这个月没饭钱了，或者怀疑自己的性取向，感到很郁闷的时候，静下心来玩一玩拼图游戏可以让你暂时忘掉烦恼。当你最终完成整个拼图时，你会有前所未有的成就感。当然，只有那些有耐心的人才觉得拼图有趣，像我这样的人肯定拼个十几二十分钟就觉得烦了。计算机搞久了的人往往都很没耐心，同一个操作反复执行的次数多了就觉得很烦，心里总会想这种机械操作交给傻B计算机去做该多省事啊。有时我会想，计算机是否有什么牛B算法可以用来解决拼图问题。今天我们要研究的是，如何把拼图游戏描述成一个信息学问题，计算机是否有更高效的算法来解决这个问题。
    传统的拼图一共有w*h个正方形小块，最终将拼成一个w*h的矩形图案。我们大致有以下两种依据来确定一个小块的位置：根据这一小块上的图案来确定它在整幅图片中的位置，或者从形状上观察这一小块可以和其它哪些块拼接。于是，拼图游戏变成了这样一种交互式的问题：允许你询问某一块是否在指定的位置，或者某两块是否相连，你如何尽早地完成整个拼图。具体地说，你可以：

• 询问拼块A是否在(x,y)上，交互库返回yes/no
  
• 询问拼块A和拼块B是否相连，交互库返回yes/no

    有时候，你并不能把拼图完全当作一个顶点最大度为4的无向图。多数情况下两个拼块只能按某一个方向上的某一种顺序相连。为了更贴近拼图游戏的真实情况，我们可以假定，对于第二个问题如果返回的是yes，则交互库还会告诉你A应该接在B的什么方向。现在的问题是，完成整个拼图最少需要多少次询问？
    假如拼图共有n块，询问的次数不会超过O(n^2)。对于每一个拼块，我都像傻B一样挨着挨着询问“它是不是在这里”，O(n^2)次询问可以保证我完成整副拼图。我们希望知道，是否有算法可以使用O(nlogn)甚至更少的询问次数？



































    答案是否定的。对于拼图问题，计算机并没有英明到哪里去，它也只能像傻B一样一个一个去试。我们下面将证明，不管你怎么努力，询问次数再怎么也不会低于O(n^2)。首先我们需要说明的是，问题2实际上并不能带给我们多大的帮助。

      
    如上图，我们把整个拼图划分成一个一个的“十字架”，并且挖掉每个十字架正中间的那个格子（深灰色的格子）。注意到关于这种划分的三个重要性质：

• 每个浅灰色的格子最多与一个深灰色的格子相邻
  
• 任何两个深灰色的格子都不相邻
  
• 深灰色的格子共有n/5个（可能有常数级别的偏差）

    现在，假如整个拼图里只剩这些被挖掉的深灰色格子还没确定，其它的格子上都已经放好了正确的拼块。再换句话说，在拼图游戏过程中，拼块是否应放在浅灰色的格子里，若可以则应该放在哪个格子，以及浅灰色格子之间的邻接状态都是已经知道的了，只要是不涉及深灰色格子的信息，你要什么我就给你什么。此时，我们只剩下n/5个格子（仍然是O(n)个格子），并且询问1与询问2变得完全等价；你要问拼块A和拼块B是否相邻，还不如直接问拼块是否应放在某个洞里。于是，问题变为这样，只凭借询问1来确定O(n)个拼块的位置需要多少次询问。我们下面证明，O(n^2)次询问是必须的。
    考虑一个二分图，左边n个顶点表示n个拼块，右边n个顶点表示拼图上残留的n个洞。现在，我只能询问指定的两顶点间是否有边，只有当交互库回答了n次yes后拼图才算完成。那么，作为交互库，你应该尽可能返回对游戏者不利的信息，让整个局面往最坏的方向发展。如果叫你来写这个交互库，你该怎么写？容易想到，只要有可能，我都返回no；除非某个时候一旦我再返回一次no，所有没被问过的边和返回过yes的边所组成的二分图不存在一个完全匹配时，我才可能返回yes。我们需要一个二分图存在完全匹配的充分条件来支持我们的这个算法。
    考虑如下定理：如果一个二分图左边右边各有n个顶点，每个顶点都与对面至少n/2个顶点相连，则这个二分图一定存在一个完全匹配。定理的证明很简单。König定理告诉我们，二分图的最大匹配数应该等于最小点覆盖集，而一个图的最小点覆盖与最大点独立集是互补的，它们的和始终等于顶点数|V|（在这里|V|=2n）。因此我们只需要证明，上述二分图的最大点独立集不会超过n。假如我在左边选的顶点数不超过n/2个，则右边最多也只能选n/2个顶点（左边任一个点都已经使右边至少n/2个点废了）；假如我左边选的顶点数超过了n/2个，则右边的顶点一个都不能选（右边每个点都连接了左边至少n/2个点，任选一个都会导致冲突）。总之，最大点独立集不可能超过n，但n显然是可以达到的（取同一边的所有点），那么最小点覆盖集也就是n，即二分图存在完全匹配。
    有了这个定理，下面我就好办了：任何时候，只要每个顶点你都有半数以上的边没问过，我就可以放心大胆的回答no（因为这些没问过的边总可以组成一个完全匹配）；一旦某个时刻有一个顶点被问过了n/2次，那么我就随便找一个完全匹配，把这个点“亮”出来，告诉你这个点应该和哪个点匹配（不计询问次数），然后把这两个匹配了的顶点从图中删去，继续刚才的操作。每次删除一对顶点都会顺带着删掉与它们相连的至少k/2条问过的边，其中k表示当时左边右边各剩下k个顶点。删掉了多少边就表示你曾问过了多少边，因此完成整个拼图你总共问过至少n/2 + (n-1)/2 + ... + 2/2 + 1/2条边，这个数量显然是O(n^2)的。

做人要厚道
转贴请注明出处
参考资料：http://www.brand.site.co.il/riddles/200710q.html