好久不曾写点有意思的东西了。准备介绍一下图论，也是边学边写，证明一概省略，主要是如何理解。顺便呼应一下昌海的“什么是好的数学”，其中Tao讲到的关键是那个Szemeredi引理。当然，我们的介绍是一个sketch式的。

计划

简介和例子
图的联通性与新闻封锁
匹配问题
极值理论
Szemeredi引理与小世界网络、6度分离、Erdos数
Ramsey理论
随机图与分形和Pareto分布

当然我个人关心的是随机图理论，没有现成的书介绍这个（当然，实际上有一本，05年出版的，手头没有）。
注：因为是边学边写，所以本文的进度就很难说了。另外，本文多半不会关注众所周知的几个问题，比如Hamilton回路以及旅行家问题以及四色问题。

图论的基本概念简单而自明，所以我们不给出其详细定义而是简单地描述一下。一个图由顶点和边构成。边的作用是连接顶点，分作定向和不定向两种类型。更一般的可以对顶点或者边加权，即每一个顶点和每一条边都赋予一个或者多个实数。

图论可以用来描述各种各样的现实问题。下面，我们给出一些例子。

电网：顶点为所有电器，包括变压器、电视等等。边就是电路。两个顶点之间的电位差以及电路的电阻为电网的加权。
互联网：顶点为所有计算机，若两台计算机之间有网线连接，则此连接为一条边。
Euler的哥尼斯堡7桥问题
人际关系网络：顶点为所有的人。两个人之间有一条边，当且仅当，这两个人认识。
传染病网络
通讯网络
网页连接网络：顶点就是网页，若某个网页上有一个超连接指向另一个网络，则称这个连接为一条边。
大脑神经网络。顶点为神经元，边定义为神经元之间的触突连接。
人类社会的信息传播网络。顶点为所有的人、新闻媒体、计算机、报纸、电话等等。注意，这是一个非定向图。

说得广泛一点，所有离散数学都可以归结为图论。

图论中有大量的直观易懂同时很有研究和实用价值的问题。举几个例子。

地图着色问题。这是一个人命关天的大问题。对于平面4色问题已有计算机证明。
一笔画问题。这个比较容易。
Hamilton回路问题。
旅行家问题。或者推销员问题。
社会学上著名的6度分离。小世界网络。

Spectral Graph Theory and Random Graph Theory are interesting...

by the way, graph theory is a good example of comma category

期待gauge兄的作品。

也欢迎kanax有闲暇时写点有关category的文章

不过写这种话题无法配图比较痛苦。。。

我研究生时上的数学课是学位课，是应用数学，里面是图论、组合数学、模糊数学等；读博士时上的数学课是学位课，是应用数学，居然仍然是同一门课，结果我同一门考两次，纯属浪费我的时间，没有任何提高（泛函分析是我自己上的，不是要求的）。学校搞课程设置的人估计TMD是个大白痴，想学的没有开，跟我们专业无关的课重复开，而且非常肤浅。虽然研究生和博士生学位课里都上了图论，都只是重复一点皮毛，不如正常上图论课的本科生学的深。到目前为止我们学校唯一的优博得益于自学成才和在香港呆了半年，而不是自己学校和导师培养出来的，可以说跟导师没有任何关系，反而是导师沾了学生的光。

多谢各位，希望写得尽可能好点。

顶点又称为节点。图、网、网络基本上有相同的含义，当然一般网络是指节点数比较多的图，或者所谓的复杂网络。图的连通性是指图中的任意两点都可以用边将之连接起来。也可定义两个节点之间的连通性。举例。

1，对于人际关系网络来说， 如果A是B的熟人，B是C的熟人，...，P是Q的熟人，则称A,Q在人际关系网络中是连通的。换言之，A,Q两人之间可通过熟人相联系。

2，对于传染病网络模型来说，如果A感染B，B感染C，...，P感染Q，则称A,Q是连通的。

3，对于信息传递网络来说，网络的连通性相当于信息总是可以从任意节点传到另外的任意一个节点。消息封锁就相当于以某种方式切断消息的传递，破坏通信网络的连通性。

