关 键 词：

大学计算机 数学 基础 何春江 课件 ppt

资源描述：

大学计算机数学基础-何春江-课件PPT,大学计算机,数学,基础,何春江,课件,ppt

内容简介：

第10章 概率论基础 10.1 随机事件与概率,10.1.1 基本概念: 要研究随机现象，就要构造数学模型，在概率论中我们把对随机现象的观察或试验称为随机试验（记作），如果一个现象或实验满足以下三个条件，则称为随机实验。 （1） 可以在相同的条件下重复进行； （2） 每次试验的可能结果不止一个，并且能事先明确知道所有可能的试验结果； （3） 进行一次试验之前不能确定哪一个结果会出现,样本点：随机试验的每个可能结果称为一个基本事件或样本 点，记为 。 样本空间：所有样本点的集合称为样本空间，记为 。 随机事件：样本空间的子集称为随机事件，简称为事件，用大定英文字母表示。,必然事件：如果某事件包含了样本空间中所有样本点，则称为必然事件，记为 。必然事件在每次试验中一定发生。 不可能事件：如果某事件不包含任何样本点，则称为不可能事件，记为 。,10.1.2 事件间的关系及运算,1 包含 若事件 发生必然导致事件 发生，则称事件 包含事件 , 记作 或 2相等 如果两事件同时发生同时不发生，则称为两事件相等.,3事件的和 由事件 和 至少有一个发生构成的事件称为事件 与 事件的和事件，记作 ,4事件的积 由事件 与 同时发生构成的事件称为事件 与 事件的积事件，记作 ,5事件的差,由事件 发生而事件 不发生构成的事件称为事件 与事件 的差，记作 ,6互不相容（互斥）事件,若事件 与事件 不能同时发生，即 ，则称事件 与事件 互不相容，又称事件 与事件 为互斥事件,7对立事件（互逆） 若事件 与事件 满足： （1） ； （2） . 即事件 与 不能同时发生，又必然发生一个，则事件 与事件 称为对立事件（或互逆），并且记作 ,10.1.3 概率 1.频率,在相同条件下进行了 次试验，如果事件 发生了 次，则称 为事件 在这 次试验中发生的频率。记为 . 显然，频率具有以下性质：,（1）对任何事件 ， ； （2） ； （3）互斥事件和的频率等于频率的和.,2 概率的统计定义 当试验次数增大时，事件的频率 将趋于稳定，如果当试验次数 无限增大时， 稳定地在某常数 附近摆动，则称 为事件 发生的概率.记为,10.2 古典概型,10.2.1 古典概型 如果随机试验满足如下条件： （）有限性：样本空间的样本点数（即基本事件数）只有有限个，记为 ； （）等可能性：每个基本事件发生的可能性相等，即 则称为古典概型. 对于古典概型，其概率的计算公式为：,例1 某宾馆共有职工200人，其中女性有160人，现从所有职工中任选一人，选到男性的概率是多少？ 解 样本点总数为200，事件 “选到男性”的样本点数为男职工人数，为 人，因此,例2 在盒子中放有10个球，分别标有号码 ，现从中任取一球，求取得号码为偶数的概率,解 设 ：“取出的球的号码是偶数”； ：“表示取出的球号码为 ”， ,则 中所含基本事件有 ，基本事件个数为5，而事件总数为10，故,10.2.2 概率性质,（1）有限可加性：设 是两两互不相容的事件， 即对于 ， ，则有,（2）对任意事件 ，,（3）若 ，则,10.2.3 概率的加法公式 对于任意两事件 有 若事件 与事件 互不相容，即 ，则,例3 某班学生共40人，其中订数学杂志的有25人，订英语杂志的有20人，两种都订的有15人，求该班中订这两种杂志的人数占总人数的比例是多少,即全班有 的人订了此两种杂志.,10.3 条件概率、乘法公式与事件的独立性,10.3.1 条件概率,显然，条件概率符合概率定义中的三个性质，即 (1)非负性：对于每一事件 有 ； (2)规范性：对于必然事件 有 ； (3)有限可加性：设 是两两互不相容的事件，则有,例1 袋中装有 个白球， 个黑球， 从中一次取出 个球，发现都是同一种颜色的，求这种颜色是黑色的概率,10.3.2 乘法公式,10.3.3 事件的独立性,定义2 若事件 和 满足 则称它们是相互独立的,定理 若事件 和 相互独立，则事件 与 ， 与 ， 与 也相互独立,例3 甲、乙、丙三人各自独立地向同一目标射击一次，命中率分别为 ，求目标被击中的概率,10.3.4 全概公式与逆概公式,定义3 设 为样本空间，一组事件 若满足以下两个条件：,1全概率公式,设事件 是样本空间的一个划分，则对任一事件 有,例4 某批产品由甲、乙、丙三个车间生产，产量分别为 ，各车间的次品率分别为 ，求全部产品的次品率,2逆概公式,设事件 是样本空间的一个划分，则对任一事件 有,因此有,由全概率公式有,上式称为逆概公式，又称为贝叶斯（Bayes）公式,例5 如上例，若取出的一件产品是次品，求该次品是甲、乙、丙生产的概率分别是多少,第10章 概率论基础10.1 随机事件与概率10.1.1 基本概念:要研究随机现象，就要构造数学模型，在概率论中我们把对随机现象的观察或试验称为随机试验（记作），如果一个现象或实验满足以下三个条件，则称为随机实验。（1） 可以在相同的条件下重复进行；（2） 每次试验的可能结果不止一个，并且能事先明确知道所有可能的试验结果；（3） 进行一次试验之前不能确定哪一个结果会出现样本点：随机试验的每个可能结果称为一个基本事件或样本 点，记为 。样本空间：所有样本点的集合称为样本空间，记为 。随机事件：样本空间的子集称为随机事件，简称为事件，用大定英文字母表示。必然事件：如果某事件包含了样本空间中所有样本点，则称为必然事件，记为 。必然事件在每次试验中一定发生。不可能事件：如果某事件不包含任何样本点，则称为不可能事件，记为 。 10.1.2 事件间的关系及运算5事件的差6互不相容（互斥）事件10.1.3 概率1.频率 10.2 古典概型10.2.2 概率性质 例3 某班学生共40人，其中订数学杂志的有25人，订英语杂志的有20人，两种都订的有15人，求该班中订这两种杂志的人数占总人数的比例是多少 10.3 条件概率、乘法公式与事件的独立性10.3.1 条件概率10.3.2 乘法公式10.3.3 事件的独立性10.3.4 全概公式与逆概公式1全概率公式 2逆概公式设事件 是样本空间的一个划分，则对任一事件 有因此有由全概率公式有上式称为逆概公式，又称为贝叶斯（Bayes）公式 例5 如上例，若取出的一件产品是次品，求该次品是甲、乙、丙生产的概率分别是多少第11章 随机变量的分布与数字特征,11.1 随机变量的分布,11.1.1 离散型随机变量及其概率分布,定义1 设离散型随机变量 的全部可能取值为 ( ),且取 的概率为 ,即,由概率的性质可知,分布列具有如下性质:： (1) ; (2) .,例1 袋中有个球，其中个黑球，个白球，现从中随机地抽取个，求取到白球的分布列,解 设 表示取出的白球的个数，则 的可能取值为，1，2，并且有,于是 的分布列为,例2 某设备由三个独立工作的元件构成,该设备在一次试验中每个元件发生故障的概率为0.1,试求该设备在一次试验中发生故障的元件数的分布列.,解 设 为一次试验中发生故障的元件数,则 的可能取值为0,1,2,3.该试验可看成三重独立试验,于是有,例3 设随机变量 的分布列为,求（1） ；（2） ；（3） .,解 由随机变量 的分布列知， 的可能取值为 因此,1 两点分布,若随机变量 的概率分布为,其分布列为,则称 服从参数为 的两点分布.,2 二项分布,若随机变量 的值为 ,并且,其中 , , 为非负整数, 则称 服从参数为 的二项分布,简记为 .,当 时二项分布即为两点分布.,例4 某人进行射击，设每次射击的命中率为 ，独立射击 次，求至少击中两次的概率,解 将一次射击看成一次实验，设击中的次数为 ，则 ，于是所求的概率为,3 泊松分布,若随机变量 的概率分布为,则称 服从参数为 的泊松分布,简记为 .,且有,11.1.3 连续型随机变量及其概率分布,定义2 对于随机变量 ，若存在非负可积函数 使得对任意的 都有,成立，则称 为连续型随机变量， 称为随机变量 的密度函数，或概率密度,对于连续型随机变量 有 ,所以有,密度函数具有如下的性质： （1） ； （2） ,1 均匀分布 若随机变量 的概率密度为,则称 服从 上的均匀分布，记作 ,均匀分布的密度函数具有下列性质： （1） ； （2） ,2 指数分布 若随机变量 的概率密度为,则称 服从参数为 的指数分布，记作 ，其中参数 ,指数分布的密度函数具有下列性质： （1） ； （2） ,例5 假设某元件的寿命服从参数为 的指数分布，求它使用1000小时后还没有损坏的概率 解 设 为该元件的寿命，则,3 正态分布 若随机变量 的概率密度为,其中 、 为大于零的常数，则称 服从参数为 、 的正态分布，记作 ,正态分布的密度函数具有下列性质： （1） ； （2）,正态分布的密度函数曲线具有如下性质：,（1） 在 内处处连续； （2） 的图形关于 对称； （3）在 处， 取得最大值 ； （4）曲线在点 处对应有拐点； （5）参数 确定图形的位置，而参数 决定图形的陡峭程度.,特别地，对于 ， 的正态分布，我们称之为标准正态分布，简记为 ，其密度函数记为,11.1.4 分布函数,1 分布函数概念,定义3 设 是一个随机变量， 是任意实数，函数 称为 的分布函数 对于任意实数 有,2 分布函数性质： （1） 是一个单调不减函数；即若 ，那么 （2） 并且有 ； （3） ，即 满足右连续,3 离散型随机变量的分布函数 设离散型随机变量 的分布列为,由概率的可列可加性得,即,例6 设随机变量 的分布列为,求 的分布函数 ，并求 ， ,解 由于 仅在 三点处取值，故,当 时， 当 时， 当 时， 当 时，,故,所以,4 连续型随机变量的分布函数 设 为连续型随机变量，其密度函数为 ，则有,而对上式两端求关于 的导数得,这正是连续型随机变量 的分布函数与密度函数之间的关系.,例7 设 的分布函数为,求其密度函数 ， ,解,11.1.5 随机变量函数的分布,设 是一个随机变量,则 ( 为连续函数), 作为随机变量 的函数,仍是随机变量, 下面我们对 是离散型的情况进行讨论,设 是一个离散型随机变量，其分布列为,是随机变量 的函数，则随机变量 的分布列为,例10 设离散型随机变量 的分布列为,求 的分布列,解 的取值为0，2，4，其对应的概率分别为,因此 的分布列为,例11 设离散型随机变量 的分布列为,求 的分布列,解 的取值为0，1，4，其对应的概率分别为,11.2 随机变量的数字特征,11.2.1 数学期望,1 离散型随机变量的数学期望,定义4 设离散型随机变量的分布律为,若级数 绝对收敛，则称其和为随机变量 的数学期望，简称期望，记作 ，即,例13 袋中装有10件产品，其中有2件是次品，某人从中一次取一个进行检测，直到取到正品为止，求取得正品前已取出次品数的数学期望,解 设 表示取得正品前已取出的次品数，则 的可能取值为0，1，2，于是有,于是随机变量 的数学期望为,下面介绍几种常见的随想变量的数学期望,1）两点分布,若随机变量 服从两点分布，其分布列为,则,2）二项分布,若随机变量 ，即,则,3）泊松分布,若随机变量 ，即,则,2 连续型随机变量的数学期望,定义5 设连续型随机变量 的密度函数为 ，若积分,绝对收敛，则称该积分值为随机变量 的数学期望，简称期望，记为 ，即,例14 设随机变量 具有密度函数,求 的数学期望,解,例15 设 ，求 ,解,例16 设 （ ），求 ,解,例17 设 ，求 ,解,3 数学期望的性质：,（1）设 为一常数，则 ；,（2）设 为一常数，则 ；,（3）设 、 均为随机变量，则 ；,（4）设 、 均为随机变量且相互独立，则,11.2.2 随机变量函数的数学期望,设随机变量 是随机变量 的函数，且 （ 为连续函数），那么,（1）若 是离散型随机变量，其概率分布为 且 绝对收敛，则,（2）若 是连续型随机变量，其密度函数为 ，且 绝对收敛，则,例18 设离散型随机变量 的分布列为,求 的数学期望,解,例19 设随机变量 服从参数为3的指数分布，求 ,解 由题知 的密度函数为,则,11.2.3 方差,1 方差概念,定义6 设离散型随机变量 的分布列为,如果 存在，则称之为随机变量 的方差，记为 ，即,并称 为 的标准差或根方差,我们经常使用下面的公式进行计算：,2 常见的随机变量的方差,（1）两点分布,服从两点分布的随机变量 ，其数学期望为 ，而,因此,（2）二项分布,服从二项分布的随机变量 ，其数学期望为 ，而,因此,（3）泊松分布,对于服从泊松分布的随机变量 ，其数学期望为 ，而,因此,3 方差基本性质：,（1）设 为一常数，则 ； （2）设 为一常数，则 ； （3）设 、 均为随机变量，则 ； （4）设 为随机变量， 为一常数，则 ,第11章 随机变量的分布与数字特征11.1 随机变量的分布11.1.1 离散型随机变量及其概率分布 例1 袋中有个球，其中个黑球，个白球，现从中随机地抽取个，求取到白球的分布列于是 的分布列为 例2 某设备由三个独立工作的元件构成,该设备在一次试验中每个元件发生故障的概率为0.1,试求该设备在一次试验中发生故障的元件数的分布列.例3 设随机变量 的分布列为1 两点分布其分布列为2 二项分布解 将一次射击看成一次实验，设击中的次数为 ，则 ，于是所求的概率为3 泊松分布若随机变量 的概率分布为且有 11.1.3 连续型随机变量及其概率分布 定义2 对于随机变量 ，若存在非负可积函数 使得对任意的 都有成立，则称 为连续型随机变量， 称为随机变量 的密度函数，或概率密度对于连续型随机变量 有 ,所以有密度函数具有如下的性质：（1） ；（2） 1 均匀分布 若随机变量 的概率密度为则称 服从 上的均匀分布，记作 均匀分布的密度函数具有下列性质： （1） ； （2） 2 指数分布 若随机变量 的概率密度为则称 服从参数为 的指数分布，记作 ，其中参数 指数分布的密度函数具有下列性质： （1） ； （2） 例5 假设某元件的寿命服从参数为 的指数分布，求它使用1000小时后还没有损坏的概率解 设 为该元件的寿命，则3 正态分布 若随机变量 的概率密度为其中 、 为大于零的常数，则称 服从参数为 、 的正态分布，记作 正态分布的密度函数具有下列性质：（1） ；（2）正态分布的密度函数曲线具有如下性质：（1） 在 内处处连续；（2） 的图形关于 对称；（3）在 处， 取得最大值 ；（4）曲线在点 处对应有拐点；（5）参数 确定图形的位置，而参数 决定图形的陡峭程度.特别地，对于 ， 的正态分布，我们称之为标准正态分布，简记为 ，其密度函数记为11.1.4 分布函数1 分布函数概念定义3 设 是一个随机变量， 是任意实数，函数称为 的分布函数对于任意实数 有2 分布函数性质：（1） 是一个单调不减函数；即若 ，那么（2） 并且有 ；（3） ，即 满足右连续3 离散型随机变量的分布函数设离散型随机变量 的分布列为由概率的可列可加性得即 例6 设随机变量 的分布列为求 的分布函数 ，并求 ， 解 由于 仅在 三点处取值，故当 时，当 时，当 时，当 时，故所以4 连续型随机变量的分布函数设 为连续型随机变量，其密度函数为 ，则有而对上式两端求关于 的导数得这正是连续型随机变量 的分布函数与密度函数之间的关系.例7 设 的分布函数为求其密度函数 ， 解 11.1.5 随机变量函数的分布设 是一个随机变量,则 ( 为连续函数), 作为随机变量 的函数,仍是随机变量, 下面我们对 是离散型的情况进行讨论设 是一个离散型随机变量，其分布列为 是随机变量 的函数，则随机变量 的分布列为例10 设离散型随机变量 的分布列为求 的分布列解 的取值为0，2，4，其对应的概率分别为因此 的分布列为例11 设离散型随机变量 的分布列为求 的分布列解 的取值为0，1，4，其对应的概率分别为11.2 随机变量的数字特征11.2.1 数学期望1 离散型随机变量的数学期望定义4 设离散型随机变量的分布律为若级数 绝对收敛，则称其和为随机变量 的数学期望，简称期望，记作 ，即 例13 袋中装有10件产品，其中有2件是次品，某人从中一次取一个进行检测，直到取到正品为止，求取得正品前已取出次品数的数学期望 解 设 表示取得正品前已取出的次品数，则 的可能取值为0，1，2，于是有于是随机变量 的数学期望为下面介绍几种常见的随想变量的数学期望1）两点分布若随机变量 服从两点分布，其分布列为则 2）二项分布若随机变量 ，即则3）泊松分布若随机变量 ，即则2 连续型随机变量的数学期望定义5 设连续型随机变量 的密度函数为 ，若积分绝对收敛，则称该积分值为随机变量 的数学期望，简称期望，记为 ，即例14 设随机变量 具有密度函数求 的数学期望解例15 设 ，求 解 例16 设 （ ），求 解 例17 设 ，求 解 3 数学期望的性质：（1）设 为一常数，则 ；（2）设 为一常数，则 ；（3）设 、 均为随机变量，则 ；（4）设 、 均为随机变量且相互独立，则11.2.2 随机变量函数的数学期望设随机变量 是随机变量 的函数，且 （ 为连续函数），那么（1）若 是离散型随机变量，其概率分布为 且 绝对收敛，则 （2）若 是连续型随机变量，其密度函数为 ，且 绝对收敛，则例18 设离散型随机变量 的分布列为求 的数学期望解 例19 设随机变量 服从参数为3的指数分布，求 解 由题知 的密度函数为则 11.2.3 方差1 方差概念定义6 设离散型随机变量 的分布列为如果 存在，则称之为随机变量 的方差，记为 ，即我们经常使用下面的公式进行计算：2 常见的随机变量的方差（1）两点分布服从两点分布的随机变量 ，其数学期望为 ，而因此 （2）二项分布服从二项分布的随机变量 ，其数学期望为 ，而 因此 （3）泊松分布对于服从泊松分布的随机变量 ，其数学期望为 ，而因此 3 方差基本性质：（1）设 为一常数，则 ；（2）设 为一常数，则 ；（3）设 、 均为随机变量，则 ；（4）设 为随机变量， 为一常数，则 1,第13章 图论初步,2,本章学习目标,我们在前面曾介绍过二元关系的图形表示，即关系图。在关系图中，我们主要关心研究对象之间是否有连线（图论中称为边），这样的图正是图论的主要研究对象。图论中还根据实际需要，将这类图进行了推广，并且把它当作一个抽象的数学系统来进行研究。通过本章学习，读者应该掌握以下内容：,3,本章学习目标,无向图、有向图的定义，图的基本术语的含义 子图、生成子图的概念 无向连通图及有向连通图的有关概念 通路、回路的概念 图的矩阵表示 赋权图的概念及应用 欧拉通路、欧拉回路、欧拉图和半欧拉图的概念 哈密尔顿通路、哈密尔顿回路、哈密尔顿和半哈密尔顿的概念 树的定义 最小生成树的求法 最优树的求法,4,主要内容,13.1 图的基本概念 13.2 图的矩阵表示 13.3 路与回路 13.4 树及其应用,5,13.1 图的基本概念,13.1.1 图的定义,定义13.1.1 图G是一个三元组，G=，其中V(G)是一个非空的顶点集合，E（G）是边的集合，G是从边集合E到顶点无序偶或有序偶集合上的函数。,由定义可知，图G中的每条边都与图中顶点的无序偶或有序偶相联系，若边eE与顶点无序偶vi，vj相联系，则G（e）=vi，vj，此时边e称为无向边，有时简称边；若边eE与顶点有序偶相联系，则G（e）=，此时边e称为有向边或弧。vi称为弧的始点，vj称为弧的终点，有向边的箭头方向自始点指向终点。,6,13.1 图的基本概念,13.1.1 图的定义,例13.1.1 画出下面二图的图形,（1）无向图 ，其中,7,13.1 图的基本概念,13.1.1 图的定义,例13.1.1 画出下面二图的图形,（）有向图 ，其中,8,13.1 图的基本概念,13.1.1 图的定义,例13.1.1 画出下面二图的图形,解：(1)的图形为13.1-3（a）所示，（2）的图形为13.1-3（b）所示。,9,13.1 图的基本概念,定义 设无向图,（1）如果在顶点和顶点之间存在一条边，即若存在且=(u,v)，则称顶点u和顶点v是彼此相邻的，简称相邻的，并称顶点u和顶点v是边e的端点，e与u（或e与v）是彼此关联的。 （2）若ek,el至少有一个公共端点，则称边ek,el是彼此相邻的，简称相邻的。,10,13.1 图的基本概念,13.1.2 顶点的度数,定义13.1.2 设无向图G，v是图G中的顶点，所有与v关联的边的数目，称为顶点v的度数，记作deg(v)。 度数为零的点称为孤立点，度数为1的点称为悬挂点，与悬挂点关联的边称为悬挂边。,定理13.1.1 设图G是具有n个点，m条边的无向图，其中顶点集合为V=v1，v2，vn，则,推论 度数为奇数的顶点个数为偶数。,11,13.1 图的基本概念,定义13.1.3 设有向图G，v是图G中的顶点，以v为始点的有向边的数目，称为v的出度，记个deg+(v)，以v为终点的有向边的数目，称为v的入度，记作deg-(v)。,定理13.1.2 设有向图G具有n个顶点，m条边，其中顶点集合V=v1，v2，vn，则有,证明 因为每一条有向边为始点提供1个出度，为终点提供1个入度，而所有各顶点的出度之和及入度之和均由m条有向边提供，所以定理得证。,12,13.1 图的基本概念,13.1.3 多重图、简单图与完全图,定义13.1.4 如果两个顶点之间存在多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相顶点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含平行边和自回路的图称为简单图。,当图中顶点的数目为有限个数时，称为有限图，否则称为无限图。本章仅讨论有限图。,定义13.1.5 在n阶无向（无向）图中，如果任意两个不同的顶点之间都有一条边关联，则称此图为n阶无向（无向）完全图，记作Kn。,13,13.1 图的基本概念,13.1.2多重图、简单图与完全图,如在图13.1-5中（a）和（b）均为4阶完全图。,14,13.1 图的基本概念,13.1.2多重图、简单图与完全图,定理13.1.3 n阶无向完全图Kn的边数为,证明 在Kn中，因为任意两个顶点间都有边联结，所以Kn的边数为n个顶点中取两个顶点的组合数：,即，Kn的边数为,。,定理13.1.3 n阶无向完全图Kn的边数为,。,15,13.1 图的基本概念,13.1.4 子图,定义13.1.6 设G=和G=是两个图， （1）若VV且EE，则称G是G的子图； （2）若G是G的子图，但VV或EE，则称G是G的真子图； （3）若G是G的子图，且V=V，则称G是G的生成子图或支撑子图。 从上面的定义可以看出，对图G=，G本身和零图G=都是它的生成子图，它们称为G的平凡生成子图。,16,13.1 图的基本概念,13.1.4 子图,如图13.1-6，（a）是（b）的子图且是真子图。,17,13.1 图的基本概念,13.1.4 子图,若 且 ，则称 是 的生成子图（或支撑子图）。,如在图7.1-6中，（a）是（b）的一个生成子图。,18,13.2 图的矩阵表示,13.2.1 图的邻接矩阵表示,定义13.2.1 设图G的顶点集合为V，边集为E，且 V=v1，v2，vn，令 aij=,则称矩阵Aaij为图G的邻接矩阵。,19,13.2 图的矩阵表示,13.2.1 图的邻接矩阵表示,图13.2.1 有向图G 例如，图13.2.1的邻接矩阵为：,图13.2.1,20,13.2 图的矩阵表示,13.2.1 图的邻接矩阵表示,从图G的邻接矩阵中，还可以得到图的很多重要的性质： （1）令B=A2，则有 bij=,，bij表示从vi到vj长度为2的通路数目。如果bij=0，则表示不存在长度为2的通路。而bii表示经过vi的长度为2的回路数目。 （2）令C=Ar，则此时cij表示从vi到vj长度为r的通路数目。如果cij=0，则表示不存在长度为r的通路。而cii表示经过vi的长度为2的回路数目。,21,13.2 图的矩阵表示,13.2.2 图的关联矩阵表示,定义13.2.2 设无环无向图G=，V=v1，v2，vn，E=e1，e2，em，则矩阵M（G）=（mij）nm，其中 mij=,称M（G）为完全关联矩阵。,图13.2.3,例如，图13.2.3所示的无向图G的关联矩阵为： M（G）=,e1 e2 e3 e4 e5 e6,22,13.2 图的矩阵表示,关联矩阵与图是相互唯一确定的，因而M（G）也描述了G的一切特征，从关联矩阵可以看出图形的一些性质： （1）M（G）中的每一列只有两个1，说明图中每一条边关联两个顶点。 （2）M（G）中每一行元素的和数对应顶点的度数。一行中元素全为0，其对应的顶点为孤立顶点。 （3）M（G）中，若两列相同，则它们对应的边为平行边。,13.2.2 图的关联矩阵表示,23,13.2 图的矩阵表示,13.2.2 图的关联矩阵表示,定义13.2.3 设简单有向图G=，V=v1，v2，vn，E=e1，e2，em，则矩阵M（G）=（mij）nm，其中,称M（G）为G的完全关联矩阵。,mij =,24,13.2 图的矩阵表示,有向图的完全关联矩阵也有类似于无向图的一些性质。如： （1）关联矩阵中每列的元素之和为0，说明有向图中每条边关联两个顶点，一个始点，一个终点。 （2）第i行元素的绝对值之和为对应顶点的度数，其中1的个数为出度，-1的个数为入度。 （3）关联矩阵中，1的个数与-1的个数相同，都等于边的数目，这说明有向图中各顶点入度之和等于出度之和，都等于边数，于是各顶点度数之和等于边数的2倍。 （4）若关联矩阵中有两列相同，说明图中这两列对应的边有相同的始点和终点，因而它们是平行边。,13.2.2 图的关联矩阵表示,25,13.2.3 图的可达矩阵表示,定义13.2.4 设n阶简单有向图G=，V=v1，v2，vn，令 pij=,则称矩阵Ppij为图G的可达矩阵。记作P（G），简记为P。 可达性矩阵表明图中任意两个顶点间是否至少存在一条路以及在任何顶点上是否存在回路。 可通过图G的邻接矩阵A得到G的可达性矩阵P，令Rn=（rij）nn， Rn=A+A2+A3+An 将Rn中不为0的元素改为1，为0的元素不变，这个改变后的矩阵即为可达性矩阵P。,26,例13.2.2 求图G=的可达性矩阵，其中V=v1，v2，v3，v4，E=，。 解 图G的邻接矩阵为 A=,A2=,A3=,A4=,故,R4=,P=,13.2.3 图的可达矩阵表示,27,13.3 路与回路,13.3.1 通路与回路,定义13.3.1 在无向图（或有向图）G=中，设v0，v1，vnV，e0，e1，enE，其中ei是关联于顶点vi-1，vi的边，交替序列v0e0v1e1en-1 vn称为联结v0到vn的通路或路。v0和vn分别称为通路的起点和终点，通路中所含边的条数称为该通路的长度。如果通路中的始点与终点相同，则称这条路为回路。,下面介绍两种常用的特殊通路与回路。 简单通（回）路：如果一条（回）路中的各边都是不相同的，则称这样的（回）路为简单通（回）路。 基本通（回）路：如果一条（回）路中的各个顶点都是不相同的，则称这样的（回）路为基本通（回）路。,28,13.3 路与回路,定理13.3.1 在n阶无向图中，如果存在一条从vi到vj的通路，则从vi到vj必有一条长度不大于n-1的基本通路。 证明 设从vi到vj存在的通路为vivj，若其中有相同的顶点vk，如vivkvkvj，则删去vk到vk的这些边，它仍是vi到vj的通路，如此反复进行，直到没有重复顶点为止，此时所得的通路就是vi到vj的基本通路。由于1条基本通路的长度比此通路中顶点数少1，而图中仅有n个顶点，故此基本通路的长度不大于n-1。,13.3.1 通路与回路,29,13.3 路与回路,定理13.3.2 在n阶无向图中，如果存在一条通过vi的回路，则必有一条长度不大于n的通过vi 的基本回路。,13.3.1 通路与回路,30,13.3 路与回路,13.3.2 图的连通性,定义13.3.2 设图G是无向图，u和v是图G中的两个顶点，如果u和v之间有通路，则称u，v是连通的，并规定u与自身是连通的。 容易验证，点的连通关系是等价关系，这个等价关系所对应的划分把图G的点集V分成若干个非空子集V1，V2，Vk，其中每一个子集Vi（i=1，2，k）中的顶点和G中以Vi中的顶点为端点的边组成的G的子图（即点集Vi的导出子图）称为图G的一个连通分支。,31,13.3 路与回路,13.3.2 图的连通性,定义13.3.3 若图G是平凡图或G中任意两点都是连通的，则称图G为连通图，否则称G为非连通图或分离图。 例如，图13.3.2是连通图，图13.3.3是非连通图，它由两个连通分支构成。,图13.3.2 连通图 图13.3.3 非连通图,32,13.3 路与回路,定义13.3.5 在有向图G=中，若从顶点u到v有通路，则称u可达v。 一般来说，可达性不是对称的，因为如果从u到v有通路，但不一定存在从v到u的通路。 如果u可达v，它们之间可能不止一条路，在所有这些路中，最短路的长度称为顶点u和v之间的距离，记作d，它满足下列性质： d=0 d0 d+dd 如果从u到v是不可达的，则通常写为d=。注意当u可达v，且v可达u时，d不一定等于d。关于距离的概念对无向图也适用。通常把D=,称为图的直径。,13.3.2 图的连通性,33,13.3 路与回路,定义13.3.6 有向图的连通性分为强连通、单向连通和弱连通三种。 强连通：在有向图中，如果图中任意两点vi，vj存在着vi到vj的通路，并且存在着vj到vi的通路，则称此有向图为强连通图。 单向（侧）连通：在有向图中，如果图中任意两点vi，vj存在着vi到vj的通路，或者存在着vj到vi的通路，则称此有向图为单向（侧）连通图。 弱连通：如果有向图的底图是无向连通图，则称此有向图为弱连通图。,13.3.2 图的连通性,34,13.3 路与回路,例如，在图13.3.5（a）中，由点集v1，v2，v3，v4或v5导出的子图是强分支。由点集v1，v2，v3，v4，v5导出的子图是单向分支也是弱分支。在图7.22（b）中，由点集v1，v2，v3，v4导出的子图是强分支。由点集v1，v2，v3，v1，v3，v4导出的子图是单向分支，由点集v1，v2，v3，v4导出的子图是弱分支。,图13.3.5 连通分支,13.3.2 图的连通性,35,13.3 路与回路,定理13.3.3 在有向图G=中，它的每一个顶点位于且仅位于一个强分支中。,13.3.2 图的连通性,例13.3.1 设图G是n阶无向简单图，且图G中任意不同的两个顶点的度数之和大于等于n-1,证明图G是连通图。 证明 用反证法。 假设图G不是连通图，则G是由多个连通分支构成，不妨设有k个连通分支G1，G2，Gk构成，并设连通分支G1中含有n1个顶点，连通分支G2中含有n2个顶点，连通分支Gk中含有nk个顶点。显然n1+n2+nk=n 如果在连通分支G1中任取一点u，由于连通分支G1是简单图，G1中任意一点的度数小于等于n11，所以有deg（u）n1-1 再在连通分支G2中任取一点v，同理有deg（v）n2-1 于是有deg（u）+deg（v）n1 1+n2-1=（n1+n2）-2n-2 这与题设：“图G中任意不同的两个顶点的度数之和大于等于n-1”相矛盾，所以图G是连通图。,36,13.3 路与回路,13.3.3 欧拉图与哈密顿图,定义13.3.8 给定无孤立顶点图G，如果图中存在一条通过图中各边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图，称为欧拉图。如果图中存在一条通过图中各边一次且仅一次的通路，则称此通路为欧拉通路，具有欧拉通路的图，称为半欧拉图。 在图13.3.7中，图（a）具有欧拉回路，所以图（a）图是欧拉图。图（b）具有欧拉通路，所以图（b）是半欧拉图，图（c）图既不是欧拉图也不是半欧拉图。,图13.3.7 欧拉图、半欧拉图、既不是欧拉图也不是半欧拉图,37,13.3 路与回路,定理13.3.4 无向连通图G是欧拉图的充分必要条件是图中各点的度数为偶数。 证明 如果图G为平凡图则定理显然成立。所以我们下面讨论的都是非平凡图。 首先证必要性。设C是图G的欧拉回路，则当通过C的每一顶点时，该顶点总有进出两个方向的边，把该顶点的度数增加2，又因为C中每条边仅出现一次，所以每个顶点的度数必是偶数。,13.3.3 欧拉图与哈密顿图,38,充分性。对图G的边数采用数学归纳法。 当边数m=1时，显然图仅由一个自回路构成，此自回路即为欧拉回路。 由于图G是连通图，并且每个点至少为2度，所以图G中必有一条回路。设此回路为C。如果C包含G中所有边，则定理得证。如果C不所包含G中所有的边，从图G中删去C中所有边，得到图H，当然，图H可能是不连通的，但图H的边数比图G的边数少，并且图H中的每个顶点仍为偶数度点。由归纳假设可知，图G的每一个连通分支是欧拉图，又因为G是连通图，所以图H的每一个连通分支与回路C至少有一个公共点，于是我们从C中任一点出发，沿C中的边行走到达与图H的一个连通分支的公共点u，然后在图H的这个连通分支中通过一条该连通分支的欧拉回路再回到u，继续沿C的边行走到达与图H的另一个连通分支的公共点w，重复整个过程，最后得到一条包含G中所有边的欧拉回路。,39,13.3 路与回路,定理13.3.5 无向连通图是半欧拉图的充分必要条件是：图中至多有两个奇数度顶点。,定理13.3.6 设图G是有向连通图，图G是欧拉图的充分必要条件是：图中每个顶点的入度和出度相等。,13.3.3 欧拉图与哈密顿图,定理13.3.7 设图G是有向连通图，图G是半欧拉图的充分必要条件是：至多有两个顶点，其中一个顶点的入度比它的出度多1，另一个顶点的出度比它的入度多1，而其他顶点的入度和出度相等。,40,13.3 路与回路,定义13.3.9 给定图G，如果图中存在一条通过图中各顶点一次且仅一次的回路，则此回路称为哈密尔顿回路，具有哈密尔顿回路的图,称为哈密尔顿图。如果图中存在一条通过图中各个顶点一次且仅一次的通路，则此通路称为哈密尔顿通路，具有哈密尔顿通路的图,称为半哈密尔顿图。 例如，在图13.3.11中，（a）是哈密尔顿图，（b）是半哈密尔顿图，（c）既不是哈密尔顿图也不是半哈密尔顿图。,图13.3.11 哈密尔顿图、半哈密尔顿图和非半哈密尔顿图,13.3.3 欧拉图与哈密顿图,41,13.3 路与回路,13.3.3 欧拉图与哈密顿图,定理13.3.8 设图G=是哈密尔顿图，则对于顶点集V的每个非空子集S，都有W（G-S）|S|成立，其中W（G-S）是G-S中的连通分支数。 证明 设C是图G的哈密尔顿回路，则对于V的任何一个非空子集S在C中删去S中任一顶点a1，则C-a1是连通的非回路，若再删去S中另一顶点a2，则W（C-a1-a2）2，由归纳法可得：W（C-S）|S| 同时C-S是G-S的一个生成子图，因而W（G-S）W（C-S） 所以，W（G-S）|S|。 利用这个定理，可以判定某些图不是哈密尔顿图。,42,13.3 路与回路,定理13.3.9 设图G是具有n个顶点（v1，v2，vn）的无向简单图，如果图G中任意两个不同顶点的度数之和大于等于n-1，即deg(vi)+deg(vj)n-1 则图G具有哈密尔顿通路，即G是半哈密尔顿图。,13.3.3 欧拉图与哈密顿图,定理13. 3.10 设图G是具有n个顶点（v1，v2，vn）的无向简单图，如果图G中任意两个不同顶点的度数之和大于等于n，即 deg（vi）+deg（vj）n 则图G具有哈密尔顿回路，即G为哈密尔顿图。,43,13.3 路与回路,定义13.3.10 给定图G=，V中有n个顶点，若将图G中度数之和至少是n的非邻接顶点连接起来得到图G，对图G重复上述步骤，直到不再有这样的顶点存在为止，所得到的图，称为图G的闭包，记作C（G）。,13.3.3 欧拉图与哈密顿图,定理13.3.11 当且仅当一个简单图G的闭包是哈密尔顿图时，则图G是哈密尔顿图。,例13.3.3 设有n个人，其中任意两个人合在一起能认识其余n-2个人，证明当n4时，这n个人可以围成一圈，使每个人的两边都是他认识的人。（这里所说的“认识”是指相互认识）。,44,13.3 路与回路,13.3.3 欧拉图与哈密顿图,证明 设用n个点表示n个人，如果两人认识，就在表示这两个人的两点之间连一条边，从而得到一个n阶无向简单图。题意可知，即要求证明这个n阶无向简单图具有哈密尔顿回路。 由题设可知，此图中的任意不同两点都有 deg（vi）+deg（vj）n-2 现分两种情况讨论。 第一种情况：如果vi和vj之间有边相连，则deg（vi）+deg（vj）n，见图13.3.14（a）。 第二种情况：如果vi和vj之间没有边相连，也即vi所表示的人与vj所表示的人是不认识的（以后简称为vi和vj是不认识的）。则可以证明：vi和余下n-2个人都认识，vj也和余下n-2个人都认识，见图13.3.14（b）。因为如果存在vk，它仅与vi有边相连，而与vj没有边相连，见图13.3.14（c），则可考察点vi和vk，易见，这两个点与vj都没有边相连，因此对于vi和vk，他们合起来不能认识余下n-2个人（他们都不认识vj）。这与“任意两个人合起来认识余下的n-2个人”的题设矛盾，由此可得 deg（vi）=n-2 deg（vj）=n-2 deg（vi）+deg（vj）=2n-4 易见，当n4时，deg（vi）+deg（vj）n。 综合这两种情况可知，此图是哈密尔顿图。,45,13.3 路与回路,13.3.4 赋权图与最短通路,狄克斯特拉算法。 假定无向赋权图G=有n个顶点，要求从v1到其余各顶点的最短路径，狄克斯特拉算法的基本思想是： （1）将顶点集合V分成两部分：一部分称为具有P（永久性）标号的集合，另一部分称为具有T（临时性）标号的集合。初始时，P=v1，T=V-P。 （2）对T中每一个元素v计算D（v），根据D（v）值找出T中距v1最短的一个顶点，写出v1到v的最短路径的长度D（v）。 （3）令P=Pv，T=T-v，如果P=V或T=，则停止，否则转到（2）。,46,13.3 路与回路,13.3.4 赋权图与最短通路,在（2）中，D（v）表示从v1到v的不包含T中其它顶点的最短通路的长度，但D（v）不一定是从v1到v的距离，因为从v1到v的更短通路可能包含T中另外的顶点。 首先证明“若v是T中具有最小D值的顶点，则D（v）是从v1到v的距离”，用反证法证明。若有另外一条含T中顶点的更短通路，不妨设这个通路中第一个属于T-v的顶点是t，于是D（t） D（v），但这与题设矛盾。这就证明了论断正确。 其次，说明计算D（v）的方法。初始时，D（v）=d（v1，v），如果（v1，v）E，则D（v）=，现在假设对T中的每一个v计算了D值。设t是T中D值最小的一个顶点，记P=Pt，T=T-t，令D（t）表示T中顶点t的D值，则 D（t）=minD(t)，D(t)+d（v，t） 下面分情况证明上式： （1）如果从v到t有一条最短路径，它不包含T中的其它顶点，也不包含t点，则D（t）=D（t）。 （2）如果从v到t有一条最短路径，它从v1到v，不包含T中的顶点，有边（v，t），这种情况下，D（t）= D（t）+d（v，t）。 除了这两种情况外不再有其它更短的不包含D另外顶点的路径了。,47,13.3 路与回路,例13.3.3 计算图13.3.15中v1到v5的最短路径。,图13.3.15 赋权图,13.3.4 赋权图与最短通路,48,解 初始P=v1，T=v2，v3，v4，v5，v6，v7，D（v1）=0，D（v2）=4，D（v3）=，D（v4）=，D（v5）=，D（v6）=，D（v7）=1。因为D（v7）=1是T中最小的D值，所以将v7加入到P中，即P=v1，v7，T=v2，v3，v4，v5，v6，然后计算T中各点的D值： D（v2）=min4，1+2=3； D（v3）=min，1+7=8；D（v4）=min，=； D（v5）=min，=； D（v6）=min，1+8=9； D（v2）是T中最小的D值，将v2加入到P中，即P=v1，v7，v2，T=v3，v4，v5，v6，然后计算T中各点的D值： D（v3）=min8，3+3=6； D（v4）=min，3+9=12； D（v5）=min，=； D（v6）=min9，=9； D（v3）是T中最小的D值，将v3加入到P中，即P=v1，v7，v2，v3，T=v4，v5，v6，然后计算T中各点的D值： D（v4）=min12，6+5=11； D（v5）=min，6+9=15； D（v6）=min9，6+1=7； D（v6）是T中最小的D值，将v6加入到P中，即P=v1，v7，v2，v3，v6，T=v4，v5，然后计算T中各点的D值： D（v4）=min11，=11； D（v5）=min15，7+3=10； D（v5）是T中最小的D值，所以，v1到v5的最短距离是10，如果每次在求T中最小的D值时，把各点通过的通路记录下来，就能得到最短通路所经过的顶点。本例中v1到v5的最短通路是v1v7v2v3v6v5。,13.3 路与回路,49,13.3 路与回路,表格的形式给出,表13.1 求最短通路,50,13.3 路与回路,由表可知， v1到v2的最短通路长为3，最短路为v1v7v2。 v1到v3的最短通路长为6，最短路为v1v7v2v3。 v1到v4的最短通路长为11，最短路为v1v7v2v3v4。 v1到v5的最短通路为10，最短路为v1v7v2v3v6v5。 v1到v6的最短通路为7，最短路为v1v7v2v3v6。 v1到v7的最短通路为1，最短路为v1v7。,51,13.4 树及其应用,13.4.1 无向树及其性质,定义13.4.1 设T是无回路的无向简单连通图，则称T为无向树，或简称为树。在树中，度数为1的点称为树叶，度数大于1的点称为内顶点或分枝点。,定理13.4.1 设T是含n个顶点和m条边的简单无向图，则下列各结论都是等价的，都可作为无向树的定义。 （1）T连通且无回路。 （2）T中任意两个不同的顶点间，有且仅有一条通路相连。 （3）T无回路且n=m+1。 （4）T连通且n=m+1。 （5）T连通，但删去树中任意一条边，则变成不连通图。 （6）T连通且无回路，若在T中任意两个不邻接的顶点中添加一条边，则构成的图包含唯一的回路。,52,13.4 树及其应用,定理13.4.2 设T是n阶非平凡的无向树，则T至少有两片树叶。,证明 因为T是连通的，对于任意的viV，有deg（vi）1并且deg（vi）=2（n-1）=2n-2。 若T中每个顶点的度数都大于等于2，则deg（vi）2n，产生矛盾。 若T中只有一个顶点度数为1，其他顶点的度数都大于等于2，则deg（vi）2（n-1）+1=2n-1，得出矛盾。 所以T中至少有两个1度顶点，即T至少有两片树叶。,53,13.4 树及其应用,13.4.1 生成树与最小生成树,定义13.4.2 设G是无向连通图，若G的一个生成子图（含有图G的所有顶点的子图）T是一棵树，则称图T为图G的生成树。,定义13.4.3 在图的所有生成树中，树权之和最小的生成树，称为最小生成树。,54,13.4 树及其应用,定理13.4.3 设图有n个顶点，可用下面的算法产生最小生成树。 （1）选取最小边e1，设边数k=1； （2）若k=n-1，结束，否则转（3）； （3）设已选择边为e1，e2，ek，在G中选择不同于e1，e2，ek的边ek+1，使ek+1是满足e1，e2，ek，ek+1中无回路的权最小的边。 （4）k=k+1，转（2）。 上面给出的求最小生成树的算法，是克鲁斯卡尔在1956年首先提出的。,55,13.4 树及其应用,13.4.3 有向树,定义13.4.4 如果一个有向图在去掉方向后为无向树，则称该有向图为有向树。,定义13.4.5 在有向树T中，如果有且仅有一个入度为0的点。其他点的入度均为1，则称有向树T为有根树，简称根树。入度为0的点称为根，出度为0的点称为树叶或叶片，出度不为0的点称为分枝点或内顶点。,56,13.4 树及其应用,定义13.4.7 根树包含一个或多个顶点，这些顶点中某一个称为根，其他所有顶点被分成有限个子根树。,定义13.4.8 在根树中，如果每一个顶点的出度小于或等于k，则称这棵树为k叉树。若每一个顶点的出度恰好等于k或零，则称这棵树为完全k叉树，若所有树叶的层次相同，称为正则k叉树。当k=2时，称为二叉树。,13.4.3 有向树,57,13.4 树及其应用,例如，在图13.4.7中，（a）是4叉树，（b）是完全4叉树，（c）是正则3叉树。,图13.4.7 4叉树、完全4叉树和正则3叉树,13.4.3 有向树,58,13.4 树及其应用,定义13.4.9 在根树中，如果每一个顶点的儿子都规定次序（一般采用自左到右），则称此树为有序树。,图13.4.8 有序