资源描述：
《第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中权值最小的边，若该边连
