第七章 图
第七章 图
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使得<Vp,Y>,<1,V2>, ≤Vg1,Vg或(VpV),（y1,V2,,(Vg41,g) 属于E(G),则称v,到v存在一条路径。 路径的长度是该路径上的边的个数。 如果一条路径上除了起点和终点可以相同外， 再不能有相同的顶点，则称此路径为简单路径。 如果一条简单路径的起点和终点相同，且 路径长度大于等于2，则称之为简单回路
⑤ 路径和回路 ： 设G是图，若存在一个顶点序列vp，v1， v2，…， vq， 使得< vp ,v1 >，< v1 , v2 >，…， < vq-1 , vq >或 ( vp ,v1 )， ( v1 ,v2 )，…， ( vq-1 ,vq ) 属于E(G)，则称vp到vq存在一条路径。 路径的长度是该路径上的边的个数。 如果一条路径上除了起点和终点可以相同外， 再不能有相同的顶点，则称此路径为简单路径。 如果一条简单路径的起点和终点相同，且 路径长度大于等于2，则称之为简单回路