14.2 通路、回路(simple)

通路与回路的定义第十一章图的连通性本章各节间的关系概图11.1 通路与回路11.2 无向图的连通性11.3 有向图的连通性无向图连通连通有向图图的连通性在计算机科学技术相关领域的应用回路通路回路图的连通性操作系统判断并发进程是否存在递归和死锁计算机网络表示网络优化最短路径定义11.111.1通路与回路基本回路：一条回路，除始点与终点相同外其余结点均不相同，则称该路径为基本回路或者圈。

简单回路：一条回路经过的所有边均不相同，则称该回路为简单回路或闭迹。

长度：路径P中所含的边数称为路径P的长度。

长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。

注意：基本路径必定是简单路径，基本回路必定是简单回路，反之不一定成立。

11.1通路与回路表示法①定义表示法②只用边表示法③只用顶点表示法（在简单图中）④混合表示法（顶点表示法基础上标示平行边）环（长为1的圈）的长度为1，两条平行边构成的圈长度为2，无向简单图中，圈长≥3，有向简单图中圈的长度≥2.例11.1：在下图中分别找出一条基本路径、简单路径、基本回路和简单回路。

v 1e 2e 1e 3e 4e 6e 8e 5e 7v 3v 5v 4v 2解：路径：基本路径：简单路径：基本回路：简单回路：定理11.1在一个具有n个结点的图中，如果从结点v j到结点v k存在一条路径，则从结点v j到结点v k存在一条不多于n?1条边的路径。

证：如果从结点v j到结点v k存在一条路径，则该路径上的结点序列是[ ]。

如果在这路径上有m条边，则序列中必有m+1个结点。

若m n?1，则必有结点，它在序列中不止一次出现，即必有序列[ ]，在路径中去掉从v到v s的这些边，仍然得到一条从s结点v j到结点v k的路径，但此路径比原来的路径的边数要少。

如此重复进行下去，必得到一条从结点v j到结点v k不多于n?1条边的路径。

证毕。

例11.2：无向完全图K3的顶点依次标定为a，b，c。

教案：14.2 让电灯发光一、教学内容1. 电路的基本概念：电源、用电器、开关、导线等。

2. 电路的两种状态：通路和断路。

3. 电路图的绘制方法。

4. 电灯发光的原理。

二、教学目标1. 让学生掌握电路的基本概念和电路的两种状态。

2. 培养学生绘制电路图的能力。

3. 让学生了解电灯发光的原理，提高学生的物理素养。

三、教学难点与重点1. 教学难点：电路图的绘制方法，电灯发光的原理。

2. 教学重点：电路的基本概念，电路的两种状态。

四、教具与学具准备1. 教具：电源、电灯、导线、开关等。

2. 学具：笔记本、笔。

五、教学过程1. 实践情景引入：展示一个简单的电路，让学生观察并描述电路的组成。

2. 知识讲解：(1) 讲解电路的基本概念，引导学生理解电源、用电器、开关、导线等电路元件的作用。

(2) 讲解电路的两种状态：通路和断路，并通过实际操作演示。

(3) 讲解电路图的绘制方法，引导学生学会绘制简单的电路图。

3. 例题讲解：以电灯发光为例，讲解电灯发光的原理。

4. 随堂练习：让学生绘制一个电灯发光的电路图，并解释电路图中的各个元件的作用。

5. 课堂小结：回顾本节课所学内容，强调电路的基本概念和电路的两种状态。

六、板书设计板书设计如下：电源——用电器——开关——导线通路：电流畅通的状态断路：电流被切断的状态电灯发光的原理七、作业设计1. 作业题目：绘制一个电灯发光的电路图，并解释电路图中的各个元件的作用。

答案：略2. 作业题目：用自己的语言描述电路的两种状态。

答案：电路的两种状态分别是通路和断路。

通路指的是电流畅通的状态，断路指的是电流被切断的状态。

八、课后反思及拓展延伸1. 课后反思：本节课通过实际操作和讲解，使学生掌握了电路的基本概念和电路的两种状态，大部分学生能够绘制简单的电路图。

但在教学过程中，对于电路图的绘制方法，部分学生仍存在一定的困难，需要在今后的教学中加强指导。

2. 拓展延伸：引导学生探索更多电路元件的作用和电路的复杂状态，提高学生的物理素养。

