资源描述：
《图论第02讲 阙夏制作(免费).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图论GraphicTheory阙夏制作内容回顾图论的发展史；图论中著名的问题：七桥问题；哈密顿回路问题；四色问题；第一章图的基本概念§1引论§2图的概念§3道路和回路§4图的矩阵表示法§5中国邮路问题§6平面图五、Ramsey问题1928年，英国数学家Ramsey提出了Ramsey数与相关理论，直观的讲，就是：任意6个人在一起，6人中要不是有3个人彼此相互认识，就必然有3个人相互不认识；即两种情况至少存在一种。记作：r(3,3)=6推广：r(p,q)是任给出的人群中必有p人彼此认识或有q人彼此不相识的最小值。鸽巢原理有n+1只鸽子进入n个笼子，那么必然有至少两只
2、鸽子在同一个笼子中。Ramsey问题的证明证：设6个人分别用顶点v1,v2,v3,v4,v5,v6表示。任取一点vi，它与其他5点联线中，至少有3条同为实线或3条同为虚线：vjvivjvpvqvivpvq或实线表示相互认识虚线表示相互不认识证毕。Ramsey问题－2而5个人的人群，可能出现既没有3个人彼此不认识，也没有3个人相互认识，如下图：v1v3v2v5v4实线表示相互认识虚线表示相互不认识所以r(3,3)≥6>>六、Ramsey问题自Ramsey在1928年提出了Ramsey数与相关理论80多年以来，至今求得的Ramsey数仅仅9个，它们是：r(3,3)=
3、6,r(3,4)=9,r(3,5)=14,r(3,6)=18,r(3,7)=23,r(3,8)=28,r(3,9)=36,r(4,4)=18,r(4,5)=25.Ramsey问题－3计算Ramsey数是一个NPC问题，匈牙利数学家厄尔多斯（Erdos）曾用下面的话比喻计算Ramsey数的艰巨性：某年某月某日，一伙外星强盗入侵地球，并威胁到，若不能在一年内计算出r(5,5)，他们便灭绝人类！面对危机，人类最好的选择是调动地球上所有的计算机、数学家、计算机专家，日以继夜的计算r(5,5)，以求人类免于灭顶之灾；如果外星人威胁说要求得r(6,6)，那我们别无选择，只能
4、和外星人战斗到底了！>>思考题1、试证明9人中必有3个人相互认识或4个人相互不认识，两者必居其一。六、妖怪（snarkgraph）妖怪图每个点都关联着3条边，用4种颜色可以把每条边涂上颜色，使得有公共端点的边异色，而用3种颜色办不到，切断任意3条边不会使它断裂成2个有边的图。单星妖怪双星妖怪七、过河问题参看课本p7~p11。八、路径问题顶点v1～v7代表七座城市，有方向的边vivj表示从vi城到vj城的单行车道，问从v1城到v7城有无道路相通？如下图所示：v1v2v3v4v5v6v7二、路径问题－1通过观察上图容易得出解答。如果我们进一步问：若v1城到v7有道路
5、相通，共有几条不同的道路？二、路径问题－2为此引入矩阵：0，若从点到点无边相连。＝＝1，若从点到点有边相连；二、路径问题－3v1v2v3v4v5v6v7A＝010010000000000100011101010110010100010000000001012345671234567二、路径问题－4A·A＝1001010000000000100101201131112020101000110010000＝＝01001000000000010001110101011001010001000000000100100100000000001000111010101100
6、101000100000000010×＝0×0＋1×0＋0×0＋0×1＋1×1＋0×0＋0×0＝1二、路径问题－5一般有：＝＝＝其中：·A＝1120201000000001100112141221230215200100100100011＝＝其中：＝二、路径问题－6现在来看看的值有什么实际意义。以为例：＝＝＋＋…＋当且仅当表示从出发两步到达的路径数目同理表示从出发k步到达的路径数目若要追问这一路径是什么？途经哪几个点？只要回溯是如何形成即可求得二、路径问题－7例如，我们来看一下它的形成过程：＝＝＝（1120201）010010000000000100011101
7、0101100101000100000000010（1001010）×0100100000000001000111010101100101000100000000010＝（0100100）×（1001010）＝（0100100）＝××＝154154715415155447二、路径问题－8对于如何证明v7没有道路走到v1，大家可以参看课本P6～P7。上例只是讨论从一点到另一点是否有路相通？有几条路相通？思考：若存在多条路相通，哪一条是最短的？由此可见图论中蕴含着强有力的思想、漂亮的图形和巧妙的理论，即使是非常困难尚未解决的问题，它的表述也可以是非常平易的。图论是最
8、接近百姓生活、最容易阐述