我们看看internet的起源。20世纪60年代初，古巴核导弹危机发生，美苏之间的冷战状态随之升温。美国国防部认为：如果只有一个集中的军事指挥中心，万一这个中心被敌方所摧毁，那么整个国家的军事指挥都将处于瘫痪状态，后果不堪设想。因此有必要设计一个分散的指挥系统。这个系统由许多分散的指挥点构成，当部分指挥点被摧毁后其它点仍能正常工作，而这些分散的点又能通过某种形式的通讯网络取得联系。这个网络后来发展成为internet.

通讯网络最重要的功能是在节点之间进行通讯。如果两个节点之间有一条道路相联结，那么总是可以在这两个节点之间交换信息。通常我们还需要考虑信息交换的效率，此处暂时不管这个问题。网络的联通性就保证了任何一个节点的信息都可以传递到其他任意节点。因而对通讯网络的破坏就表现为破坏网络的连通性。对网络的攻击可以从攻击节点和线路两个方面入手。显然对于节点的攻击更加有效，因而我们也仅考虑对于网络节点的攻击。

一般来说，通讯网络面临两种方式的攻击，即随机攻击和智能攻击。在军事对抗中，随机攻击是指攻击者只有关于网络结构的很少知识，因而其对于网络的攻击表现为从网络中随机删除一部分节点。随机攻击的另一种形式是在普通商用环境中节点的自然损坏引起的网络故障。智能攻击是指攻击者对网络拓扑结构有很好的了解，从而可以先攻击重要的连接数较多的节点。

从防御的角度看，网络在某种攻击下的连通性可以作为通讯网络可靠性的标准。有如下几种常用的衡量标准，

1，(Baran) 在遭受破坏后幸存下来的网络中，选出一个最大的连通子网络，其节点数的平均值占原网络节点数的百分比，即为通信网络的连通概率。这里平均值是指对所有样本作平均。

2，(Frank) 在遭受破坏后幸存下来的网络中，任意选取一个节点，所有能与它相连通的节点数占原网络节点数的百分比。

3，整个网络构成一个连通网络的概率。

对这种网络的研究通常采用的是计算机模拟。也可以从概率统计上作一些理论上的研究。

网络的统计结构定义如下。假设网络中所有的节点为：A,B,...,P,Q. 与每个节点相连的边的个数满足一定的分布规律。这一分布规律即称为网络的统计结构。实际上这是随机网络的一个概念。

网络统计结构有两种典型的方式。

1，节点的连接数符合正态分布，这时称之为随机网络。严格的来说，有限网络的节点连接数不可能符合正态分布，所以需要取极限，即节点数趋向于无穷。

2，节点的连接数符合幂律分布，这时称之为无标度scale-free网络。

大致上说来，随机网络中所有节点都差不多是平等的。据说这是internet 网的前身APARnet设计的初衷之一，然而实际上现在的大型网络差不多都是无标度网络。由此看来，即使设计者也很难预料以后的发展。

现实世界中大量的网络都是无标度网络。比如internet,人际关系网络。无标度网络的重要特点是其中某些节点的连接数很大，称为核心节点。同时其中有大量的节点，其连接数相当少。无标度网络对于随机攻击有很好的抵抗能力。但是，这种网络对于智能攻击的抵抗能力很差。注意到智能攻击是首先破坏那些连接数很多的节点。反过来说，对于无标度网络的保护也可以主要针对核心节点来进行。

无标度网络这个概念的明确化也是很晚的，几年之前学术界才统一口径。比如是否仅仅要求服从的分布在尺度变换下具有不变性，若此，则对数正态分布也是可以的。

随机网络对于两种形式的攻击都是稳健的。
从通讯的效率上比较，无标度网络比随机网络更加有效。

很容易理解具有正态分布的随机网络的生成机制，所以就不多讲了。

再来看无标度网络的生成机制。其中最重要的一个机制是Barabosa给出的，论文发表在Nature letters上。这个网络的生成过程如下，

初始化，首先有一个节点。

生成过程，对于一个给定的网络，其中的节点连接数已知。在此基础上增加节点和边。使得，新增加的边与节点之间的连接概率等于每个节点连接数在总连接数中的比率。确切的说，假设节点为x_1,x_2,...x_n. 与节点x_i相连接的边数为k_i. 总的边数为k=k_1+k_2+...k_n.节点x_i处的加权为p_i=k_i/2k. 则新增加的边与x_i相连接的概率为p_i.

