图论与网络流理论.ppt

《图论与网络流理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论与网络流理论二〇一二年十月十日第一章图的基本概念1.1图的基本概念1.2最短路问题1.3数及其性质1.4生成树与最小生成树1.5图的中心与中位点1.6图的矩阵表示1.1图的基本概念图（graph）定义：一集元素及它们之间的某种关系称为图。一个图G是指一个二元组(V(G),E(G))，其中:1）是非空有限集，称为顶点集，2）E(G)是顶点集V(G)中的无序或有序的元素偶对组成的集合，即称为边集,其中元素称为边.图G的阶是指图的顶点数

2、V(G)

3、,用v来表示；图的边的数目

4、E(G)

5、用来表示.表示图，简记用也用来表示边2图的

6、图示通常，图的顶点可用平面上的一个点来表示，边可用平面上的线段来表示（直的或曲的），这样画出的平面图形称为图的图示。3一些术语和概念边和它的两端点称为互相关联。与同一条边关联的两个端点称为相邻的顶点，与同一个顶点关联的两条边称为相邻的边。两端点重合的边称为环边。若一对顶点之间有两条以上的边联结，则这些边称为重边。既没有环边也没有重边的图，称为简单图。任意两顶点都有一条边的简单图,称为完全图。记为Kv.边集为空的图称为空图。边集为空且只有一个顶点的图成为平凡图。边集和顶点集都为空的图称为零图。图G中顶点v所关联的边的数目（环边

7、计两次）称为顶点v的度，记为dG(v)或d(v)。图G的最大度：Δ(G)=max{dG(v)

8、vV(G)};图G的最小度：δ(G)=min{dG(v)

9、vV(G)};各个顶点的度都相等的图称为正则图。每个顶点的度都等于k的图称为k-正则图。设G是一个图，以V(G)为顶点集，以｛(x,y)

10、(x,y)E(G)｝为边集的图称为G的补图，记为定理1.1.1对任何图G，其各顶点度数之和等于边数的2倍，即证明：按每个顶点的度来计数边，每条边恰数了两次。推论1.1.1任何图中，奇数顶点的个数总是偶数（包括0）。4子图5图的并、联和对称差

11、设G1、G2是两个图：G1、G2的并是指图（V1UV2，E1UE2），记为G1UG2若V1∩V2=Ф，则G1UG2称为不交并（和）记为G1+G2A、B两集合，(A∪B)−(A∩B)称为A与B的对称差。设两个相同顶点集的图G1=（V，E1）；G2=（V，E2），则图（V，E1E2）称为G1、G2的对称差。6路和圈图G中一个点边接续交替出现的序列称为图G的一条途径，其中分别称为途径W的起点和终点，W上其余顶点称为中途点。图G中边不重复出现的途径称为迹。图G中顶点不重复出现的迹称为路。图G中起点和终点相同的途径称为闭途径。图G中边

12、不重复出现的闭途径称为闭迹，也称为回路。中途点不重复的闭迹称为圈。注：（1）途径（闭途径）、迹（闭迹）、路（圈）上所含的边的个数称为它的长度。（2）简单图G中长度为奇数和偶数的圈分别称为奇圈(oddcycle)和偶圈(evencycle)。（3）对任意，从x到y的具有最小长度的路称为x到y的最短路（shortestpath），其长度称为x到y的距离(distance)，记为d(x,y)。（4）简单图G中最短圈的长度称为图G的围长(girth)，最长圈的长度称为图G的周长(circumference)。例1.1.2设G是一个简

13、单图，若δ(G)≥2，则G中必含有圈。证明：设G中的最长路为P=v0v1……vK。因d(v0)≥2，故存在与相异的顶点v与相邻。若v∉P，则得到比P更长的路，这与P的取法矛盾。因此必定定v∈P，从而G中有圈。证毕。例1.1.3设G是简单图，若δ(G)≥3,则G必有偶圈。证明：设P=v0v1……vK是G的最长路。因为d(v0)≥3，所以存在两个与v1相异的顶点v′,v′′与v0相邻。v′,v′′必都在路P上，否则会得到比P更长的路。无妨设v′=vi,v′′=vj,(2

14、P上v0到vi的一段与边v0vi构成一个偶圈；若i,j都是偶数，则路P上vi到vj的一段与边v0vi及v0vj构成一个偶圈。证毕。7二部图二部图(bipartitegraph)：若图G的顶点集可划分为两个非空子集X和Y，使得G的任一条边都有一个端点在X中，另一个端点在Y中，则称G为二部图（或偶图），记为G＝(X∪Y,E)或G=(X,Y)，(X,Y)称为G的一个顶点二划分。完全二部图(completebipartitegraph)：在二部图G＝(X∪Y,E)中，若X的每个顶点与Y的每个顶点有边连接，则称G为完全二部图；若

15、X

16、

17、=m，

18、Y

19、=n，则记此完全二部图为Kmn。定理1.1.2一个图是二部图当且仅当它不含奇圈。例1.1.5判断下列图是不是二部图。解：Herschel图的一个顶点二划分如下：可见Herschel图是一个二部图。Peterson图中含有奇圈，因此不是二部图。8连通性图中两点的连通：如果在图G中