第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无向图个无向图是一个二元组，即：G=，其中：（1）V是G的顶点集，V（G)（2）E是G的边集，也称无向边，E（G）。无向图示例：G=, 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 无向图 一个无向图是一个二元组，即：G= ，其中： （1）V 是 G 的顶点集，V（G）； （2）E 是 G 的边集，也称无向边， E（G）。 无向图示例： G= ，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有向图一个有向图是一个二元组，即：D=，其中：（1）V是D的顶点集，V（D）（2）E是D的边集，也称无向边，E（D）有向图示例：D=, 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=的一条边，称vi、vj为ek的端点，ek与vi（或vj）是彼此关联的。e1V1V2e2e6ee30esV4V30V5
3、定义 5.2 有向图 一个有向图是一个二元组，即：D= ，其中： （1）V 是 D 的顶点集，V（D） （2）E 是 D 的边集，也称无向边， E（D） 有向图示例： D= ，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= 的一条边，称 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=，viEV，以vi为端点的边的数量为度数，简称度，记作d(vi）。问：下图中，vl的度数d(vl）？设有向图D=，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= ，vi∈V，以 vi 为端点的边的数量为度数，简称度，记 作 d(vi)。 问：下图中，v1 的度数 d(v1) ？ 设有向图 D= ，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=，[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= ，|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=是n阶无向简单图，若G中任何顶点都与其余的n-1个顶点相邻，称为n阶无向完全图。0设D=是n阶有向简单图，对任意顶点u、V，既有有向边，又有，称D为n阶有向完全图。O10、定义5.8子图、母图、生成子图、导出子图设G=，G’=是两个图。若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= 是 n 阶无向简单图，若 G 中任何顶点都与其余的 n-1 个顶点相 邻，称为 n 阶无向完全图。 设 D= 是 n 阶有向简单图，对任意顶点 u、v，既有有向边，又 有,称 D 为 n 阶有向完全图。 10、定义 5.8 子图、母图、生成子图、导出子图 设 G=，G’=是两个图。若 V’∈V，且 E’∈E，则称 G’ 是 G 的子图，G 是 G’的母图，记作 G’ G
生成子图：若G'二G且G'≠G，称G”是G的真子图。若G'G且v'=V，称G'是G的生成子图。1导出子图：（1）顶点的导出子图设V1≤V，且V1≠Φ，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图。V1e1e3V3V2e20v1v2v3的导出子图（2）边的导出子图设E1E，且E1≠Φ，以E1为边集，以E1中边关联的顶点的全体为顶点的G的子图，称为E1导出的导出子图。V10e1V2e2
生成子图： 若 G’ G 且 G’≠ G，称 G’是 G 的真子图。 若 G’ G 且 v’= v，称 G’是 G 的生成子图。 导出子图： （1）顶点的导出子图 设 V1 V，且 V1 ≠ ф，以两端点均在 V1 中的全体边为边集的 G 的子图， 称为 V1 导出的导出子图。 （2）边的导出子图 设 E1 E，且 E1 ≠ ф，以 E1 为边集，以 E1 中边关联的顶点的全体为顶 点的 G 的子图，称为 E1 导出的导出子图。 v1 v2 v3的导出子图 v1 e1 e2 e3 v2 v3 e1 e2 v1 v2
11、定义5.8补图设G=是n阶无向简单图，以V为顶点集，以所有能使G称为完全图的添加边组合的集合为边集的图，称为G相对于完全图Kn的补图，记作G..S5.2通路、回路、图的连通性1、定义5.11通路、回路图G=，设顶点和边的交替序列为L=vOelvle2vlel，若vi-1和vi是ei的端点（有向图时，vi-l是ei的始点，vi是ei的终点），则称L为顶点vo到vl的通路。vO是始点，vl是终点。L中边的数目为长度。VoV1V2V30000长度为3vO到v3都存在通路，VoV1V2V3o-0+00+V3到vO存在通路吗？在通路中，当vO=vl时，称为回路。Vo=V5QI
11、定义 5.8 补图 设 G=是 n 阶无向简单图，以 V 为顶点集，以所有能使 G 称为 完全图的添加边组合的集合为边集的图，称为 G 相对于完全图 Kn 的补图，记作 G。 §5.2 通路、回路、图的连通性 1、定义 5.11 通路、回路 图 G=，设顶点和边的交替序列为 L=v0e1v1e2.vlel，若 vi-1 和 vi 是 ei 的端点（有向图时， vi-1 是 ei 的始点，vi 是 ei 的终点），则称 L 为顶点 v0 到 vl 的通路。v0 是始点，vl 是终点。L 中边的数目为长度。 v0 到 v3 都存在通路，长度为 3 V3 到 v0 存在通路吗？ 在通路中，当 v0=vl 时，称为回路。 v0 v1 v2 v3 v0 v1 v2 v3 v0= v5 v1 v4
>简单通路：V简单回路：ele2el各不相同。>初级通路：初级回路：vOvlvl各不相同（初级回路vO=vl）。》复杂通路：>复杂回路：有边重复出现。2、定理5.3在一个n阶图中，若从顶点vi到vj（vi≠vj）存在通路，则从vi到vj存在长度小于等于n-1的通路。推论：在一个n阶图中，若从顶点vi到vi（vivi）存在通路，则从vi到vj存在长度小于等于n-1的初级通路。3、定理5.4在一个n阶图中，若存在vi到自身的回路，则从vi到自身存在长度小于等于n的回路。推论：在一个n阶图中，若vi到自身存在简单回路，则从vi到自身存在长度小于等于n的初级回路。4、定义5.12连通（1）在无向图G中，若从顶点vi到vj存在通路，则称vi与vj是连通的。（vi到自身是连通的）。（2）在有向图D中，若从顶点vi到vj存在通路，则称vi可达vj（vi到自身是可达的）。5、定义5.13连通图、非连通图若无向图G是平凡图，或G中任意两点都是连通的，则称G是连通图：否
➢ 简单通路： ➢ 简单回路：e1e2.el 各不相同。 ➢ 初级通路： ➢ 初级回路：v0v1.vl 各不相同（初级回路 v0= vl）。 ➢ 复杂通路： ➢ 复杂回路：有边重复出现。 2、定理 5.3 在一个 n 阶图中，若从顶点 vi 到 vj（vi ≠ vj）存在通路，则从 vi 到 vj 存在长度小于等于 n-1 的通路。 推论：在一个 n 阶图中，若从顶点 vi 到 vj（vi ≠ vj）存在通路，则从 vi 到 vj 存在长度小于等于 n-1 的初级通路。 3、定理 5.4 在一个 n 阶图中，若存在 vi 到自身的回路，则从 vi 到自身存在长度小于等 于 n 的回路。 推论：在一个 n 阶图中，若 vi 到自身存在简单回路，则从 vi 到自身存在长 度小于等于 n 的初级回路。 4、定义 5.12 连通 （1）在无向图 G 中，若从顶点 vi 到 vj 存在通路，则称 vi 与 vj 是连通的。 （vi 到自身是连通的）。 （2）在有向图 D 中，若从顶点 vi 到 vj 存在通路，则称 vi 可达 vj （vi 到 自身是可达的）。 5、定义 5.13 连通图、非连通图 若无向图 G 是平凡图，或 G 中任意两点都是连通的，则称 G 是连通图；否
则，G是非连通图。6、定义5.14（1）弱连通图：设D是有向图，如果略去各有向边的方向后所得的无向图G是连通的，则称D是连通图（或弱连通图）。（2）单向连通图：若D中任意两顶点至少一个可达另一个。（3）强连通图：若D中任意两顶点都相互可达。$5.3图的矩阵表示1.无向图的关联矩阵设无向图G=，V={vl,v2,."，vn)，E=(el，e2，,en)，令mij为顶点vi与边ei的关联次数，则称（mii)nxm为G的关联矩阵。记作M(G）0vi与e,不关联。mj的取值为：1Vi与e关联次数为l。2Vi与e关联次数为2。esV1e1V3e3e2e40V4V2关联矩阵性质：
则，G 是非连通图。 6、定义 5.14 （1）弱连通图：设 D 是有向图，如果略去各有向边的方向后所得的无向图 G 是连通的，则称 D 是连通图（或弱连通图）。 （2）单向连通图：若 D 中任意两顶点至少一个可达另一个。 （3）强连通图：若 D 中任意两顶点都相互可达。 §5.3 图的矩阵表示 1.无向图的关联矩阵 设无向图 G=，V={v1，v2，.，vn}，E ={e1，e2，.，en}，令 mij 为顶点 vi 与边 ej 的关联次数，则称(mij)nxm 为 G 的关联矩阵。记作 M(G) 关联矩阵性质： mij的取值为： 0 vi与ej不关联。 1 vi与ej关联次数为1。 2 vi与ej关联次数为2。 e3 v3 v2 v1 v4 e1 e2 e4 e5
（1）每一列恰好有两个1或一个2（2）第i行元素之和为vi的度数。（3）所有元素之和等于2m。（4）第i行之和等于0，vi是孤立点。（5）第j列与第k列相同，ej与ek为平行边。2.有向图的关联矩阵设有向图D=，V=(vl，v2,.,vn),E=(el,e2,...,en),令:[1-1 0 0 0e241V4O-1 0 1 -1 1M (D)ei0000-1e.001-110V2esV3关联矩阵的性质：（1）每一列恰好有一个1和一个-1。(2）第i行1的个数等于d(vi)，-1的个数等于d（vi)。（3）M（D）中1与-1的个数相等，为m。3.有向图的邻接矩阵设有向图D=，V={vl，v2，，vn)，lE|=m，令a(1)ij为vi邻接到vj的边的条数，则称（a(1)ii)nxm为D的邻接矩阵。记作A(D)。1210V4-0010A (D) =00010010V3V2邻接矩阵的性质：（1）第i行元素之和等于d+（vi)。（2）第j行元素之和等于d-(vi)。（3）所有元素之和等于边数m。4.有向图的可达矩阵设D=, V=[vl, v2, ."",vn),令:
（1）每一列恰好有两个 1 或一个 2 （2）第 i 行元素之和为 vi 的度数。 （3）所有元素之和等于 2m。 （4）第 i 行之和等于 0，vi 是孤立点。 （5）第 j 列与第 k 列相同， ej 与 ek 为平行边。 2.有向图的关联矩阵 设有向图 D=，V={v1，v2，.，vn}，E ={e1，e2，.，en}，令： 关联矩阵的性质： （1）每一列恰好有一个 1 和一个-1。 （2）第 i 行 1 的个数等于 d + (vi)， -1 的个数等于 d - (vi)。 （3）M（D）中 1 与-1 的个数相等，为 m。 3.有向图的邻接矩阵 设有向图 D=，V={v1，v2，.，vn}，|E| =m，令 a(1)ij 为 vi 邻接到 vj 的边的条数，则称(a(1)ij)nxm 为 D 的邻接矩阵。记作 A(D)。 邻接矩阵的性质： （1）第 i 行元素之和等于 d+(vi)。 （2）第 j 行元素之和等于 d-(vi)。 （3）所有元素之和等于边数 m。 4.有向图的可达矩阵 设 D=，V={v1，v2，.，vn}，令：