可以用一句话来概括这个规则：你新认识的人是比较容易认识的那个。比如学校里面同一个系的同事中，你最有可能认识的是系主任而不是那些不显眼的。在交际场合，你认识交际花的可能性大于认识Jane的可能性。一个刚刚建立的网站，总是打破脑袋要和google,yahoo这些大的网站连接起来。简而言之，富者越来越富，受到关注的人、明星受到更多的关注，无人关注的始终无人理睬。当然这个说法不太精确，有疑问可参考前一段，这里的说法是文字叙述，自然会带有一定的不确切性。在经济学上，个人收入据称也符合幂律，此时叫做Pareto分布。大概也是同样的机制。

顺便说一句。Pareto分布据信和分形理论有关联。这来源于分形通常具有所谓的自相似性，这个自相似性产生的根源一般没什么人认真考虑。不知道是不是与Barabosa机制有关。

我们来看消息封锁问题。信息传播网络差不多是一个无标度网络。信息传播中有两个要素，其一是接受信息的人，其二是媒体，包括电台、网站、报社等等。消息封锁是指切断信息流通的途径从而使得人们接受不到信息。消息封锁由两种形式。其一，阻断人们接受信息的途径，这相当于破坏通信网络的边，这一方式效率较低。其二，禁止媒体传播信息，这相当于破坏无标度网络的核心节点。实际上对于消息的封锁基本上都是禁止媒体进行传播。人们之间的通信方式随着时代的不同而变化，当前的手段包括信件、电话、短信、面谈等等。每个人都可以很容易的和数十个甚至上百个人相联系并通信。这样的网络很难被切断成为不连通的，除非以某种方式强制关掉大部分通信设施，比如电台、报社、卫星、电话交换机、网络路由器等等。我们前面提到过的对于网络连通的可靠性指标，可以用到此处来衡量在当前的社会，封锁新闻、消息的可行性。结论很显然，封锁消息没有可行性。这个结论不以人的意志为转移，不是一个物理定律或者社会规律，而是一个关于随机图的概率论定理。

网络在攻击下的连通性又称为网络的健壮性。现在的internet，其健壮性并不太好。八卦消息说几年前某个渔民刮断了中美之间的海底光缆，造成了长达250小时的网络中断。

补充说明。随机网络有两种含义，

1，一般的随机网络，所有带有概率加权的网络都可叫做随机网络。

2，狭义的随机网络，这是我们在前一节使用的说法。当然可以将之称为正态分布型随机网络。

相比较而言，通常的图论研究的是所有网络都要满足的性质。因为某些网络具有很坏的特性，使得这种方式得到的结论显得很弱。原因在于这种很坏的网络可能很少，因而不具有一般性。这些网络没有戴表，只是一小撮、少数而已。这也是概率论的要点，可以作为代表的不是几个，而是大多数。少数几个人戴表是没有用的，代表不了一般人。

大本时，考运筹学，35分，全系最低。因为根本不学。其实我对图论还是很有兴趣的，但是对运筹学中的其他一点兴趣都没有，呜呼~

运筹学 = 网络流 = 线形优化问题

看gauge兄写的，我觉得自己就跟从来没有学过图论一样。可能我学的充其量相当于给小学生看的科普。这不奇怪，我们学校有个博导给博士上专业必修课，结果被他上成低级科普，而他自己的水平也只能看低级科普，还不如我们这些前去上课的到上面给他上上课。把利用权力把自己的课弄成专业必须课，害得我浪费时间不得不去上他的，40个学时最多讲了六节课，这样的人还当上院长，看来在中国越是混混越是容易当官。

By the way.顺便谈一下幂律分布。幂律分布也叫做Pareto分布，是指概率分布函数的形式为F(t)=P(X<t)=1-a/x^k.其中，a,k为适当的常数，a,k>0.

