图的基本概念
第一章 图的基本概念
第一节 图和有向图
定义1.1 一个无向图图（graph ）G 是指一个二元组),(E V ，其中集合V 中的元素称为顶点（或点,或端点, 或结点）（or vertice, or node, or point), 集合E 中元素为V 中元素组成的无序对，称为边 (edge).
注意：1. 上述集合E 中的元素可以相同，有的文献称这样的集合为多重集。
2. 图),(??称为空图，它有时在举反例的时候用到，且有时将一个结论推广到包含空图时会引起不必要的麻烦, 故本书中假设所讨论的图都不是空图。
3. 在一个图=G ),(E V 中，为了表示V 和E 分别是G 顶点集合边集，常将V 和E 分别记为)(G V 和)(G E .
我们经常用图形来表示一个图。用小圆圈或实心点表示图的顶点，用线段把无序对中两个顶点连接起来表示边。其中顶点的位置，连线的曲直、是否相交等都无关紧要. 例如，=G ),(E V ，V =}{54321,,,,v v v v v ，=G }{),(),,(),,(),,(),,(),,(544231212111v v v v v v v v v v v v ，G 的图形如下.
3v 4v
e 2 5v
1v 2v
1e
图. 1.
设=G ),(E V . 若V 为有限集，则称G 为有限图（finite graph ）；若V 为单点集，则称G 为平凡图 (trivial graph ). 为方便起见，常用e i 表示边，例如在图1中2e 表示边),(31v v , 而1v ,3v 称为2e 的端点. 两个顶点相同的边称为环 (loop), 具有相同顶点的多条边称为重边 (multiple edge), 不含环和重边的图称为简单图 (simple graph). 例如在图1中1e 为环, 32,e e 为重边，所以此图不是简单图.
定义1.2 设图G 的顶点集为)(G V ={}n v v v ,...,,21，边集为)(G E ={}m e e e ,...,,21.G 的邻接矩阵（adjacency matrix ）)(G A 是一个n n ?矩阵，元素j i a ,为端点的边的数目。G 的
关联矩阵（incidence matrix ）)(G M 是一个m n ?矩阵，元素j i m ,为1，当i v 是j e 的端点. 否
则，元素j i m ,为0. 顶点v 的度（degree ）是其作为边的端点的个数, 记为)(v d .
例1.3 图1的邻接矩阵和关联矩阵分别如下:
?????
??????????
?
注意：邻接矩阵由顶点的顺序决定. 任意邻接矩阵都是对称的. 邻接矩阵法是将一个图
储存于计算机的方法之一. 在关联矩阵或邻接矩阵中，将某顶点对应的行的元素求和，就得
到该顶点度数. 关于顶点度数，我们有下面的基本定理.
定理1.4 设图G 的顶点集为)(G V ={}n v v v ,...,,21，边集为E =m , 则
∑=n
i i
v d 1)(= .2m 推论 图中度为奇数的顶点个数为偶数.
我们称一个图的所有顶点度数的非递增序列为这个图的度序列. 例如图1的度序列为
（4,3,2,2,1）. 每个图都有一个度序列，反之，并非每个非递增序列都为度序列，例如
（5,4,3,2,1）就不可能是某个图的度序列，因为定理1.4告诉我们，一个非递增序列要成为
某个图的度序列，必须先满足序列的元素和为偶数. 其实，这个显然的必要条件也是充分的.
定理1.5 非负整数1d ,2d ,...,n d 是某个图的所有顶点度数当且仅当
∑i d 是偶数. 证明 ? 显然.
? 设}{n v v v V ,...,,21=. 显然集合{i v : i d 是奇}
数的元素个数为偶数. 将此
集合中元素两两配对，对每个元素对，构造一条边使其端点为元素对. 则此时每个顶点i v 需
要的度数是偶数（非负），在i v 处加上??2/i d 个环，就得到以V 为顶点集的图，且i v 的度
为i d .
定理1.5的证明是构造性的，当然可以用其它方法来证明，例如用归纳法（对n 或
∑i d 进行归纳），证明留给读者. 定理1.5中对度序列的刻画比较简单是因为允许使用环.如果不允许使用环，∑i
d 是偶数的条件就不充分了. 我们在习题中给出无环图度序列的刻画. 关于简单图度序列的刻画以及更多关于度序列的内容参考[1] .
定义 1.6 图G 中顶点和边的交替序列Γ=n n v e e v e v ...2110称为一条),(0n v v -通道
(),(0n v v -walk ), 如果1-i v 和i v 是i e 的端点. 0v 和n v 分别称为通道Γ的起点(origin)和终点
(terminus)，其它顶点称为内点. Γ中边的数目n 称为通道的长度. 若起点和终点相同，称此
通道是闭的. 如果Γ中的边互不相同，则称Γ为一条迹（tail ）; 如果Γ中的顶点互不相同，
则称Γ为一条路径（path ）. 起点和内点互不相同的闭通道称为圈（cycle). 若对于图中任意
两个顶点i v 和j v ，都存在一条),(j i v v -通道，则称此图是连通的（connected ）.
在图2中， 为通道， 为闭迹， 为路径
定义1.7 设=G ),(E V ，),('''E V G =是两个图. 若V V ?',E E ?', 则称'G 是G
的子图（subgraph). 若'G 是G 的子图且V V =', 则称'
G 是G 的生成子图（spanning
subgraph). 设1V ?V , 以 1V 为顶点集, 以两端点全在1V 中的全体边为边集的G 的子图称
为G 的导出子图(induced subgraph), 记为][1V G .
在图3中，
定义1.8 图G 的连通分支(connected component) 是指其最大连通子图. 图G 的割点
(cutvertex) (割边 (cut-edge or bridge))是指一个顶点（一条边）且删除它会增加连通分支的数
目. 我们用v G -)(e G -来表示删除点v (边)e 所得到的子图.
在图4中，
下面来刻画割边.
定理1.9 一条边是割边当且仅当它不属于任何一个圈.
证明: 设e )(G E ∈,不妨设G 是连通的（为什么?）.
? 若e 位于某个圈中, 则不难证明e E -连通，这与e 是割边矛盾，故e 不属于
任何一个圈.
? 若e 不是割边, 则e E -连通. 设e 的两个顶点分别为21,v v . 由于e E -连通.
连通，故e E -中存在一条(21,v v )-路径，这条路径加上e 就构成了一个圈.
定义1.10 一个有向图（digraph ）D 是指一个二元组),(E V ，其中集合V 中的元素称
为顶点（或点,或端点, 或结点), 集合E 中元素为V 中元素组成的有序对，称为边或有向边.
有向图也可以用图形表示. 例如：
但要注意有向图中边),(b a 是有方向的，箭头必须从a 指向b . 有些概念对有向图或无向图
都适用; 有些概念对有向图和无向图而言是有差异的. 在习题中我们给出有向图中一些基本
概念的定义.
习 题
1. 证明：一条),(v u -通道都包含一条),(v u -路径.
2. (1) 如果简单图G 的每个顶点的度数为2，G 一定是圈吗？
(2) 证明：如果图G 中每一个点的度至少是2，则G 含有一个圈.
3. 给定下列各序列：
（1）（2,2,2,2,2）；
（2）（3,2,2,1,1）；
（3）（2,2,2,1,1）；
（4）（3,3,3,1,0）；
（5）（5,4,4,3,1）.
以上五组数中，那几组数可以构成简单图的度数序列?
4. 证明：含有n 个顶点和k 条边的图至少有k n -个连通分支.
5. 证明：如果一个图的所有顶点的度都为偶数(这样的图称为偶图)，则此图没有割边.
6. 对于含有n 个顶点的简单图，如果任意两个顶点都有边相连(即每个顶点的度为1-n )，则称此图为完全图(complete graph), 记为n K . 确定4K 是否包含以下情况(给出例子或证明不包含).
(1) 一个不是迹的通道.
(2) 一个不是路径的闭迹.
(3). 一个不是圈的闭迹.
7. 对于图G 和H ，如果存在两个双射θ：)()(H V G V →和)()(:H E G E →λ使得对于任意的)(),(G E u v e ∈=, )(),(v u θθ是)(e λ的两个端点, 则称G 和H 同构
(isomorphism), 记为H G ?. 一个简单图G 的补图（complement ）c G 也是一个简单图，其
顶点集为)(G V , 且)(),()(),(G E v u G E v u c ??∈.
(1) 证明：4P （4个顶点的路径）和其补图同构. 像这样和其补图同构的图称为自补的 (self-complementary).
(2) 证明：c
c H G H G ???.
(3) 证明简单图集合的同构关系时一种等价关系.
(4) 按同构关系给下面4个图分类.
第2节 树的性质
本节和下一节学习图论中最有用的概念之一——树. 作为图，树在数据存储、查询，通信，电网分析，化学等方面有着重要应用.
定义2.1 一个森林（forest ）是指一个无圈图. 一棵树（tree ）是指一个连通的森林. 度为1的顶点称为叶子（leaf ）. 若果一个图的生成子图是一棵树，则称该树是图的生成树 (spanning tree).
例2.2 给一所大学的所有学生编排学号，形成一颗树. 以0表示学校，以01, 02, 03,.... 表示学院, 以01, 02, 03...表示各个学院的班级，以001, 002, 003,....表示各班级的学生这结果如下图所示，注意树中的叶子表示一个学生.
下面给出树的定价刻画.
定理 2.3 对于n 个顶点的图G ，下面命题等价:
（1）G 是连通的且无圈.
(2) ?)(,G V v u ∈, G 中只有一条),(v u -路径且G 无环.
（3）G 有1-n 条边且无圈.
（4）G 是连通的且有1-n 条边.
证明：（1）?（2）. 由于G 是连通的，故?)(,G V v u ∈, G 中有一条),(v u -路径. 若G 中还有一条不同的),(v u -路径，则不难证明G 中有圈 (证明留作练习) ，与G 中无圈矛盾，所以G 中只有一条),(v u -路径. 无圈推出无环.
（2）?（3）. 上面证明已经指出：?)(,G V v u ∈, 若G 中只有一条),(v u -路径，则G 中无圈. 下面用归纳法证明G 有1-n 条边. 如果1=n ，结论是显然的 (由于G 无环)，下设对于顶点数小于n (2≥n )的图命题成立. 对于G 中任意一条边),(v u ，在图G 中删除此边得到图H . 由于G 中只有一条),(v u -路径，故H 不连通. 不难证明 H 有两个连
通分支且无圈，设这两个连通分支分别为1H 和2H . 由（1）?（2）知这两个连通分支中任意两顶点间只有一条路径，又由于1H 和2H 的顶点数都小于n ，由归纳假设知1-=i i n e (其中i i n e ,分别表示i H 的边和顶点数，2,1=i ). 又=n 1n +2n =1e +2e +1+1=e +1, 证毕.
（3）?（4）. 设k H H H ...,,21使G 的连通分支. 由 (1) ?(2) ?(3)知，对每个连通分支i H 都有1-=i i n e (其中i i n e ,分别表示i H 的边和顶点数, k i ,...,2,1=) . 故 ∑==k i i i e 1∑===k
i i i n 1k -，即k n e -=. 由于1-=n e ，故1=k ，即G 连通.
（4）?（1）. 若G 中有圈，则从各个圈中删除边. 直到G 中无圈. 又因为删除圈中的边不会破坏连通性 (也即圈中的边一定不是割边，见定理1.9)，故最后得到的图*
G 是
连通的无圈图且顶点数为n . 由于(1) ?(2) ?(3)，故*G 有1-n 条边. 所以*G G =且是无圈的.
我们在习题中给出树的其它的定价刻画，下面给出关于生成树的一个结果.
定理2.4. G 是连通的当且仅当它有生成树.
充分性是显然的，必要性的证明类似于定理2.3证明中的（4）?（1），故我们略去. 注意定理2.4给出了确定图G 是否连通的方法，我们将在下一节讨论检测G 是否有一个生成树的算法.
我们下面讨论树在计算机学科的一些应用，先给出根树的定义.
每一颗树都可以按下面的方式画出来 (例如图 ). 每一个顶点都有层次 (level)0, 1, 2,..., k. 存在的唯一的层次为0的顶点称为根 (root). 所有相邻的顶点相差一个层次, 且1+i 层次上的顶点正好与一个i 层次上的顶点相邻. 这样的树称为根树 (rooted tree ）. 显然指定一个顶点作为根后，每一颗树都可以认为是根数. k 称为树高 (height). 与顶点u 相邻且比u 层次低的顶点称为u 的孩子 (children), 比u 层次低且与u 有路径相连的顶点称为u 的后代(descendant). 如果一颗树的每个顶点有不多于m 个孩子，则称此树为m 元 (m -ary)树.如果每个顶点有0个或m 个孩子，则称此树为完全m 元树. 2元根树也称为二叉树 (binary tree). 下图给出了一颗高为3的二叉树.
当传输数据时，每一个字符被编码或被指定一个二进制串. 例如我们要传送σ
εγβα,,,,
这五个符号时就需要至少三位二进制串 (为什么？). 由于我们可能要处理一些很大的文件且计算机的储存空间有限，我们常常希望将字符编码成二进制串使得文件总长最小. 不妨设这五个字符在文件中出现得频率分别为51,...,a a ，则如果用三位二进制串传输这一数据集合需要
)...(3521a a a σβα+++位.
如果允许使用变长度的二进制串，则可能节省很多. 例如我们给上面5个字符分别编码如下：
010:;001:;01
:;00:;0:σεγβα 则传输这一数据集合需要
)(3)(254321a a a a a σεγβα++++位.
显然变长度的传输方式节省了传输位数，然而却出现了问题. 如果我们收到二进制串：001..... 则没有办法解码. 出现这样问题的原因很简单，是因为我们在编码过程中一个字符的二进制串是某个字符二进制串的前面部分. 例如上例中α的二进制串是β的前面部分等等. 因此我们分不清楚00是表示两个α还是一个β. 我们称这种情况不出现得编码为前缀码 (prefix code). 下面我们来介绍构造最优前缀编码的算法 (Huffman 1952).
Huffman 算法：最优前缀编码
输入：权值 (频率或概率) n a a a ,...,,21.
输出：前缀码 (一颗二叉树).
思想：权值小的字符 (或数据) 应该有较长的编码, 将权值小的数据置于二叉树的深层.
步骤：1.取权值最小的j i a a ,为叶子，做一个新顶点为这两个树叶的父亲且其权为j i a a + . 从所有的权中删去j i a a ,加上j i a a +.
2.重复1-n 次过程1 后就得到一颗二叉树.
3.从二叉树的树根出发，给左边的边标记0，右边的边标记1，则树叶的编码为从树根到树叶的路径上标记的字符串.
关于这一算法最优性的证明可参考[1]或[2] . 下面我们用一个例子说明求最优前缀编码的过程.
例2.5 在通信中， 0,1,2,3,4,5出现的频率如下：
0: 45% 1: 20% 2: 15% 3: 15% 4: 10% 5: 5%
求传输它们的最优前缀码.
解：按照Huffman 算法得到的二叉树如下图所示. 所以0,1,2,3,4,5的最优前缀编码分别为
0: 1 1: 011 2: 012 3: 001 4: 0001 5: 0000
按比例传输上述字符1000个需要的二进制数字个数为
1000（45%?1+20%?3+15%?3+15%?3+10%?4+5%?4）=2150个. 如果所有字符都用长为3的码字传输，则需要二进制数字3000个. 所以用最优前缀编码省
了850个二进制数字.
考虑搜索n 个数字列表中的某个数字. 最坏情况是，该数字处于列表的最后位置，则我们需要n 步找到它.下面我们用二叉搜索树储存这些数据，并证明通过这种方法我们搜索某个数的步骤将大大降低.
一颗二叉搜索树 (binary search tree) 是一颗给每一个顶点赋值了的二叉树, 且对每一个顶点如果它有孩子，那么它的左孩子和左孩子的后代的赋值比该顶点的赋值小；它的右孩子和右孩子的后代比该顶点的赋值大. 图2.1中给出了一个完全二叉搜索树. 各顶点的赋值为1, 2, ...,7. 例如要搜索7，先是和5比较，7大于5故而和5的右孩子比较，7又大于6，故在和7比较，这样用了3步就找到了. 如果按照列表1,2,3,... 7则需要7步.
假如已知一颗二叉搜索树，最坏情况下用多少步可以搜索到某个顶点取决于这颗二叉树的高度. 对于n 个顶点的二叉树，我们自然关心它的最小高度是多少.
定理2.6 n 个顶点的二叉树的最小高度为??1)1(log 2-+n .
定理的证明我们留作习题. 由此定理知对于n 个数据, 我们利用二叉搜索树搜索某个数据最多需要??)1(log 2+n 步. 这比按顺序查找列表中的项要好很多，因为
∞=+∞→)1(log lim
2
n n n .
习题.
1. 图G 中有两条),(v u -路径，则G 中含圈.
2. 图G 是树?G 连通且G 中每一条边都是割边
?在G 中任意添加一条以)(G V 中顶点为端点的边都构成一个圈.
3. 设G 是一颗树. 证明：
G 的顶点全部是奇数度当且仅当对所有的)(G E e ∈，e G -的两个连通分支都有奇数个顶点.
4. 设1G , 2G 是连通图G 的两个生成树并且)()(21G E G E e -∈, 则存在边)()(12G E G E e -∈*, 使得*+-e e G 1是G 的一颗生成树.
5. 用20个消息符号构成的集合，其中各个符号的频率分别为1,2,3,4,4,5, 6,7,7,9. 求传输这些消息符号的最优前缀编码，并画出编码树.
6. 考虑下列数据集合：2个A ，3个B ，5个C ，5个D.
（1）证明Huffman 算法可以产生不同高度的最优代码树.
（2）如何修改Huffman 算法使得其产生高度最小的最优代码树.
7. 证明定理2.6.
(1) 证明：树的第l 层最多有l
2个顶点.
(2) 证明公： )1(11 (11)
2≠--=+++++x x x x x x l l
. （3）证明：对n 个顶点且高度为l 的二叉树有121-≤+l n .
（4）证明：存在n 个顶点的二叉树且其高度为??1)1(log 2-+n (考虑完全二叉树).
（5）证明：n 个顶点的二叉树的最小高度为??1)1(log 2-+n
8. 假设在某二叉查找树中，有1到1000之间的一些数，现在要找出363这个数，下
列的节点序列中，哪一个是不可能检查的序列. （Cormen et al []）（1）2,252,401,398,330,344,397,363.
(2) 924,220,911,244,898,258,362,363
(3) 925,202,911,240,912,245,363
(4) 2,399,387,219,266,282,381,278,363
（5）925,278,347,621,299,392,358,363.
数字图像的基本概念
数字图像的基本概念： 分辨率： 指单位区域内包含的像素数目。 常见的分辨率: 1.图像分辨率 2.显示分辨率 3.输出分辨率 4.位分辨率 分辨率单位： 1.像素/英寸(通用),简写为 ppi 2.像素/厘米 常接触到的分辨率： 网页图像分辨率：72 ppi 96 ppi 报纸图像分辨率：120 ppi 150 ppi 打印图像分辨率：150 ppi 彩板印刷分辨率：300 ppi 常用的显示器分辨率： 1024*768 (水平方向上1024个像素，垂直方向上分布了768个像素) 800*600，640*480 常用打印机分辨率： 24针针式打印机180 ppi 喷墨打印机：300ppi 激光打印机：600ppi 色彩学基础知识： 图形的动态显示： 指在显视器上的图像图形以不同位置，不同大小，不同灰度的动态显示，多幅不同的图形图像序列的连续显示。 色彩的产生 可见光的种类： （1）直射光：发光物体产生的光（照明光，日光，） （2）透射光：直射光到透明或半透明物体上，通过物体投射的光 （3）反射光：直射光射到别的物体上产生的光 色彩属性： (1) 色相：红，橙，黄，绿，靛，蓝，紫（色彩成分） (2) 亮度：色彩的纯度（彩色光越大，亮度越大）
(3) 彩度：色彩的饱和度（饱和度越高，颜色越深） 色光三原色（色光三原色，三基色）：红，绿，蓝 色料三原色：黄，品红，青 颜色模式 Rgb模式：红，绿，蓝，组成，显示器采用 Cmyk模式：青，洋红，黄，黑组成，彩色印刷利用 Hsb模式：色相，饱和度，亮度组成 索引颜色模式：像素8位，256颜色 位图模式：黑白组成 Lab模式：ps标准模式， 双色调模式：八位的灰度模式 彩色与位数 彩色及其基本参数： （1）亮度：彩色光引起的视觉强度（明暗程度） （2）色相：光谱在不同波长的辐射在视觉上的表现（颜色类别） （3）饱和度：同色的饱和度越高，颜色越深（颜色深浅）彩色显示器分类： (1)crt显示器 (2)液晶显示器 彩色的位数 色彩深度：一幅图像的颜色数量 常用色彩深度：1位(2种颜色)，8位（256种颜色）16位（65536种颜色）还有24位和32位
第8章 图的基本概念
习题8 1. 给定下面两个图的集合表示，画出他们的图形表示。 >=<111,E V G , 其中},,,,{543211v v v v v V =，)},(),,(),,(),,(),,{(43415351211v v v v v v v v v v E = >=<222,E V D , 其中},,,,{543221v v v v v V =，},,,,,,,,,{43412552212><><><><><=v v v v v v v v v v E 注：2D 改为2G 解： 2. 先将下图中各图的顶点标定次序，然后写出各图的集合表示。 解：顶点标定如下： 图G1 图G2 V5 V5 （1） （2） （3）
(1) 其中},,,{43211v v v v V =，)},(),,(),,(),,(),,{(43324131211v v v v v v v v v v E = (2) 其中},,,,{543221v v v v v V =，)},(),,(),,(),,{(545452212v v v v v v v v E = (3) 其中},,,,{543231v v v v v V =， },,,,,,,,,,,{4534133251213><><><><><><=v v v v v v v v v v v v E 3. 写处下图中各图的度数列，对有向图还要写出出度列和入度列。 解：（1）4,2,2,2 （2）度数列：1,4,1 ,5,1；出度列：1，2，0，3，0；入度列：0，2，1，2，1 4. 设无向图中有6条边，3度与5度顶点各1各，其余的都是2度顶点，问该图有几个顶点？ 注：“各1各”改为“各1个”。 解：设该图有x 个顶点，3×1+5×1+2×(x-1-1)=6×2，x=4 5. 画以（1，2，2，3）为度数列的简单图和非简单图各一个。 解： （1） （2） （3） V5 （1） （2） 3 v 1v 23v
图像的基本概念
图像的基本概念 Keyword：数字图像处理图像通道格式 1、数字图像数字图像又称数码图像或数位图像，是二维图像用像素值的表示。在数学的领域，图像以矩阵的形式进行定义，在计算机的内存当中使用内存块来存储数字图像。以下就是数字图像在计算内存中的存储示意图： 2、像素像素又叫像元，是数字图像的基本元素。像素在图像中有两个基本属性，像素值和坐标。像素值对应着像素的灰度值或者颜色值，坐标对应着像素在数字图像中的位置。 3、几个重要的概念 （1）、图像坐标在解析几何当中，通常我使用左下角为原点建立二维笛卡尔坐标系，但是，在数字图像中，我们通常以图像的左上角为原点建立图像坐标系，对像素位置进行描述。 （2）、位宽在图像处理中我们经常遇到几位几位图像这一说，它的意思是说，一个像素我们使用多少个比特位进行描述。比如，灰度图像经常使用8位进行存储，那么它的每一个像素在内存中对应着8个比特位。 （3）、通道又叫颜色通道，表明一个像素对应着多少个像素值。比如，8位灰度图像，就是一（单）通道图像，它的每一个像素对应着一个0-255的灰度值；24位真彩图像，就是3通道图像，它的每一个像素需要（R,G,B）三个颜色值进行描述。
4、常见的数字图像文件 （1）、BMP是英文Bitmap（位图）的简写，它是Windows操作系统中的标准图像文件格式。 （2）、GIF是英文Graphics Interchange Format（图形交换格式）的缩写。是一种常见的网络图片格式。 （3）、JPEG也是常见的一种图像格式，它由联合照片专家组（Joint Photographic Experts Group）开发并以命名。JPEG文件的扩展名为.jpg或.jpeg。 （4）、TIFF（Tag Image File Format）是Mac中广泛使用的图像格式，它由Aldus和微软联合开发，最初是出于跨平台存储扫描图像的需要而设计的。 （5）、PNG是目前保证最不失真的格式，它汲取了GIF和JPG二者的优点，存贮形式丰富，兼有GIF和JPG的色彩模式 （6）、其他SWF、PSD、SVG、PCX、DXF、WMF等。 关注微信公众号：图像大师，更多干货。 扫一扫：
离散数学结构 第14章 图的基本概念
第十四章图的基本概念 14.1 图 (2) 一．无向图与有向图 (2) 1．无序积与多重集 (2) 2．无向图与有向图的定义及表示法 (2) 二．简单图与多重图 (4) 1．顶点的度数 (5) 2．握手定理 (5) 四．图的同构 (8) 1．两图同构的定义 (8) 2．图之间的同构关系是等价关系 (8) 五．完全图与正则图 (9) 1．完全图 (9) 2．正则图 (9) 六．子图与补图 (9) 1．子图 (9) 2．补图与自补图 (12) 14.2 通路与回路 (15) 一．通路与回路的定义 (15) 二. n阶图中通路与回路的性质 (17) 14.3 图的连通性 (17) 一、无向图的连通性 (17) 二、无向图中顶点之间的线程线及距离 (18) 三、无向图的连通度 (18) 四、有向图的连通性及其分类 (20) 五、扩大路径法及极大路径 (21) 六、二部图及判别定理 (22) 14.4 图的矩阵表示 (26) 一、无向图与有向图的关联矩阵 (26) 二、有向图的邻接矩阵 (27) 三、有向图的可达矩阵 (29) 典型习题 (29) 14.5 图的运算 (33)
14.1 图 主要内容 无向图与有向图。 简单图与多重图。 顶点的度数与握手定理。 图的同构。 完全图与正则图。 子图与补图。 学习要求 熟练掌握握手定理及其推论的内容及其应用。 掌握图同构的概念。 加深对简单图、完全图、正则图、子图、补图等概念的理解。 一．无向图与有向图 1．无序积与多重集 设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B. 为方便起见，将无序积中的无序对{a,b}记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A. 元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1. 2．无向图与有向图的定义及表示法 定义14.1一个无向图是一个有序的二元组
离散数学第七章图的基本概念知识点总结
图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G=
第一章 图的基本概念
第一章图 教学安排的说明 章节题目：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算 学时分配：共2课时 本章教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），会进行图的运算，会用图论的方法描述一些简单的实际问题． 其它：由于离散数学中已介绍过相关内容，本章以复习为主
课 堂 教 学 方 案 课程名称：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算 授课时数：2学时 授课类型：理论课 教学方法与手段：讲授法 教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈）， 会进行图的运算，会用图论的方法描述一些简单的实际问题． 教学重点、难点： （1） 理解图、简单图、子图以及图的同构等概念，并能够用图表示简单 的现实问题； （2） 掌握途径、链和道路的概念及其区别； （3） 理解图的连通性概念； （4） 掌握图的四种运算。 教学内容： 第一章 图 §1.1图的概念 引例 例1.下面是五城市之间的航线图，若两城市间有航线，则连线，否则不连如图1.1（a ）：由图中可知，北京与广州间没有航线，而大连到上海间有航线 北京 大连 上海 广州 昆明 9 6 4 8 10 （a ） （b ） 图1.1
例2.数4，6，8，10，9五个数，若有公因子则连线，，否则不连，如上图1.1(b) 通常人们认为，过去我们所学的微积分是属于连续数学，而本章所要讨论的图论是离散数学的重要分支． 首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系．因此在图论中，顶点之间的距离、弯曲、以及顶点间的位置关系都是无关紧要的，即图的概念是抽象化的,它是数学中经常采用的抽象直观思维方法的典型代表． 下面给出图作为代数结构的一个定义。 图的定义:一个图是一个三元组〈)(G V ，)(G E ，G ?〉，其中)(G V 是一个非空的点集合，)(G E 是有限的边集合，G ?是从边集合E 到点集合V 中的有序偶或无序偶的映射。 例3 图G =〈)(G V ，)(G E ，G ?〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ， ),()(1b a e G =?，),()(2c a e G =?，),()(3d b e G =?，),()(4c b e G =?，),()(5c d e G =?，),()(6d a e G =?。
07正弦交流电的基本概念
《电工基础》 第七章 弦交流电的基本概念 1. 2. 相位。 3. 等概念。 了解正弦交流电的产生。 掌握表征正弦交流电的三要素：振幅、角频率、初 理解交流电的周期、频率、有效值、相位与相位差 4. 图、相量图等）。 掌握正弦交流电流、电压的表示法 （解析式、波形 1. 理解相位差的概念。 2. 掌握正弦量的相量图。 序号 内 容 学时 1 第一节交流电的产生 1 2 第二节 表征交流电的物理量 1 3 第三节 交流电的表示法 2 4 实验7.1用示波器观察交流电的波形 1 5 本章小结与习题 1 6 本章总学时 6 第一节交流电的产生 一、 交流电的产生 如果电流的大小及方向都随时间做周期性变化，则称之为 交流电。
电动势的初相位或初相，单位为弧度rad 或度（），它表示初始时刻（t = 0时）正弦交流电所 处的电角度。 振幅、角频率、初相这三个参数叫做正弦交流电的 三要素。任何正弦量都具备三要素。 三、 交流发电机简介 发电机的基本组成部分是磁极和线圈 （线圈匝数很多，嵌在硅钢片制成的铁心上， 通常 叫电枢）。电枢转动、而磁极不动的发电机，叫做 旋转电枢式 发电机。磁极转动、而电枢不 动，线圈依然切割磁感线，电枢中同样会产生感应电动势，这种发电机叫做 旋转磁极式 发 电机。不论哪种发电机，转动的部分都叫 转子，不动的部分都叫 定子。 旋转电枢式发电机，转子产生的电流必须经过裸露着的滑环和电刷引到外电路， 压很高，就容易发生火花放电，有可能烧毁电机。这种发电机提供的电压一般不超过 旋转磁极式发电机克服了上述缺点，能够提供几千伏到几十千伏的电压，输出功率可达几 十万千瓦。所以，大型发电机都是旋转磁极式的。 发电机的转子是由蒸汽机、水轮机或其他动力机带动的。动力机将机械能传递给发电 札发电机把机械能转化为电能传送给外电路。 第二节 表征交流电的物理量 、周期与频率 正弦交流电完成一次循环变化所用的时间叫做 周期，用字母T 表示，单位为秒 然正弦交流电流或电压相邻的两个最大值 期，由三角函数知识可知 交流电周期的倒数叫做 频率（用符号f 表示），即 f 丄 T 二、 正弦交流电 大小及方向均随时间按正弦规律做周期性变化的电流、电压、电动势叫做 正弦交流电 流、电压、电动势，在某一时刻t 的瞬时值可用三角函数式（解析式）来表示，即 i （t ） = I m sin （ t u （t ） = U m sin （ t e （t ） = E m sin （ t 式中，I m 、U m 、E m 分别叫做交流电流、电压、电动势的 的单位为安培（A ），电压和电动势的单位为伏特 （V ）； 秒（rad/s ），它表征正弦交流电流每秒内变化的电角度； io ) U0) eo ) 振幅（也叫做峰值或最大值），电流 叫做交 流电的角频率，单位为弧度/ eo 分别叫做电 流、电压、 iO 、 uO 、 如果电 500 V 。 （S ）。显 （或相邻的两个最小值 ）之间的时间间隔即为周