第七章 图
第七章 图
7.1图的概念 7.1.1 图的定义 。定义:图G由两个集合V和E组成。 记为G=(V,E) 。有向图和无向图
7.1 图的概念 7.1.1 图的定义 ● 定义:图G由两个集合V和E组成。 记为G = (V , E) ● 有向图和无向图
7.1.2 图的基本术语 ①端点和邻接点:在一个无向图中,若存在一条 边(V,v),则称v1,v为此边的两个端点,并称 它们互为邻接点。 ②顶点的度、入度、出度: 在无向图中顶点的度定义为以该顶点为一 个端点的边的数目,称为顶点的度。 若G是有向图,则v的出度是以v为始点的边 的个数,v的入度是以v为终点的边的个数。 e=>D(v:) i=0
7.1.2 图的基本术语 ① 端点和邻接点:在一个无向图中,若存在一条 边(vi,vj),则称vi,vj为此边的两个端点,并称 它们互为邻接点。 ② 顶点的度、入度、出度 : 在无向图中顶点V的度定义为以该顶点为一 个端点的边的数目,称为顶点的度。 若G是有向图,则v的出度是以v为始点的边 的个数,v的入度是以v为终点的边的个数。 i=0 n-1 e = ½ ∑ D(vi)
③完全图:有向完全图(边数=n*(n-1) 无向完全图(边数=1/2*n*(n-1)) ④子图:G,H是图,如果V(H)≤V(G), E(H)CE(G),则称H是G的子图,G是H的 母图。如果H是G的子图,并且V(H)= V(G),则称H为G的支撑子图
③ 完全图 :有向完全图(边数=n*(n-1)) 无向完全图(边数=1/2*n*(n-1)) ④ 子图 :G,H是图,如果V(H) V(G), E(H) E(G),则称H是G的子图,G是H的 母图。如果H是G的子图,并且V(H) = V(G),则称H为G的支撑子图。
⑤路径和回路 : 设G是图,若存在一个顶点序列vp,V V2,,Vg使得,, ≤Vg1,Vg或(VpV),(y1,V2,,(Vg41,g) 属于E(G),则称v,到v存在一条路径。 路径的长度是该路径上的边的个数。 如果一条路径上除了起点和终点可以相同外, 再不能有相同的顶点,则称此路径为简单路径。 如果一条简单路径的起点和终点相同,且 路径长度大于等于2,则称之为简单回路
⑤ 路径和回路 : 设G是图,若存在一个顶点序列vp,v1, v2,…, vq, 使得,,…, 或 ( vp ,v1 ), ( v1 ,v2 ),…, ( vq-1 ,vq ) 属于E(G),则称vp到vq存在一条路径。 路径的长度是该路径上的边的个数。 如果一条路径上除了起点和终点可以相同外, 再不能有相同的顶点,则称此路径为简单路径。 如果一条简单路径的起点和终点相同,且 路径长度大于等于2,则称之为简单回路
⑥可及和连通分量: 若从顶点v到顶点v有路径,则称v与V可及(连 通的)。 ◆ 若G为无向图,且V(G)中任意两顶点都可及, 则称G为连通图。 无向图G的极大连通子图称为G的连通分量。 ⑦强连通图和强连通分量: 若G为有向图,且对于V(G)中任意两个不同的 顶点v和y,v与y可及,V与v也可及,则称 G为强连通图。 有向图G的极大强连通子图称为G的强连通分量
⑥ 可及和连通分量 : 若从顶点vi到顶点vj有路径,则称vi与vj可及(连 通的)。 若G为无向图,且V(G)中任意两顶点都可及, 则称G为连通图。 无向图G的极大连通子图称为G的连通分量。 ⑦ 强连通图和强连通分量 : 若G为有向图,且对于V(G)中任意两个不同的 顶点vi和vj , vi与vj可及, vj与vi也可及,则称 G为强连通图。 有向图G的极大强连通子图称为G的强连通分量
⑧权和网: ·在一个图中,每条边可以标上具有某种含义的 数值,此数值称为该边的权。 边上带有权的图称做带权图(网)
⑧ 权和网: 在一个图中,每条边可以标上具有某种含义的 数值,此数值称为该边的权。 边上带有权的图称做带权图(网)
7.2图的存储结构 7.2.1邻接矩阵 。定义:表示顶点之间相邻关系的矩阵叫邻接矩阵。 具有n个顶点的图G(W,E)是具有下列性质的n阶 方阵: to Ai,]= 若(,)或是E(G)中的边 若(v,)或不是E(G)中的边
7.2 图的存储结构 7.2.1 邻接矩阵 ● 定义:表示顶点之间相邻关系的矩阵叫邻接矩阵。 具有n个顶点的图G=(V,E)是具有下列性质的n阶 方阵: A[i,j]= 1 若(vi , vj)或是E(G)中的边 0 若(vi , vj)或不是E(G)中的边
·[例1]无向图的邻接矩阵 0123 0 0111 1 1001 2 100 1 3 111
[例1]无向图的邻接矩阵 0 1 2 3 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 1 2 3 V0 V2 V3 V1
[例2]有向图的邻接矩阵 0123.4 001000 1 10001 2 2 01010 3 3 10000 4 00010
[例2]有向图的邻接矩阵 V0 V4 V3 V1 V2 0 1 2 3 4 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 1 2 3 4