资源描述：
《14 第十四次课(图论)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、图论最早处理的问题是哥尼斯堡（konigsberg）城pregel河上的七桥问题。1736年，瑞士数学家L.Eluer在他发表的“哥尼斯堡七座桥”的著名文章中阐述了解决这个问题的观点，从而被誉为图论之父。问题是这样的：在公元十八世纪的东普鲁士有个哥尼斯堡城（后属于苏联立陶宛苏维埃社会主义共和国，现名为加里宁格勒；现属于立陶宛共和国）。哥尼斯堡城位于pregel河畔，河中有两个岛，城市中的各个部分由七座桥相连。当时，城中的居民热衷于这样一个问题，从四块陆地的任一块出发，怎样才能做到经过每座桥一次且仅一次，然后回到出发点。问题看来并不复杂，但当地的居民和游人做了不少的尝试，却都没有取
2、得成功。7/18/20211HongzhiQiao,XiDianUniv.ABCD图1图实际上是反映了客观事物之间的相互关系DCAB图27/18/20212HongzhiQiao,XiDianUniv.后来，在1736年，瑞士的数学家L.Euler解决了这个问题。他将四块陆地表示成四个结点，凡陆地间有桥相连的，便在两点间连一条线，这样图1就转化为图2了。此时，哥尼斯堡七桥问题归结为：在图2所示的图中，从A,B,C,D任一点出发，通过每条边一次且仅一次而返回出发点的回路是否存在？欧拉断言这样的回路是不存在的。理由是：从图2中的任一点出发，为了要回到原来的出发点，要求与每个点相关联的
3、边数均为偶数。这样才能保证从一条边进入某点后，再从另一条边出去，从一个点的不同的两条边一进一出才能回到出发点，而图2中的A,B,C,D全是与奇数条边相连，由此可知所要求的回路是不可能存在的。LeonhardEuler（1707-1783）瑞士数学家7/18/20213HongzhiQiao,XiDianUniv.图/Graph：可直观地表示离散对象之间的相互关系，研究它们的共性和特性，以便解决具体问题。第八章---图论7/18/20214HongzhiQiao,XiDianUniv.8.1图的概念/IntroductionofGraph[定义]图Ｖ是一个非空有限集，Ｅ是Ｖ上的一个
4、二元关系，有序对（Ｖ，Ｅ）称为有向图/DirectedGraph。若将E中的有序对看成是无序的（即将e=(a,b)看成e={a,b}），则称（Ｖ，Ｅ）为无向图/UndirectedGraph。有向图和无向图统称为图/Graph，记为G。G=（Ｖ，Ｅ）第八章---图论7/18/20215HongzhiQiao,XiDianUniv.[定义]顶点：Ｖ中的元素称为顶点，用带标记的点表示，也称为结点/Vertices。[定义]边：在有向图G中，若e=（ａ，ｂ）∈Ｅ，e称为G的有向边/directededge。用由ａ到ｂ带箭头的线把ａ和ｂ连起来；在无向图G中，若e=（ａ，ｂ）∈Ｅ，e称为G
5、的无向边/undirectededge。a、ｂ间用连线连结，有向边和无向边统称为G的边/edge。第八章---图论7/18/20216HongzhiQiao,XiDianUniv.8.2图的术语/GraphTerminology[定义]相邻和关联：在无向图G中，若e=（ａ，ｂ）∈Ｅ，则称ａ与b相邻/adjacent，或边e关联a、ｂ/incident或联结a、b/connect。a、b称为边e的端点或结束顶点/endpoint.在有向图G中，若e=（ａ，ｂ）∈Ｅ，即箭头由ａ到ｂ，称ａ相邻到ｂ，或a关联或联结b。a称为e的起点/initialvertex，b称为e的终点/termi
6、nalorendvertex。第八章---图论7/18/20217HongzhiQiao,XiDianUniv.[定义]自回路：若（ａ，ａ）∈Ｅ，（{ａ，ａ}∈Ｅ），称边（ａ，ａ）（{ａ，ａ}）是自回路/loop。[定义]孤立顶点：若ａ∈Ｖ，ａ不与其他顶点相邻，称ａ为孤立顶点/isolated。第八章---图论7/18/20218HongzhiQiao,XiDianUniv.[定义]顶点的次：在无向图G中，与a相邻的顶点的数目称为a的次或度/degree。记为deg(a)或d(a)。在有向图G中，以a为终点的边的条数称为a的入次或入度/in-degree。记为deg–(a)或d–
7、(a)。以a为起点的边的条数称为a的出次或出度/out-degree。记为deg+(a)或d+(a)。第八章---图论7/18/20219HongzhiQiao,XiDianUniv.[定理1(Handshaking)]设无向图G=（V，E）有e条边，则G中所有顶点的次之和等于e的两倍。证明思路：利用数学归纳法。第八章---图论7/18/202110HongzhiQiao,XiDianUniv.[定理2]设有向图G=（V，E）有e条边，则G中所有顶点的入次之和等于所有顶点的出次之
