数据结构与算法王曙燕chapter7图

D,A>,<E,C>}7.2图的基本概念2019/9/44*第7章图无向图:由顶点集和边集构成的图称作无向图。例如:其中V2={A,B,C,D,E,F}E2={(A,B),(A,E),(B,E),(C,D),(D,F),(B,F),(C,F)}若<v,w>VR必有<w,v>VR,则以(v,w)代替这两个有序对,称v和w之间存在一条边。ABCDEF7.2图的基本概念2019/9/45*有向图或无向图中的弧或边带权后的图分别称作有向网或无向网。第7章图ABCDE15911732217.2图的基本概念2019/9/46*第7章图名词和基本术语例如:设图G=(V,{VR})和图G=(V,{VR}),且VV,VRVR,则称G为G的子图。ABCDEBCDAEDA7.2图的基本概念2019/9/47*第7章图名词和基本术语假设图中有n个顶点,e条边,则含e=n(n-1)/2条边的无向图称作完全图;含e=n(n-1)条弧的有向图称作有向完全图;若边或弧的个数e<nlogn,则称作稀疏图,否则称作稠密图。7.2图的基本概念2019/9/48*第7章图名词和基本术语若无向图顶点v和w之间存在一条边(v,w),则称顶点v和w互为邻接点,称边(v,w)依附于顶点v和w或边(v,w)与顶点v和w相关联。与顶点v关联的边的数目定义为v的度(TD)。例如:ABCDEFTD(B)=TD(A)=327.2图的基本概念2019/9/49*第7章图名词和基本术语对于有向图,若顶点v和w之间存在一条弧<v,w>则称顶点v邻接到顶点w,顶点w邻接自顶点v,称弧<v,w>与顶点v和w相关联。以v为尾的弧的数目定义为v的出度(OD)。例如:OD(B)=ID(B)=以v为头的弧的数目定义为v的入度(ID)。出度+入度=该顶点的度(TD)ABCDETD(B)=1237.2图的基本概念2019/9/410