文库发布：2023图论1上传

图论

第一节课程概述参考书参考书《图论引导》，DouglasB.West，机器工业出版社教学周历图的基本概念树、生成树、最优树、有序二元树、追捕问题平面图、Euler公式、灌木生长算法匹配理论、图的因式分解着色问题、四色证明、Ramsey数Euler图、Hamilton图、邮递员问题有向图、强弱连通、循环赛最大流、2F算法、Dinic分层算法、网络流连通度、边数最少的k连通图图的线性空间与矩阵图论中的NPC问题及算法分析习题课与考试考核方法书面作业及报告20%课外编程项目10%期末闭卷考试70%课程特点图论是研究点与线的学问图论是组合数学的一个分支图论交叉运用了拓扑学、群论和数论图论中的定理证明有的显而易见、有的令人费解图论是一项强大而灵活的科学分析工具图论是形式语言、数据结构、分布式系统、操作系统理论的数学基础高速数字计算机

5树3七桥问题欧拉

1游戏博弈问题

2四色猜想4七桥问题如何不重复的走完七座桥？七桥问题抽象9完全对偶图网络通讯旅行社航空公司连接游戏博弈问题数据结构中的树四色问题可否用四种颜色标示所有的地图？高速计算第一章图图的应用

6图的性质3通路与回路4图的基本概念1图的表示、分类2图的连通性5第一章学习要求重点掌握一般掌握了解1图的概念特殊图图论的基本定理通路与回路图的连通性3图论的典型应用

2图的同构图的构成与证明

图的基本概念图的定义考虑一张航线地图，图中用点表示城市，当两个城市间有直达航班时，就用一条线将相应的点连接起来。这种航线地图的一部分如下图所示；长春北京成都武汉上海图的基本概念

假设有4台计算机，分别标记为A、B、C和D，在计算机A和B、C和D以及B和C之间有信息流。这种情形可用下图表示，通常称这种图为通信网络；ACDB图的基本概念

假设有一群人和一组工作，这群人中的某些人能够做这组工作中的某些工作。例如，有3个人A、B和C，3件工作D、E和F，假设A只能做工作D,B能做工作E和F,C能做工作D和E。则这种情形可用下图表示，其中，在人和这个人能够做的工作之间画有线。ACFDBE基本思想

用图形表示一组对象，其中有些对象对是有联系的。对于这种图形，我们感兴趣的只是有多少个点和哪些结点之间有线连接，至于连线的长短曲直和结点的位置却无关紧要，只要求每一条线都起始于一个点，而终止于另一个点。图的定义

一个图(Graph)是一个序偶<V,E>，记为G=<V,E>，其中：（1）V={v1,v2,…,vn}是有限非空集合，vi称为结点(NodalPoint)，简称点(Point)，V称为结点集(NodalSet)。（2）E是有限集合，称为边集(FrontierSet)。E中的每个元素都有V中的结点对与之对应，称之为边(Edge)。图的表示形式化：对于一个图G，如果将其记为G=<V,E>，并写出V和E的集合表示称为图的集合表示。图形化：用小圆圈表示V中的结点，用由u指向v的有向线段表示有向边<u,v>无向线段表示无向边(u,v)，称为图的图形表示。图论的艰苦从许多实例中，我们发现图论最吸引人的特色是它蕴含着大量强有力的思想、漂亮的图形和巧妙的论证，即使是非常困难的尚未解决的问题也易于表达。问题外表的简单朴素和本质上的难以解决，使每个搞图论的人在图论面前必须谨慎严肃地思考问题。常常是貌似简单的问题，即使幸运地得出证明，证明中包含的细节也十分之繁琐，并且往往运用了极艰苦的计算。钻石与足球烯足球烯应用在超导、太阳能电池、护肤品数学领先其他科学100年妖怪（snark）妖怪图每个点都关联着3条边，用4种颜色可以把每条边涂上颜色，使得有公共端点的边异色，而用3种颜色办不到，切断任意3条边不会使它断裂成2个有边的图。单星妖怪双星妖怪更多妖怪Hamilton旅行游戏货郎担问题TSP（TravelingSalesmanProblem）假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。NPC问题Ramsey定理在一群人数不少于三的人群中，若任意两人都刚好只有一个共同认识的人，这群人中总有一人是所有人都认识的。对于所有的N顶图，包含k个顶的团或q个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,q)莱昂哈德·欧拉(LeonhardEuler)

瑞士的数学家和物理学家。他被称为历史上最伟大的两位数学家之一（另一位是卡尔·弗里德里克·高斯）。欧拉出生于瑞士，在那里受教育。他是一位数学神童。作为数学教授，他先后任教于圣彼得堡(1727-1741)和柏林，尔后再返圣彼得堡(1766)。欧拉的离世也很特别：据说当时正是下午茶时间，正在逗孙儿玩的时候，被一块蛋糕卡在喉头窒息而死。欧拉是第一个使用“函数”一词来描述包含各种参数的表达式的人，例如：y=F(x)(函数的定义由莱布尼兹在1694年给出)。他是把微积分应用于物理学的先驱者之一。欧拉是有史以来最多产的数学家，他的全集共计75卷。欧拉实际上支配了18世纪的数学，对于当时新发明的微积分，他推导出了很多结果。在他生命的最后7年中，欧拉的双目完全失明，尽管如此，他还是以惊人的速度产出了生平一半的著作。小行星欧拉2002是为了纪念欧拉而命名的。Euler卡尔·弗里德里希·高斯高斯能完整地背出圆周率——是倒着背。

高斯口渴时会用塔斯基悖论弄出更多橙汁。

高斯不能理解随机过程，因为他能预测随机数高斯小时候，老师让他算从1到100的和。他计算了这个无穷级数的和，然后一个一个地减去从100开始的所用自然数。而且，是心算。

一位数学家、一位物理学家、一位工程师走进酒吧，酒吧招待说：“您好，高斯教授。”

询问高斯一个命题是真的还是假的，构成了一个严格的证明。有一次高斯证明了一条公理，但他不喜欢它，所以他又证明了它是假命题。高斯通过在证明结束时省去“QED”来保护热带雨林。有一次高斯在森林里迷路了，于是他加了几条边把它变成了一棵树。高斯用奥卡姆剃刀剃胡子。图论第一节课图的表示有序与无序

定义中的结点对即可以是无序的，也可以是有序的。ACFDBE

若边e与无序结点对(u,v)相对应，则称e为无向边(UndirectedEdge)，记为e=(u,v)=(v,u)，这时称u、v是边e的两个端点(Endpoint)。若边e与有序结点对<u,v>相对应，则称e为有向边(DirectedPoint)(或弧)，记为e=<u,v>，这时称u为e的始点(InitialPoint)(或弧尾)，v为e的终点(terminalPoint)(或弧头)，统称为e的端点。例题

设图G=<V,E>，这里V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6}，其中e1=(v1,v2)，e2=<v1,v3>，e3=(v1,v4)，e4=(v2,v3)，e5=<v3,v2>，e6=(v3,v3)。试画出图G的图形，并指出哪些是有向边，哪些是无向边？解G的图形如下图所示。G中的e1、e3、e4、e6是无向边，e2、e5是有向边。v3e1e2e3e5v2v1v4e4v5e6例题设图G=<V,E>的图形如下图所示，试写出G的集合表示。12345解图G的