通路和回路1. 图的矩阵表示矩阵表示便于我们把图存入计算机中，也便于对图进行代数运算。

定义1.1邻接矩阵（adjacent matrix ）以各顶点为行标和列标的方阵A ，其中项A ij =连接顶点i 和j 的边的个数。

关联矩阵（incidence matrix ）以各顶点为行标和以各边为列标的矩阵M ，其中若顶点i 与边j 相关联，则M ij =1，否则M ij =0。

例1.2邻接矩阵：关联矩阵：2. 通路与可达关系定义2.1 通路（walk ）：在无向图中，通路是相邻的边顺次组成的序列。

在有向图中，通路中相邻的边还必须满足，前一条边的终点是下一条边的起点。

位于通路最左端的顶点称为该通路的起点（initial vertex ，start vertex ），位于最右端的顶点称为该通路的终点（final vertex ）。

若a ,b 分别是某通路的起、终点，则称从顶点a 可达顶点b ，记为a→b 。

通路的长度：非加权图中，一条通路的长度是指其中边出现的次数。

在加权图中，一条通路的长度是指其中出现的所有边（包括重复出现的边）的权重之和。

路径（trail ）：所含边互不相同的通路称为路径。

简单路径（path ，复数为paths ）：所含顶点互不相同的通路称为简单路径。

课本第289页定理14.11.定理2.2 在图G 的邻接矩阵A 的k 次幂A k 中，A ij 表示从顶点i 到j 的所有长度为k 的通路的总数。

v 2 v 3e 5 e 1推论2.3 2k+++A A A定义2.4 可达矩阵。

3.最短路径问题最短路径：距离：d(u,v)=从u到v的最短路径的长度。

约定：d(u,u)=0；若u不可达v，则d(u,v)=+∞问题描述：给定一个加权无向图G=(V,E,W)，其中每条边e的权重W(e)为非负实数，找出从某顶点s到另外一个顶点之间的最短路径。

Dijkstra算法：由E. W. Dijkstra与1959年给出。

《电路》知识要点归纳1．正负电荷的确定：自然界只存在正电荷和负电荷。

物理学中把绸子摩擦过的玻璃棒上带的电荷叫做正电荷，毛皮摩擦过的橡胶棒上带的电荷叫做负电荷。

这里需要注意的是：(1)要明确自然界中只有两种电荷，并要记住正电荷、负电荷是如何规定的。

(2) 凡是与绸子摩擦过的玻璃棒带相同的电荷，都为正电荷，凡是与毛皮摩擦过的橡胶棒带相同的电荷，都为负电荷。

2．电荷间的相互作用规律：同种电荷互相排斥，异种电荷互相吸引。

由电荷间的相互作用规律可以判断：(1)物体是否带电，如：用一带电体与一物体相接触，发现物体与带电体相吸引，说明该物体可能带电，也可能不带电，若发现物体与带电体相排斥，则说明该物体一定带电，且与带电体带的是同种电荷。

(2)带电体带的是何种电荷，如：用一带已知电荷的物体与一带未知电荷的物体相接触，出现吸引现象，说明两物体带相反的电荷；出现排斥现象，说明两物体带相同的电荷。

3．电量及其单位：电荷的多少叫做电量。

电量的单位是库仑，简称库，符号是C。

实验室里检验物体是否带电，常用验电器。

对于验电器需要说明的是：(1)验电器的制作原理：它是利用电荷间的相互作用规律制成的，当用带电体接触验电器的金属球时，就有一部分电荷转移到验电器的两金属箔上，这两片金属箔由于带同种电荷互相排斥而张开。

(2)利用验电器能够检验物体是否带电或物体带电荷的多或少。

(3)利用验电器还能够确定带电体带何种电荷。

(4)利用验电器可以检验同一带电体所带电荷的多少，不能检验不同带电体所带电荷的多少，验电器也不能检验出带电体所带电荷个数的多少。

4．原子结构：原子是由位于中心的原子核和核外的电子组成的；原子核带正电，电子带负电；在通常情况下，原子核所带的正电荷与核外电子总共所带的负电荷在数量上相等，整个原子呈中性，对外不显示带电性质。

这里需要注意的是：(1)一切宏观物体都是由原子组成的，在通常情况下，原子是中性的，物体也呈中性，对外不显示带电性质。