1、第 7章 图的基本概念7.1 无向图及有向图7.2 通路、回路、图的连通性7.3 图的矩阵表示7.4 最短路径及关键路径7.1 无向图及有向图一 .基本概念和术语1.无向图与有向图图 :图 G=,其中 V为 (非空 )顶点集合 ,E是 V中顶点偶对的集合 ,称为边 .通常用 V(G)和 E(G)分别表示图 G的顶点集合和边集合 .无向图 :若图 G中边集合 E(G)为无向边的集合 ,则称该图为无向图 .有向图 :若图 G中边集合 E(G)为有向边的集合 ,则称该图为有向图 .有时用 D=表示有向图 .2.有限图与 n阶图若 G=中 V,E都是有穷集合 ,则称 G为有限图 .若 |V|=n,则称
2、 G为 n阶图 .例如 :图 7.1中 (1)为无向图 G=,V=v1,v2,v3,v4,v5, E=(v1,v2),(v2,v2),(v2,v3),(v1,v3),(v1,v3)(v1,v4);(2)为有向图 D=,V=v1,v2,v3,v4,v5,E=,3.零图与平凡图若 G=中 ,E=, 则称 G为零图 .若 |V|=1,则称 G为平凡图 . 4.关联与相邻设图 G=, u,v V, (u,v) E(有向图 E)常记 e=(u,v)(或有向图 e=),称 u,v为 e的端点 .(对有向图中的有向边来说 ,称 u为 e的始点 ,v为 e的终点 )称 e与 u或 v是彼此相关联的 ;无边关联
3、的顶点称为孤立点 .若 e关联的两个顶点重合 ,则称 e为环 ;若 uv, 则称 e与 u(或 v)的关联次数为 1;若 u=v(即 e为环 ),则称 e与 u关联的次数为 2;若顶点 u,v之间有边关联 ,则称 u与 v相邻 ;若两条边至少有一个公共端点 ,则称这两条边相邻 .5.顶点的度数设 v为无向图 G中的一个顶点 ,称 v作为边的端点的次数之和为 v的度数或度 ,记作 d(v).若 v为有向图 G中的一个顶点 ,称 v作为边的始点次数之和为 v的出度 ,记作 d+(v);v作为边的终点的次数之和为 v的入度 ,记作 d-(v),称 d+(v)+d-(v)为 v的度数或度 ,记作 d(
4、v).G的最大度 :(G)=maxd(v)|v V(G)G的最小度 :(G)=mind(v)|v V(G)6.简单图对于无向图 ,若关联一对顶点的边多于 1条 ,则称这些边为平行边 .对于有向图 ,关联一对顶点的方向相同的边 ,如果多于 1条 ,则称这些边为平行边 .既不含平行边 ,也不含环的图 ,称为简单图 .7.完全图设 G为 n阶 (n个顶点 )无向简单图 ,若 G中任何两个顶点均相邻 ,则称 G为 n阶 (无向 )完全图 ,记作 Kn.边数 n(n-1)/2设 D为 n阶 (n个顶点 )有向简单图 ,若 G中任何两个顶点之间均有两条方向相反的边 ,则称 G为 n阶有向完全图 .边数 n(n-1)8.子图设 G=,G=,若 V V, E E,则称 G为 G的子图 .记作 G G.若 G G且 GG, 则称 G 为 G的真子图 .若 G G且 V=V,则称 G 为 G的生成子图 .若 V1 V且 V1, 称以 V1为顶点集 ,以两个端点均在 V1中的边为边集的图为 V1的导出子图 .若 E1 E且 E1, 称以 E1为边集 ,以 E1中边关联的顶点为顶点集的图为 E1的导出子图 .注 )每个图都是本身的子图 .9.补图 :设 G=为 n阶简单图 ,称以 V为顶点集 ,以使 G成为n阶完全图所添加的边为边集的图为 G的补图 ,记作
