资源描述:
《第8章 图论 topics in graph theory11月18日周二》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第8章图论TopicsinGraphTheory§8.1图GraphsG=V={v1,v2,······,vn}顶点vertex集。E={e
2、e=(vi,vj),vi,vj∈V,vi≠vj}无向边edge集。γ(e)={vi,vj},e的端点endpoints集。简写为G=(V,E)。TD(vi)顶点vi的度数degree:连接到vi的边的条数。连接一个顶点的圈loop算两度。孤立点isolatedvertex:度数为0的点。两个顶点相邻adjacent:有一边相连。定理1.(握手定理)TD=åTD(vi)=2m.推论.任意图的奇数度
3、顶点必有偶数多个。完全图completegraph:任意两点都相邻简单图。定理2.n个顶点的完全图有n(n-1)/2条边。正则图regulargraph:每个顶点都有相同的度数。E={
4、vi,vj∈V}有向边集有向图有向边,vi起点弧尾,vj终点弧头TD(vi):顶点的度degree:以vi为端点的边的数目。OD(vi):出度,以vi为起点的边的数目。ID(vi):入度,以vi为终点的边的数目。TD(vi)=OD(vi)+ID(vi)OD=ID,TD=2
5、E
6、,E
7、=1/2*TDTDODID为整个图的总度,出度,入度数。
8、路径path:vi······vj,以vi为起点vj为终点的顶点序列,相邻顶点相邻。路径的长length:路径上边的数目,简单路径simplepath:点都不重复的路径,回路circuit:首尾相接的路径,简单回路simplecircuit:除起点和终点以外都不重复的路径,vivj连通connected:有路径vi······vj相连。连通图:任意两点都连通的图。例bfgdceafdcaeb左图a,c,d,g是简单路径右图a,d,b,c,e是简单路径。f,e,a,d,b,a,f是简单回路。f,e,d,c,e,f不是简单回路。有向图vivj强连通vi
9、vj连通vjvi也连通,强连通图任意两点都强连通。子图和商图SubgraphandQuotientGraphG=(V,E),G’=(V’,E’)如果V’ÍV,E’ÍE,就称G’是G的子图subgraph。G’的补图:=(V,EE’),G的边集中去掉E’的边。Ge=(V,E’),E’=E{e}.连通分量connectedcomponents:一个图的极大连通子图。一个图可以划分成几个不相交的连通分量。强连通分量strongconnectedcomponents:一个有向图的极大强连通子图。商图quotientgraphR是V上等价关系,V/R={
10、[v]
11、v∈V}E/R={([v],[w])
12、[v],[w]中有相邻的顶点}GR=G/R=(V/R,E/R),称为G模R的商图。把R相关的顶点粘合成一点,相关的边粘合成一边,就得到商图。HomeworkP28510,12,13,18,22§7.4无向树undirectedtrees无向图连通不含回路的图叫无向树例bfgdcead无向树:有向树的对称闭包。定理1.R是对称关系。则下列命题等价thefollowingstatementareequivalent:(TFAE)(a)R是无向树。(b)R连通connected,无回路acycle。定理2.R
13、是对称关系。TFAE(a)R是无向树。(b)R无回路,每增加一条边,都产生一个新的回路。(c)R连通,去掉任意一条边都不连通。定理3.n个顶点的树R,有n-1条边。连通图的生成树spanningtree:含有所有顶点的极小连通图.n个顶点连通图至少有n-1条边。m条边的连通图去掉m-n+1条边可以得到生成树。从连通图中如有回路,去掉回路中的一条边,继续直至没有回路,就得到生成树。从m条边的连通图中得到生成树,要去掉m-n+1条边T是连通图G的生成树,G的每一条不属于T的边e,叫弦。m条边的连通图共有m-n+1条弦。基本回路:每条弦加到T中得到一个回
14、路,叫基本回路。m条边的连通图共有m-n+1个基本回路。割集:G的边集,去掉后G不连通。一条边组成的割集叫桥bridge。树的每条边都是桥。基本割集:生成树T中每一条边,和G中对应于T的所有的弦,组成一个割集,叫基本割集。最小生成树:权重最小的生成树。带权的边:带边长的边。带权的图:每边都带权。Prim算法:设G=,1.令U={v0},T={}.2.对任意u∈U,v∈V-U,(u,v)∈E,找到权最小的边(u1,v1),令U=U∪{v1},T=T∪{(u1,v1)}3.重复2,直至U=V.得到T就是最小生成树。T中共有n-1条边Krusk
15、al克鲁斯卡尔算法G=(V,E)连通图令T=(V,{})是G的所有顶点而无边的非连通图。1.选择E中权值最小的边,若该边连