离散数学教案 编号.C1401 课时安排： 3学时 教学课型：理论课 实验课口 习题课口实践课口其它口 题目（教学章、节或主题）： Ch14图 §14.1图 教学目的要求（分掌握、热悉、了解三个层次） 掌握图的定义，包括无向图与有向图、赋权图： 2. 掌握图的顶点、边的关联与相邻关系，顶点的度数的概念： 3.掌握图的项点度数与边数的关系： 4.掌握子图的概念，以及生成子图、导出子图和补图的概念： 5了解的同物的 6. 掌握特殊图及其性质 教学重点、难点： 1)重点：图的定义、图的相关基本概念、特殊图及其性质 2)难点：图的定义、图的相关基本概念 教学方法 利用黑板，CAI课件等教学 教学用具： 黑板，CAI课件及其辅助设备. 教学内容（注明：·重点#难点 ?疑点)： 基本概念(75分钟) 1,定义设A,B为两集合，称{a,b;Ia∈AAb∈B;为A与B的无序积，记作A&B. 将无序对{ab}记作ab). 2.定义一个无向图G是一个二元组,即G=,即D=称为加权图，记为G=,其中W表示各边权的集合。 5.定义设e=(viy)为无向图G=为一无向图或有向图
1401 离 散 数 学 教 案 编号：C1401 课时安排： 3 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch14 图 §14.1 图 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 掌握图的定义，包括无向图与有向图、赋权图； 2. 掌握图的顶点、边的关联与相邻关系，顶点的度数的概念； 3. 掌握图的顶点度数与边数的关系； 4. 掌握子图的概念，以及生成子图、导出子图和补图的概念； 5. 了解图的同构的概念； 6. 掌握特殊图及其性质 教学重点、难点： 1） 重点：图的定义、图的相关基本概念、特殊图及其性质 2） 难点：图的定义、图的相关基本概念 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、基本概念（75 分钟） 1．定义 设 A,B 为两集合,称 {{a,b}｜a∈A∧b∈B}为 A 与 B 的无序积,记作 A＆B． 将无序对{a,b}记作(a,b). 2. 定义 一个无向图 G 是一个二元组,即 G＝,其中, (1) V 是一个非空的集合,称为 G 的顶点集,V 中元素称为顶点； (2) E 是无序积 V＆V 的一个多重子集,称 E 为 G 的边集,E 中元素称为无向边,简称边. 3. 定义 一个有向图 D 是一个二元组,即 D＝,其中, (1)V 同无向图中的顶点集； (2)E 是卡氏积的多重子图,其元素称为有向边,也简称边. 例 14.1 (§14.1) 4. 定义 给每条边赋与权的图 G=称为加权图，记为 G=,其中 W 表示各边权的集合。 5．定义 设 e＝(vi,vj)为无向图 G＝中的一条边,称 vi,vj 为 e 的端点, e 与 vi(或 vj)是彼此关联的. 无边关联的顶点称为孤立点.若一条边所关联的两个顶点重合,则称此边为环. 6．定义 设 G＝为一无向图或有向图
(1)若VE都是有穷集合，则称G是有限图. (2)若IV|=n,则称G为n阶图. (3)若E=⑦，则称G为零图.特别是，若此时又有1V1=1,则称G为平凡图 ()若存在 (2)若ek,cl至少有一个公共端点，则称ekel是彼此相邻的，简称相邻的. 8.定义以上两定义对有向图也是类似的 。 -wi,y,除称viy是e的端点外，还称i是e的始点，y是e的终点 i邻接到j,y邻接于vi 9.定义设G=为一无向图，yEV称y作为边的端点的次数之和为vi的度数，简称度，记作dy 称度数为1的顶点为悬挂顶点，它所对应的边为悬挂边 10.定义设D=,记△ x{dv)lv∈V3,δ(G)=mind(v)lv∈V 分别称为G的最大度和最小度 若D=(VE》是有向图，除了△(D,D)外，还有最大出度、最大入度、最小出度、最小入度，分别定义为 例14.2（§14.1） 12基本定理（握手定理）设图G=为无向图或有向图，V={y1,v,V.E=mm为边数)，则 13推论任何图无向的或有向的)中，度为奇数的项点个数为偶数 14定理设有向图D=,V={v1V,1E=m,则 15定义设V={v1,v.}为图G的顶点集，称(dv,dy:)-,dw.》为G的度数序列 例(1)(3.2,2,3).(42,3,1,4)能成为图的度数序列吗？为什么？ 2)已知图G中有10条边4个3度顶点，其余顶点的度数均小于等于2间G中至少有多少个顶点？ 二、特殊图定义(60分钟) 1,在无向图中，关联一对项点的无向边如果多于1条，称这些边为平行边平行边的条数称为重数在有向 图中，关联一对顶点的有向边如果多于】条，且它们的始点与终点相同，则称这些边为有向平行边，简称 平行边含平行边的图称为多重图既不含平行边，也不含环的图称为简单图 2. 设G=是n阶无向简单图，若G中任何顶点都与其余的n一1个顶点相邻，则称G为n阶无向完全 图，记作Kn.Kn均指无向完全图. 1402
1402 (1)若 V,E 都是有穷集合,则称 G 是有限图. (2)若｜V｜＝n,则称 G 为 n 阶图． (3)若 E＝,则称 G 为零图．特别是,若此时又有｜V｜＝1,则称 G 为平凡图. 7．定义 设无向图 G＝〈V,E〉,vi, vj∈V, ek,el∈E. (1)若存在一条边 e 以 vi, vj 为端点,即 e＝(vi, vj),则称 vi, vj 是彼此相邻的,简称相邻的． (2)若 ek, el 至少有一个公共端点,则称 ek, el 是彼此相邻的,简称相邻的． 8．定义 以上两定义对有向图也是类似的 若 e ＝〈vi, vj〉,除称 vi, vj 是 e 的端点外,还称 vi 是 e 的始点, vj 是 e 的终点, vi 邻接到 vj,vj 邻接于 vi. 9．定义 设 G＝为一无向图,vj∈V,称 vj 作为边的端点的次数之和为 vi 的度数,简称度,记作 d(vj). 称度数为 1 的顶点为悬挂顶点,它所对应的边为悬挂边. 10．定义 设 D＝为一有向图,vj∈V, 称 vj 作为边的始点的次数之和,为 vj 的出度,记作 d+(vj)； 称 vj 作为边的终点的次数之和,为 vj 的入度,记作 d-(vj)；称 vj 作为边的端点的次数之和,为 vj 的度数,简称度,记作 d(vj). 显然 d(vj)＝d + (vj)＋d- (vj). 11．定义 对于图 G＝,记 Δ(G)＝max{d(v)｜v∈V}, (G)＝min{d(v)｜v∈V}, 分别称为 G 的最大度和最小度 若 D＝〈V,E〉是有向图,除了Δ(D),(D)外,还有最大出度、最大入度、最小出度、最小入度,分别定义为 例 14.2 (§14.1) 12 基本定理(握手定理) 设图 G＝为无向图或有向图,V＝{ v 1 ,v 2 ,.,v n },|E|=m(m 为边数),则 13 推论 任何图(无向的或有向的)中,度为奇数的顶点个数为偶数. 14 定理 设有向图 D＝,V＝{ v 1 ,v 2 ,.,v n },｜E｜＝m,则 15 定义 设 V＝{v 1 ,v 2 ,.,v n }为图 G 的顶点集,称(d(v 1 ),d(v 2 ),.,d(v n ))为 G 的度数序列. 例(1) (3,2,2,3),(4,2,3,1,4)能成为图的度数序列吗？为什么？ (2) 已知图 G 中有 10 条边,4 个 3 度顶点,其余顶点的度数均小于等于 2.问 G 中至少有多少个顶点？ 二、特殊图定义（60 分钟） 1． 在无向图中,关联一对顶点的无向边如果多于 1 条,称这些边为平行边.平行边的条数称为重数. 在有向 图中,关联一对顶点的有向边如果多于 1 条,且它们的始点与终点相同,则称这些边为有向平行边,简称 平行边.含平行边的图称为多重图.既不含平行边,也不含环的图称为简单图. 2．设 G=是 n 阶无向简单图,若 G 中任何顶点都与其余的 n－1 个顶点相邻,则称 G 为 n 阶无向完全 图,记作 Kn. Kn 均指无向完全图
设D-为n阶有向简单图，若对于任意的顶点u,v∈Vu≠v,既有有向边,G=是两个图若VV且E'CE,则称G是G的子图，G是G的母图，记做G'∈G 若G'cG且G≠G即VcV或E°cE),则G是G的真子图 4.若GcG且V=V则称V是V的生成子图.设V,V,且V,≠⑦，以V,为顶点集，以两端点均在V,中 的全体边为边集的G的子图，称为V,导出的导出子图. 设E,∈E且E,≠②，以E,为边集，以E,中关联的顶点的全体为顶点集的G的子图称为E,导出的与 出子图 5.设G=是n阶无向简单图.以V为顶点集以所有能使G成为完全图Kn的添加边组成的集合为边 集的图，称为G相对于完全图Kn的补图，简称G的补图，记作G 有向简单图的补图可类似定义 6.设两个无向图G,=,G,=如果存在双射函数0：V,-V,使得对于任意的 e(vi,)∈E,当且仅当e(0(v,0(w》∈E,并且e与c的重数相同，则称G,与G,是同构的， 记作G,≌G。 7.若能将无向图G=的顶点集V划分成两个子集V,和V(V,nV,=,使得G中任何一条边的两 个端点一个属于V,另一个属于V,则称G为二部图（也称为偶图）V,V,称为互补顶点子集，此时可 将G记成G=<V1,V,E,若V,l=nIV,Fm,则记完全二部图G为Knm 1403
1403 设 D=为 n 阶有向简单图,若对于任意的顶点 u,v∈V(u≠v),既有有向边,又有,则称 D 是 n 阶有向完全图. 3．设 G=, G ‘=是两个图.若 V’V,且 E'E,则称 G '是 G 的子图, G 是 G’的母图,记做 G’ G. 若 G’ G 且 G‘≠G(即 V’V 或 E‘ E),则 G’是 G 的真子图. 4．若 G’ G 且 V’=V 则称 V’是 V 的生成子图. 设 V 1 V ,且 V 1 ≠,以 V 1 为顶点集,以两端点均在 V 1 中 的全体边为边集的 G 的子图,称为 V 1 导出的导出子图. 设 E 1 E,且 E 1 ≠ ,以 E 1 为边集,以 E 1 中关联的顶点的全体为顶点集的 G 的子图称为 E 1 导出的导 出子图. 5．设 G=是 n 阶无向简单图.以 V 为顶点集,以所有能使 G 成为完全图 Kn 的添加边组成的集合为边 集的图,称为 G 相对于完全图 Kn 的补图,简称 G 的补图,记作 G . 有向简单图的补图可类似定义. 6．设两个无向图 G 1 =,G 2 =, 如果存在双射函数 ：V 1→V 2 ，使得对于任意的 e=(vi,vj)∈E 1 当且仅当 e’=( (vi), (vj))∈E 2 ,并且 e 与 e’的重数相同,则称 G 1 与 G 2 是同构的, 记作 G 1 ≌G 2 。 7．若能将无向图 G=的顶点集 V 划分成两个子集 V 1 和 V 2 (V 1 ∩V 2 =),使得 G 中任何一条边的两 个端点一个属于 V 1 ,另一个属于 V 2 ,则称 G 为二部图(也称为偶图). V 1 , V 2 称为互补顶点子集,此时可 将 G 记成 G=,若 V 1 =n, V 2 =m,则记完全二部图 G 为 Kn,m
离散数学教案 编号：C1402 课时安排： 】学时教学课型：理论课√实验课口习题课口实践课口其它口 题目（教学章、节或主题）： Chl4图的基本概念 §14.2通路与回路 教学目的要求（分掌握、热悉、了解三个层次）： 1.理解通路、回路基本概念 教学重点、难点： 1)重点：通路、回路基本概念 2)难点：通路、回路基本概念 教学方法 利用黑板，CAI课件等教学 教学用具： 黑板，CAI课件及其辅助设备。 教学内容（注明：·重点#难点？疑点）片 ,通路、回路(40分钟) 1.定义给定图C =设G中顶点和边的交替序列为 若满足如下条件 和是的端点（在G是有向图时，要求是的始点，是的终点），i=1,2,山 则称Γ为项点到的通路。 和分别称为此通路的起点和终点，下中边的数目1称为下的长度 时，此通路称为回路 2.定义 若中的所有边 互不相同，则称Γ为简单通路或一条迹 若回路中的所有边互不相同，称此回路为简单回路或一条闭迹 3.定义若通路的所有顶点 互不相同（从而所有边互不相同），则称此通路为初级通路或一条路 若回路中，除= 外，其余顶点各不相同，所有边也各不相同，则称此回路为初级回路或圈 有边重复出现的通路称为复杂通路，有边重复出现的回路称为复杂回路 由定义可知，初级通路（回路）是简单通路（回路），但反之不真. 4.定理在一个n阶图中，若从顶点i到y(vi≠y)存在通路，则从vi到yj存在长度小于等于n一1的通路 5.推论在 个n阶图中，若从顶点i到(vi≠y)存在通路，则从i到y存在长度小于等于n一1的初级 通路 6.定理在一个n阶图中，如果存在vi到自身的回路，则从vi到自身存在长度小于等于n的回路. 推论在一个n阶图中，如果vi到自身存在一条简单回路，则从vi到自身存在长度小于等于n的初级回路 例14.4（14.2） 例14.5(514.2) 二、课堂小结（约5分钟） 1404
1404 离 散 数 学 教 案 编号：C1402 课时安排： 1 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch14 图的基本概念 §14.2 通路与回路 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解通路、回路基本概念 教学重点、难点： 1） 重点：通路、回路基本概念 2） 难点：通路、回路基本概念 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、通路、回路（40 分钟） 1．定义 给定图 G＝.设 G 中顶点和边的交替序列为Γ＝ 若Γ满足如下条件: 和 是 的端点(在 G 是有向图时,要求 是 的始点, 是 的终点), i＝1,2,.,l, 则称Γ为顶点 到 的通路. 和 分别称为此通路的起点和终点,Γ中边的数目 l 称为Γ的长度. 当 ＝ 时,此通路称为回路. 2. 定义 若Γ中的所有边 互不相同,则称Γ为简单通路或一条迹. 若回路中的所有边互不相同,称此回路为简单回路或一条闭迹. . 3. 定义 若通路的所有顶点 互不相同(从而所有边互不相同),则称此通路为初级通路或一条路 径. 若回路中,除 ＝ 外,其余顶点各不相同,所有边也各不相同,则称此回路为初级回路或圈. 有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路. 由定义可知,初级通路(回路)是简单通路(回路),但反之不真. 4．定理 在一个 n 阶图中,若从顶点 vi 到 vj(vi≠vj)存在通路,则从 vi 到 vj 存在长度小于等于 n－1 的通路. 5．推论 在一个 n 阶图中,若从顶点 vi 到 vj(vi≠vj)存在通路,则从 vi 到 vj 存在长度小于等于 n－1 的初级 通路. 6.定理 在一个 n 阶图中,如果存在 vi 到自身的回路,则从 vi 到自身存在长度小于等于 n 的回路. 推论 在一个n阶图中,如果vi到自身存在一条简单回路,则从vi到自身存在长度小于等于n的初级回路. 例 14.4 (§14.2) 例 14.5 (§14.2) 二、课堂小结（约 5 分钟）
离散数学教案 编号.C1403 课时安排：1学时☐ 教学课型：理论课 实验课口习题课口实践课口其它口 题目（教学章、 节或主题)： Ch14图的基本概急 8143图的连诵性 §144图的矩阵表 8145图的运算 教学目的要求（分掌握、熟悉、了解三个层次）： 1。理解图的连通性概念 2.掌握图的矩阵表示 3.掌握图的运算 教学重点、难点 1)重点：图的连通性概念、图的矩阵 2)难点：图的连通性概念、图的矩阵 教学方法： 利用见板CAI课件等教学 教学用具： 黑板，CAI课件及其辅助设备 教学内容（注明：◆重点#难点？疑点）： *一、图的连通性(45分钟) 1.定义在一个无向图G中若从顶点i到y存在通路（当然从y到vi也存在通路.则称ⅵ与y是连证 的规定v到自身总是连通的 在一个有向图D中，若从顶点vⅵ到y存在通路，则称ⅵ可达y规定vⅵ到自身总是可达的 2.定义设viy为无向图G中的任意两点，若vi与y是连通的，则称vi与yj之间长度最短的通路为vi 与y之间的短程线，短程线的长度称为vi与vj之间的距离，记作dvi,v) 2. 定义设i,y为有向图D中任意两点若可达，则称从到y长度最短的通路为vi到y的短程 线，短程线的长度称为vi到的距离，记作d=∞.d+d>dvi.vk- 在无向图中，还有对称性，即 d(vi.vi)=d(vi.vi). 5.定义若无向图G是平凡图，或G中任意两顶点都是连通的，则称G是连通图：否则，称G是非连通图 6.定义设D是一个有向图，如果略去D中各有向边的方向后所得无向图G是连通图，则称D是连通图 或称D是弱连通图 若D中任意两顶点至少一个可达 一个，则称D是单向连通图 若D中任何一对顶点都是相互可达的则称D是强连通图. 7.定义设无向图G=,若存在顶点子集VCY使G删除V将V中顶点及其关联的边都删除)后， 1405
1405 离 散 数 学 教 案 编号：C1403 课时安排： 1 学时 教学课型：理论课√ 实验课□ 习题课□ 实践课□ 其它□ 题目（教学章、节或主题）： Ch14 图的基本概念 §14.3 图的连通性 §14.4 图的矩阵表示 §14.5 图的运算 教学目的要求（分掌握、熟悉、了解三个层次）： 1. 理解图的连通性概念 2.掌握图的矩阵表示 3.掌握图的运算 教学重点、难点： 1） 重点：图的连通性概念、图的矩阵 2） 难点：图的连通性概念、图的矩阵 教学方法: 利用黑板,CAI 课件等教学. 教学用具: 黑板,CAI 课件及其辅助设备. 教学内容（注明：* 重点 # 难点 ？疑点）： *一、图的连通性（45 分钟） 1．定义 在一个无向图 G 中,若从顶点 vi 到 vj 存在通路(当然从 vj 到 vi 也存在通路),则称 vi 与 vj 是连通 的.规定 vi 到自身总是连通的. 在一个有向图 D 中,若从顶点 vi 到 vj 存在通路,则称 vi 可达 vj.规定 vi 到自身总是可达的. 2．定义 设 vi,vj 为无向图 G 中的任意两点,若 vi 与 vj 是连通的,则称 vi 与 vj 之间长度最短的通路为 vi 与 vj 之间的短程线, 短程线的长度称为 vi 与 vj 之间的距离,记作 d(vi,vj). 2. 定义 设 vi,vj 为有向图 D 中任意两点,若 vi 可达 vj,则称从 vi 到 vj 长度最短的通路为 vi 到 vj 的短程 线, 短程线的长度称为 vi 到 vj 的距离,记作 d. 4．定理若 vi 不可达 vj,规定 d＝∞. d具有下面性质: (1) d ≥0,vi＝vj 时,等号成立. (2)满足三角不等式,即 d+d ≥d. 在无向图中,还有对称性,即 d(vi,vj)＝d(vj,vi). 5．定义 若无向图 G 是平凡图,或 G 中任意两顶点都是连通的,则称 G 是连通图;否则,称 G 是非连通图. 6．定义 设 D 是一个有向图,如果略去 D 中各有向边的方向后所得无向图 G 是连通图,则称 D 是连通图, 或称 D 是弱连通图. 若 D 中任意两顶点至少一个可达另一个,则称 D 是单向连通图. 若 D 中任何一对顶点都是相互可达的,则称 D 是强连通图． 7．定义 设无向图 G＝,若存在顶点子集 V' V,使 G 删除 V'将 V'中顶点及其关联的边都删除)后
所得子图G-V的连通分支数与G的连通分支数满足pG-V>p(G),而刚除V的任何真子集V 后，p(GV=pG,则称V为G的一个点割集 若点割集中只有一个顶点y,则称v为割点 8.定义若存在边集子集E'cE,使G删除E(将E中的边从G中全删除)后，所得子图的连通分支数与G 酒分支数满定pGE>DO商除E的任何真子集E后NG-E)-G)则称 若边割集中只有一条边e,则称e为割边或桥 9.定义点连通度 10.定义边连通度 例14.6(S14.3) 例14.7（14.3) 例14.8(s14.3) 二、图的矩阵(25分钟) 1.定义设无向图G=.V=(v1,vv,旧=m.令a町为vi邻接到j的边的条数 称(a)加×m 为D的邻接矩阵，记作AMD). 邻接矩阵AD)的性 3. 定义14.27 有向图的可达矩阵 三图的云算 (1)定义14.28 (2)定义14.29 四、课堂小结（约5分钟） 1406
1406 所得子图 G－V'的连通分支数与 G 的连通分支数满足 p(G-V')＞p(G),而删除 V'的任何真子集 V'' 后,p(G-V'')＝p(G),则称 V'为 G 的一个点割集. 若点割集中只有一个顶点 v,则称 v 为割点. 8．定义 若存在边集子集 E' E,使 G 删除 E'(将 E'中的边从 G 中全删除)后,所得子图的连通分支数与 G 的连通分支数满足 p(G-E')＞p(G),而删除E'的任何真子集 E''后,p(G-E'')＝p(G),则称 E'是 G 的一 个边割集. 若边割集中只有一条边 e,则称 e 为割边或桥. 9．定义 点连通度 10．定义 边连通度 例 14.6 (§14.3) 例 14.7 (§14.3) 例 14.8 (§14.3) 二、图的矩阵(25 分钟） 1．定义 设无向图 G＝,V＝{ v 1 ,v 2 ,.,v n },E＝{ e 1 ,e 2 ,.,e n },令 mij 为顶点 vi 与边 ej 的关联次数, 则称(mij)n×m 为 G 的关联矩阵,记为 M(G) 关联矩阵 M(G)的性质 2. 定义 设有向图 D＝. V={ v 1 ,v 2 ,.,v n }, |E|＝m. 令 aij 为 vi 邻接到 vj 的边的条数, 称 (aij)n×m 为 D 的邻接矩阵,记作 A(D). 邻接矩阵 A(D)的性质 3. 定义 14.27 有向图的可达矩阵 三. 图的运算 (1.) 定义 14.28 (2.) 定义 14.29 四、课堂小结（约 5 分钟）