第7章图 ④⑤ 7.「图的定义和术语 1、图、顶点、边 GI 图G是由集合VG和E(G)组成记为G=(vE),其中V(G是顶 点的非空有限集合,E(G)是边的有限集合,边是点的无序对 或有序对。 2、有向图、弧、无向图 ●若图中的边是顶点的有序对,则称此图为有向图。 有向边又称为弧,通常用尖括号表示一条有向边,<vw表 示从顶点v到w顶点的一条弧,v称为边的始点(或弧尾),w 称为边的终点(或弧头)。 北京邮电大学自动化学院
北京邮电大学自动化学院 1 第7章 图 ⚫ 7.1 图的定义和术语 ⚫ 1、图、顶点、边 ⚫ 图G是由集合V(G)和E(G)组成,记为G=(V,E)，其中V(G)是顶 点的非空有限集合，E(G)是边的有限集合，边是点的无序对 或有序对。 ⚫ 2、有向图、弧、无向图 2 4 5 1 3 6 G1 ⚫ 若图中的边是顶点的有序对，则称此图为有向图。 ⚫ 有向边又称为弧，通常用尖括号表示一条有向边，<v,w>表 示从顶点v到w顶点的一条弧，v称为边的始点（或弧尾），w 称为边的终点（或弧头）
7.1图的定义和术语 ·图G中:V(G1)={1,23,4,,6} E(G1)={≤1,2>,21>,<2,3>,<24>,≤3,5>,<5,6>,<6,3>} 例 例 6③2④⑥ GI G2 无向图若图中的边是顶点的无序对,则称此图为无向图。通 常用园括号表示无向边。(V,w)或(Wv),并且(vwy)=(w,v) ·图G2中:V(G2)={1,234,5,67 E(G1)={(1,2),(1,3)(2,3),(2,4)2(25),5,6),(5,7) 北京邮电大学自动化学院
北京邮电大学自动化学院 2 例 2 4 5 1 3 6 G1 ⚫ 图G1中： V(G1)={1,2,3,4,5,6} ⚫ E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>} 例 1 5 7 3 2 4 G2 6 ⚫ 图G2中： V(G2)={1,2,3,4,5,6,7} ⚫ 无向图 若图中的边是顶点的无序对，则称此图为无向图。通 常用园括号表示无向边。（v,w）或（w,v)，并且（v,w)=(w,v) 7.1 图的定义和术语 ⚫ E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
7.1图的定义和术语 ●3、有向完全图、无向完全图 有向完全图:具有n(n-1)条弧的有向图称为有向完全图 ●无向完全图:n个顶点的无向图最大边数是n(n-1)2,具有 n(n-1)2条边的无向图称为无向完全图。 有向完全图 无向完全图 4、相邻顶点、相关联弧或边 若<V1,V2>≤E或(V1v2)E,则V1,V2是相邻顶点,弧 <V1V2>或边(v1V2)是与顶点V和v2相关联弧或边。 北京邮电大学自动化学院
北京邮电大学自动化学院 3 ⚫ 3、有向完全图、无向完全图 ⚫ 4、相邻顶点、相关联弧或边 ⚫ 无向完全图：n个顶点的无向图最大边数是n(n-1)/2，具有 n(n-1)/2条边的无向图称为无向完全图。 2 1 3 有向完全图 2 1 3 无向完全图 7.1 图的定义和术语 ⚫ 若<V1 ,V2> E或(V1 ,V2 ) E ，则V1，V2是相邻顶点，弧 <V1 ,V2>或边(V1 ,V2 )是与顶点V1和V2相关联弧或边。 ⚫ 有向完全图：具有n(n-1)条弧的有向图称为有向完全图
7.1图的定义和术语 ●5、度 个顶点V的度是与该顶点相关联的边的数目,记为TD(v)。 ●对于有向图,则把以顶点v为弧尾的数目称为点V的出度, 记为OD(V),把以顶点V为头的弧的数目称为顶点V的入 度,记为ID(v)。顶点V的度为 ●TD(v)=|D(V)+OD(V) 例1 例2 G1 G2 顶点2入度:1出度:3 顶点5的度:3 顶点4入度:1出度:0 顶点2的度:4 北京邮电大学自动化学院 4
北京邮电大学自动化学院 4 ⚫ 5、度 例1 2 4 5 1 3 6 G1 ⚫ 顶点2入度：1 出度：3 ⚫ 顶点4入度：1 出度：0 例2 1 5 7 3 2 4 G2 6 ⚫ 顶点5的度：3 ⚫ 顶点2的度：4 7.1 图的定义和术语 ⚫ 一个顶点V的度是与该顶点相关联的边的数目，记为TD（V）。 ⚫ 对于有向图，则把以顶点V为弧尾的数目称为点V的出度， 记为OD（V），把以顶点V为头的弧的数目称为顶点V的入 度，记为ID（V）。 顶点V的度为： ⚫ TD（V）=ID（V）+OD（V）
7.1图的定义和术语 6、子图 设有两个图G=(vE和G=(v,E)。若VsV且 EgE,则称图G是图G的子图。 (a)G1 子图 子图 子图 b)63子图子图子图 北京邮电大学自动化学院
北京邮电大学自动化学院 5 ⚫ 6、子图 ⚫ 设有两个图 G＝(V, E) 和 G‘＝(V’, E‘)。若 V’ V 且 E‘E, 则称 图G’ 是 图G 的子图。 7.1 图的定义和术语