第5章图的基本概念V$5.1无向图及有向图Y$5.2通路、回路、图的连通性Y$5.3图的矩阵表示V$5.4最短路径及关键路径V$5.5例题分析85.1无向图及有向图1、无序集设A、B为两个集合，称(a,b)laEA^bEB)为A与B的无序集，记作A&B例如，A=(al,a2)，B=(b1,b2)，则：A&B={(al,b1)，(al,b2)，(a2,bl)，(a2,b2))。A&A=[(al,al)，(al,a2)，(a2,a2))。2、定义5.1无向图个无向图是一个二元组<V，E>，即：G=<V，E>，其中：（1）V是G的顶点集，V（G)（2）E是G的边集，也称无向边，E（G）。无向图示例：G=<V, E>, V=(vl, v2, v3, v4, v5), E=[(vl, v2), (v2, v2), (v2, v3),(vl,v3),(vl,v3),(vl,v4))。如图7-1(a)所示：e1V1V2e2.e6e4e3esV4V30Vs7-1(a）无向图的表示
第 5 章 图的基本概念 ✓ §5.1 无向图及有向图 ✓ §5.2 通路、回路、图的连通性 ✓ §5.3 图的矩阵表示 ✓ §5.4 最短路径及关键路径 ✓ §5.5 例题分析 §5.1 无向图及有向图 1、无序集 设 A、B 为两个集合，称{{a,b}|a∈A∧b∈B}为 A 与 B 的无序集，记作 A&B。 例如，A={a1,a2}，B={b1,b2}，则： A&B={(a1，b1)，(a1，b2)，(a2，b1)，(a2，b2)}。 A&A={(a1，a1)，(a1，a2)，(a2，a2)} 。 2、定义 5.1 无向图 一个无向图是一个二元组<V，E>，即：G= <V，E>，其中： （1）V 是 G 的顶点集，V（G）； （2）E 是 G 的边集，也称无向边， E（G）。 无向图示例： G= <V，E>，V={v1，v2，v3，v4，v5}，E={(v1，v2)，(v2，v2)，(v2，v3)， (v1，v3)，(v1，v3)，(v1，v4)}。 如图 7-1(a)所示： 7-1(a) 无向图的表示 v2 v1 v4 v3 v5 e1 e2 e3 e4 e5 e6
3、定义5.2有向图一个有向图是一个二元组<V，E>，即：D=<V，E>，其中：（1）V是D的顶点集，V（D）（2）E是D的边集，也称无向边，E（D）有向图示例：D=<V, E>, V=(vl, v2, v3, v4, v5), E={(vl, v1), (v3, v2), (v3, v2),(v3,v4),(v2,v4),(v4,v5),(v5,v4),(vl,v2))。如图7-1(b)所示：e1V1e2VsV2.esese4e38O拉e6V4V3图7-1(b）有向图的表示几个相关概念：（1）有限图：V和E都是有穷集合的图。（2）n阶图：顶点个数是n的图。（3）零图：E=Φ（没有边）的图。（4）平凡图：只有1个顶点的图。4、定义5.3彼此关联（边和顶点）设ek=（vi，vj）为无向图G=<V，E>的一条边，称vi、vj为ek的端点，ek与vi（或vj）是彼此关联的。e1V1V2e2e6ee30esV4V30V5
3、定义 5.2 有向图 一个有向图是一个二元组<V，E>，即：D= <V，E>，其中： （1）V 是 D 的顶点集，V（D） （2）E 是 D 的边集，也称无向边， E（D） 有向图示例： D= <V，E>，V={v1，v2，v3，v4，v5}，E={(v1，v1)，(v3，v2)，(v3，v2)， (v3，v4)，(v2，v4)，(v4，v5)，(v5，v4)，(v1，v2)}。 如图 7-1(b)所示： 图 7-1(b) 有向图的表示 几个相关概念： （1）有限图：V 和 E 都是有穷集合的图。 （2）n 阶图：顶点个数是 n 的图。 （3）零图：E= ф（没有边）的图。 （4）平凡图：只有 1 个顶点的图。 4、定义 5.3 彼此关联（边和顶点） 设 ek=（vi，vj）为无向图 G= <V，E>的一条边，称 vi、vj 为 ek 的 端点， ek 与 vi（或 vj）是彼此关联的。 v2 v1 v5 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8 v2 v1 v4 v3 v5 e1 e2 e3 e4 e5 e6
问：上图中，边e2与谁关联？v1，v2。（1）孤立点：无边关联的顶点。（2）环：一条边关联两个顶点重合。（3）关联次数：vi，vj重合时，为2；不重合时，为l；vi不是ek的端点时，为0。5、定义5.4彼此相邻（1）顶点彼此相邻在无向图中，vi，vj是边ek的两个顶点，则vi，vj是彼此相邻的。eiV1V2e2e6e4e3oesV4V30V5问：v4与谁相邻？v5呢？v4与v1相邻，v5不与任何点相邻。（2）边彼此相邻在无向图中，ek，el有公共点，则ek，el是彼此相邻的。问：在上图中，边e6与谁相邻？e4呢？e6与e2，e4，e5相邻。e4与e2，e3，e5，e6相邻。6、定义5.5度数设无向图G=<V，E>，viEV，以vi为端点的边的数量为度数，简称度，记作d(vi）。问：下图中，vl的度数d(vl）？设有向图D=<V，E>，vjEV，称v为边的始点的次数之和，称为vj的出度，记作d(vj)。称vj为边的终点的次数之和，称为vj的入度，记作d(vj）
问：上图中，边 e2 与谁关联？v1，v2。 （1）孤立点：无边关联的顶点。 （2）环：一条边关联两个顶点重合。 （3）关联次数： vi，vj 重合时，为 2；不重合时，为 1； vi 不是 ek 的端 点时，为 0。 5、定义 5.4 彼此相邻 （1） 顶点彼此相邻 在无向图中， vi，vj 是边 ek 的两个顶点，则 vi，vj 是彼此相邻的。 问：v4 与谁相邻？ v5 呢？v4 与 v1 相邻，v5 不与任何点相邻。 （2）边彼此相邻 在无向图中， ek，el 有公共点，则 ek，el 是彼此相邻的。 问：在上图中，边 e6 与谁相邻？e4 呢？e6 与 e2，e4，e5 相邻。e4 与 e2， e3，e5，e6 相邻。 6、定义 5.5 度数 设无向图 G= <V，E>，vi∈V，以 vi 为端点的边的数量为度数，简称度，记 作 d(vi)。 问：下图中，v1 的度数 d(v1) ？ 设有向图 D= <V，E>，vj∈V，称 vj 为边的始点的次数之和，称为 vj 的出 度，记作 d + (vj)。称 vj 为边的终点的次数之和，称为 vj 的入度，记作 d - (vj)。 v2 v1 v4 v3 v5 e1 e2 e3 e4 e5 e6
d(vj)= d'(vj) + d'(vj)。v2的出度：d（v2）=1v2的入度：d(v2）=3v2的度数：d(v2)=d(v2)+d(v2)=4e1V1Oe2VsV2Qesesere3e4QOe6V4V3（1）无向图最大度数：△(G)=max(d(v)IvEV)。最小度数：(G)=min(d(v)/EV)。（2）有向图最大出度：△*(D)=maxd(v)/EV)。最大入度：△(D)=max(d(v)/vEV)。最小出度：$*(D)=min(d(v)IvEV)。最小入度：$-(D)=min(d(v)/vEV)。7、定理5.1握手定理设G=<V，E>，[E|=m，则：推论：任何图中，度为奇数的顶点个数为偶数。例题7.1：d(vl)、d(v2)、…、d(vn)为度数序列
d(vj)= d+ (vj) + d- (vj)。 v2 的出度：d + (v2) =1 v2 的入度：d - (v2) =3 v2 的度数：d(v2)=d+ (v2)+d- (v2) =4 （1）无向图 最大度数：△(G) = max{ d(v) | v ∈V }。 最小度数：∮(G) = min{ d(v) | v ∈V }。 （2）有向图 最大出度：△+ (D) = max{ d+ (v) | v ∈V }。 最大入度：△- (D) = max{ d- (v) | v ∈V }。 最小出度：∮+ (D) = min{ d+ (v) | v ∈V }。 最小入度：∮- (D) = min{ d- (v) | v ∈V }。 7、定理 5.1 握手定理 设 G= <V，E>，|E|=m，则： 推论：任何图中，度为奇数的顶点个数为偶数。 例题 7.1 ： d(v1)、 d(v2)、 . 、d(vn)为度数序列 。 v2 v1 v5 v3 v4 e1 e2 e3 e4 e5 e6 e7 e8
（1）（3、3、2、3）和（5、2、3、1、4）能成为图的度数序列吗？（2）图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，问G中至少有多少个顶点？8、定义5.6平行边、重数（1）在无向图中，关联一对顶点的无向边多与1，称为平行边。平行边的条数为重数。（2）在有向图中，关联一对顶点的有向边多与1，且始点和终点相同，称为有向平行边多重图：含平行边的图。简单图：即不含平行边，也不含环的图。9、定义5.7无向完全图、有向完全图设G=<V，E>是n阶无向简单图，若G中任何顶点都与其余的n-1个顶点相邻，称为n阶无向完全图。0设D=<V，E>是n阶有向简单图，对任意顶点u、V，既有有向边<u,v>，又有<v，u>，称D为n阶有向完全图。O10、定义5.8子图、母图、生成子图、导出子图设G=<V，E>，G’=<V’，E'>是两个图。若V’EV，且E’EE，则称G"是G的子图，G是G”的母图，记作G'二G
（1）（3、3、2、3）和（5、2、3、1、4）能成为图的度数序列吗？ （2）图 G 中有 10 条边，4 个 3 度顶点，其余顶点的度数均小于等于 2，问 G 中至少有多少个顶点？ 8、定义 5.6 平行边、重数 （1）在无向图中，关联一对顶点的无向边多与 1，称为平行边。平行边的条 数为重数。 （2）在有向图中，关联一对顶点的有向边多与 1，且始点和终点相同，称为 有向平行边 多重图：含平行边的图。 简单图：即不含平行边，也不含环的图。 9、定义 5.7 无向完全图、有向完全图 设 G= <V，E>是 n 阶无向简单图，若 G 中任何顶点都与其余的 n-1 个顶点相 邻，称为 n 阶无向完全图。 设 D= <V，E>是 n 阶有向简单图，对任意顶点 u、v，既有有向边<u,v>，又 有<v,u>,称 D 为 n 阶有向完全图。 10、定义 5.8 子图、母图、生成子图、导出子图 设 G=<V，E>，G’=<V’，E’>是两个图。若 V’∈V，且 E’∈E，则称 G’ 是 G 的子图，G 是 G’的母图，记作 G’ G