据称Pareto分布极其广泛，比如，
1，月球上的陨坑直径分布
2，沙子的直径分布--注，某些人还这样认为。
3，个人受入。关于这一点没有绝对可靠的数据。很容易注意到，这个分布严重背离文科经济学家挂在嘴角的橄榄型分布。
4，与分形有关的一些分布。
其他还有很多。

同样是那个匈牙利人Barabosa,在Nature letter上的另一篇文章中研究了人们使用电子邮件的情况。一个很详细的研究，以天为单位，研究了某大学大约1700个人在230天中使用email的情况。比如，每个人每天发送的邮件数量、两个邮件之间的时间间隔、阅读邮件以及回复所需的时间等等。Barabosa又一次得出一个幂律分布。以前很多人认为这个分布应该是Poisson分布或者指数分布。指数分布按指数衰减，在时间较长时，服从指数分布的随机事件发生的概率很快的趋向于0，以致于几乎不可能发生。而幂函数衰减的比较慢，因而有些事件发生的相隔时间可以很长。通常，这一点被称为fat tail或者long tail，即重尾或长尾。在概率分布函数的图像上，是一个按照1/x^k趋向于0的曲线。

Barabosa进而认为人类的很多活动的时间间隔都服从幂律分布。据此，Barabosa进一步提出了一种机制来解释为什么人类活动满足幂律分布。我们可以观察到人类活动的两种典型方式。其一，先来者先得到服务，比如在食堂排队买饭。其二，按照优先级安排，比如老板布置的任务，一般来说，其优先级高于看电影。可以类比，计算机的CPU进程是按照一定的优先级别进行安排的。优先级高的先执行，低的后执行。Barabosa认为正是这种按照优先级分配任务的方式导致了幂律分布。

这个工作在Nature letters上发表。Nature letters是Nature系列中排在最前面的。

然而，Barabosa对于数据的统计分析有严重的缺陷。比如，一个人是否可能在1秒钟之内打开邮件阅读邮件并回信呢？剃除掉这些不合常理的数据，剩下的数据符合对数正态分布。对数正态分布表明人的活动几乎是随机的。对此，某些统计学家质疑Nature letters的编辑是否具有足够的能力来审阅这一稿件。

Gauge兄的这个系列值得期待，希望能够不断继续。在此将粗读一遍过程中发现的问题用英文点评一下：

>>1，节点的连接数符合正态分布，这时称之为随机网络。严格的来说，有限网络的节点连接数不可能符合正态分布，所以需要取极限，即节点数趋向于无穷。

The Erdos-Renyi (ER) model of a random network starts with N nodes and connects each pair of nodes with probability p, which creates a graph with about pN(N-1)/2 randomly placed links. So the node degrees should follow a Poisson distribution (rather than a normal distribution, which only applies to a continuous random variable).

>>再来看无标度网络的生成机制。其中最重要的一个机制是Barabosa给出的，论文发表在Nature letters上。

I never heard of the name "Barabosa" and I guess you are really referring to the famous Albert-László Barabási. Also, there is no such journal named "Nature letters", I think you are referring to one of Barabasi's Nature paper. Could you give the exact reference source of this paper?

>>这个工作在Nature letters上发表。Nature letters是Nature系列中排在最前面的。

I guess you are talking about the short article category known as "Letters to Nature" within the journal "Nature" itself. The highest ranking Nature sister journal should be "Nature Genetics", “Nature letters" doesn't even exist.

One of your Barabasi references should be the following one-page correspondence published in 2005 ---

J. G. Oliveira & A.-L. Barabási Nature 437, 1251 (2005)

>>同样是那个匈牙利人Barabosa,在Nature letter上的另一篇文章中研究了人们使用电子邮件的情况。

After checking Barabasi's homepage (http://www.nd.edu/~alb/), I'm pretty sure you are referring to his following 2005 Nature paper ---

Barabasi, A.-L. (2005) "The origin of bursts and heavy tails in human dynamics", Nature 435:207-211.

>>然而，Barabosa对于数据的统计分析有严重的缺陷。比如，一个人是否可能在1秒钟之内打开邮件阅读邮件并回信呢？剃除掉这些不合常理的数据，剩下的数据符合对数正态分布。对数正态分布表明人的活动几乎是随机的。对此，某些统计学家质疑Nature letters的编辑是否具有足够的能力来审阅这一稿件。

