2、>,,,}EACBD第5页7.1图的术语与定义图的定义无向图——无向图G是由两个集合V(G)和E(G)组成的。其中：V(G)是顶点的非空有限集。E(G)是边的有限集合，边是顶点的无序对，记为(v,w)或(w,v)，并且(v,w)=(w,v)。第6页7.1图的术语与定义例如：G2=V2={v0,v1,v2,v3,v4}E2={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3),(v2,v4)}V0V4V3V1V2第7页7.1图的术语与定义图的应用举例例1.交通图（公路、铁路）顶点：地点边：连接地点的路例2.电路
3、图顶点：元件边：连接元件之间的线路例3.通讯线路图顶点：地点边：地点间的连线例4.各种流程图如产品的生产流程图。顶点：工序边：各道工序之间的顺序关系第8页7.1图的术语与定义图的基本术语：无向图的邻接点、关联边以及顶点的度：邻接点：边的两个顶点。关联边：若边e=(v,u),则称顶点v、u关连边e。顶点的度：与顶点相关联的边的数目。eV0V4V3V1V2第9页7.1图的术语与定义有向图的顶点度、入度和出度：顶点V的出度：以顶点V为起点有向边数。顶点V的入度：以顶点V为终点有向边数。顶点V的度：顶点V的出度与其入度的和。结论：如果（无向/有向）图G的顶点数为n，边数为e，则图G的所有
4、顶点的度数之和=2e。（因为每条边对图中所有顶点的度数之和都“贡献”2度）V1V2V3V4第10页7.1图的术语与定义路径、回路：无向图G=（V，E）中的顶点序列v1,v2,…,vk，若(vi,vi+1)E(i=1,2,…k-1)，v=v1,u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。有向图D=（V，E）中的顶点序列v1,v2,…,vk，若E(i=1,2,…k-1)，v=v1，u=vk，则称该序列是从顶点v到顶点u的路径；若v=u，则称该序列为回路。第11页7.1图的术语与定义例如在图G1中，V0,V1,V2,V3是V0到V3的
5、路径；V0,V1,V2,V3,V0是回路。无向图G1有向图G2V0V4V3V1V2V0V1V2V3在图G2中，V0,V2,V3是V0到V3的路径；V0,V2,V3,V0是回路。第12页7.1图的术语与定义子图：设有两个图G=(V，E)，G1=(V1，E1)，若V1V，E1E，E1关联的顶点都在V1中，则称G1是G的子图。例(b)、(c)是(a)的子图(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2第13页7.1图的术语与定义图的连通性：在无（有）向图G=中，若对任何两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）。非连通图
6、连通图强连通图非强连通图V0V1V2V3V0V2V3V1V5V4V0V1V2V3V0V4V3V1V2第14页7.1图的术语与定义连通分量（无向图）：无向图G的极大连通子图称为G的连通分量。极大连通子图含义：该子图是G连通子图，将G的任何不在该子图中的顶点加入，子图不再连通。连通分量非连通图V0V2V3V1V5V4第15页7.1图的术语与定义强连通分量（有向图）有向图D的极大强连通子图称为D的强连通分量。极大强连通子图含义：该子图是D的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。强连通分量V0V2V3V1V0V1V2V3第16页7.1图的术语与定义无向图的生成
7、树：包含无向图G所有顶点的极小连通子图称为G生成树。极小连通子图含义：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通，若T是G的生成树当且仅当T满足如下条件：T是G的连通子图T包含G的所有顶点T中无回路连通图G1G1的生成树V0V4V3V1V2V0V4V3V1V2第17页7.2图的存储结构一、数组表示法（邻接矩阵表示）邻接矩阵：G的邻接矩阵是满足如下条件的n阶矩阵：A[i][j]=1若(vi,vj)E或E0否则0101001010101101000
