资源简介

《计算机数学》课程教案
教案编写人：
课程名称 计算机数学 本次内容 图的基本概念
授课班级 时 间 第 周 第 次 教学课时 /单元课时 /项目课时
学习目标 知识目标： 1.图的概念 2.握手定理 3.图的连通性 能力目标： 1.能够根据已知条件画图 2.能够应用握手定理 3.能够使用图的知识解决简单的问题 素质目标： 动手动脑能力的培养 观察理解力的培养
教学 重难点 1.握手定理 2.图的连通性 3.图的简单应用
课后总结 建议学时2课时
一、图的基本概念
定义6.1.1 图是由非空点的集合以及连接某些点的边的集合所组成的图形，记为图.图中的点称为顶点，或简称点，在图中通常用一圆点表示.连接点与点之间的线段或曲线段称为边，也可称为弧.每条边可用一个结点对表示，即.具有个点，条边的图称为图.
什么是环？什么是平行边？（请同学在教材中勾画）
定义6.1.2 若结点是边的一个端点，则称结点与边相关联.若结点与结点之间有一条共同的边，则称结点与结点是邻接点.若边与边有一个共同的结点，则称边与边是邻接边.
定义6.1.3 给定图，如果图的所有边都是没有方向的，则称图是无向图，并称其边为无向边.如果图的所有边都是有方向的，则称图是有向图，并称其边为有向边.如果图既有有向边又有无向边，则称图是混合图.
无向完全图：任意两点之间都有边连接的无向图.一般地，有个点的完全图用表示，容易证明，无向完全图具有条边.
有向完全图：任意两点之间都有两条相反边连接的有向图.
带权图：在图中边的旁边附加一些表示该边某些特征的数字，这些数字就叫做该边的权，此边就称为带权边.具有带权边的图就称为带权图.
二、图的度数
定义6.1.3 若图为无向图，点是无向图中的结点，所有点相关联的边数称为结点的度数，记为.若图为有向图，以点为起点的边数称为结点的出度，记为以点为终点的边数称为结点的入度，记为.
度数为零的点称为孤立点.
注意：若一个顶点的关连边中有环，在计算该点的度数时环要计两条边.
定理6.1.1（握手定理） 若图是一个的无向图，结点集合为，则
.
对于有向图，每条边都为与之相关联的结点提供一个出度和一个入度，所以有.
三、通路与图的连通性
定义6.1.4 在无向图中，，，将顶点和边的交替序列称为长度为的连接点到的通路，其中，且关联于结点.并称点为该通路的起点，点为该通路的终点.当起点和终点相同时，即，则称该通路为回路.
请同学回答简单通（回）路和基本通（回）路的不同点.
定义6.1.5 在图中，如果从结点到结点至少存在一条通路，则称结点到结点是可达的，并将从结点到结点的所有通路中长度最短的一条称为结点到结点的距离，记为.
定理6.1.2 在一个图中，任何基本通路的长度均不大于，任何基本回路的长度均不大于.
定义6.1.6 在无向图中，若其每对顶点之间至少有一条通路，则称图是连通图，否则称图是非连通图.
定义6.1.7 在有向图中，若其每对顶点彼此之间至少存在一条通路，则称图是强连通图；若其每对顶点彼此之间至少存在一个方向的通路，则称图是单向连通图.
由定义可以得到一个结论：强连通图必是单向连通的，但是单向连通图未必是强连通的.
图6.1.1 图6.1.2
例6.1.1 指出图6.1.1和图6.1.2中有向图的连通性，并说明原因.
解 图6.1.1是强连通图，因为该图中的任意一对顶点彼此之间都至少有一条通路，比如可以到，也可以到；可以到，也可以到，图6.1.2就是单向连通图，因为该图中的任意一对顶点彼此之间只存在一个方向的通路，比如可以到，却不能到，也可以到，却不能到.
例6.1.2 见书上例题
四、应用拓展
例6.1.3 某仓库要存7种化学药品，分别用表示，因为某些化学药品相互之间会产生化学反应，因此不能将它们一起堆放，其中要发生反应的化学药品有、、、、、、、、、、、，那么该如何对仓库进行分区，使各区之间互相隔离并且最节约空间？
解 先把各种化学药品作为结点，则其集合为，然后把相互之间会发生化学反应的化学药品用边连接起来，就构成一个图，如图6.1.14.
如果要想将仓库分成若干个隔离区，根据题意，图中各边的两个结点表示不能存放在一起的化学药品，我们用表示隔离区的代号，则如果在区，那么、不能在区，且、没有关联边，所以它们可以存放在同一区，如果在区，那么、、不能在
区，因此每个隔离区能够存放的化学药品如下：
区：、、
区：、、

展开更多......

收起↑