Could you also give the reference sources of those statisticians' criticism on Barabasi's analytical flaws?

Omni兄指出了几个初级错误，多谢。这两篇文章我是在上个学期翻过一下。而且不熟悉非数学类期刊的名称。而且我个人对于这个一般记得不准。甚至连人的名字都拼错了，主要是那个匈牙利人的名字平不出来。不过本来是准备写完后再列举参考文献的，那时可能也会意识到问题所在。因而要更正一下，正如Omni兄所言。文献如下，

A.L.Barabasi,The origion of bursts and heavy tails of human dynamics,nature,207-211,Vol 435,12 May 2005.
这一篇论文是关于人类活动的幂律分布。

Daniel B. Stouffer, R. Dean Malmgren, Luıs A. Nunes Amaral，Comment on The origin of bursts and heavy tails in human dynamics.
这篇论文对Barabasi的数据处理方式提出了质疑，不知发于何处。我找到这篇文章的原因大概是因为我看着幂律分布就不舒服。因为当时我不知道幂律分布有什么内在机制。如果我现在才看到Barabasi结果，那么我多半不会去搜索这样一篇对之提出质疑的论文。

上述三个人的另一篇文章，Log-normal statistics in e-mail communication patterns,25 May 2006.

Omni兄可以由下面的网页开始，是Crshalizi的个人主页，有前因后果的详细介绍
http://www.cscs.umich.edu/~crshalizi/weblog/390.html

现在我个人的观点是，Barabasi的这篇论文是错的。从常理来看，由Email的使用推断人的活动，未免有点离谱。

如果Omni兄对log-normal感兴趣，有一篇不错的论文
Log-normal distributions, across the science, keys and clues, BioScience 341-352, May 2001/Vol.51 No.5.

Albert-Laszlo Barabasi, Reka Albert,Emergence of scaling in random networks,Science 286, 509 (1999)
这篇论文是关于幂律的生成机制，发表在Science上, 记错了，记成是发表在Nature上了。按照我们在前面的贴子里面叙述的方法，得到的幂律分布的指数有限制，只能为3.本文作者实际上进一步说明了如何得到一般指数。

我说的随机网络与Erdos-Renyi图，有点区别。其实随机性有多种表现方式我想只要节点连接数分布是指数型的，都可以叫做随机网络，包括正态分布和其他的更一般的Weibull分布等等。也许应该在随机图这个名字中再添一类，亦即，随机图这个说法实际上有至少3种含义。对这一点，我还需要了解一下再说。如有错误，下次来纠正。

范畴虽然可以看成一个图 但是很多信息丧失了

另外quiver也是一个有向图

各位老师，学生想问一个问题：顶点色数为k的临界图的最小度是k-1吗？其中k=4,5.
我倾向于这个命题成立，因为它蕴涵4CT。但不排除有哪位老师很快给出反例。谢谢！

太忙，这个系列恐怕得往后推了。

No problem, I will collect the above pieces first.

我在信息学竞赛中接触过图论，LZ说的图论经典问题中有NP问题

原来学过一点Approximation Algorithms 一直有个问题
比如说TSP问题,在没有加triangle inequality的时候 是没有多项式近似算法的(没记错的话)
而加了以后就有多项式近似算法了,这个是为什么? 也就是说加进了一个metric(当然满足三条性质,另metric=weights)这个问题似乎变的好处理了,从直观上理解当然可以说:"加进来一个constraints,把一些很乱的情况排除在外了"但是这并不能解释我的这个疑虑. 更进一步 这个有metric的TSP 的approximation ratio好象是1.5, 用的是round cutting and maximal perfect matching的方法. 而如果我把Eculidean度量引进来,也就是说每个点都有坐标了,这样我甚至可以得到1+epsilon的近似比(多项式时间内), 想问这是为什么.

我对这些问题,楼主你所说的那个关于健壮性的描述很吸引我,即: 一个图去掉一些点和边仍然连通.我觉得很有意思.

：：（当然，实际上有一本，05年出版的，手头没有）。

gauge兄这本书的具体名字是什么？

that's becasue triangle inequality = convex [in some sense]. convex make optimization easy.