当前位置：文档之家 › 自考离散数学第5章

自考离散数学第5章

  • 格式：ppt
  • 大小：1.98 MB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

离散数学 (5)

离散数学 (5)


15
一阶逻辑中命题符号化( 一阶逻辑中命题符号化(续)
例3 在一阶逻辑中将下面命题符号化 (1) 正数都大于负数 (2) 有的无理数大于有的有理数 注意: 题目中没给个体域, 解 注意 题目中没给个体域 一律用全总个体域 (1) 令F(x): x为正数 G(y): y为负数 L(x,y): x>y 为正数, 为负数, 为正数 为负数 →y(G(y)→L(x,y))) 或 x(F(x)→ → → xy(F(x)∧G(y)→L(x,y)) ∧ → 两者等值 (2) 令F(x): x是无理数 G(y): y是有理数 是无理数, 是有理数, 是无理数 是有理数 L(x,y):x>y : ∧y(G(y)∧L(x,y))) x(F(x)∧ ∧ ∧ 或 xy(F(x)∧G(y)∧L(x,y)) ∧ ∧ 两者等值
6
谓词: 谓词 表示个体词的性质或相互之间关系的词 谓词常项: 谓词常项:表示具体性质或关系的谓词 F: …是人,F(a):a是人 是人, 是人 : 是人 是自然数, G: …是自然数, F(2):2是自然数 是自然数 : 是自然数 谓词变项: 谓词变项:表示抽象的或泛指的谓词 F: …具有性质 ,F(x):x具有性质 具有性质F, 具有性质具有性质 : 具有性质 元数: 元数:谓词中所包含的个体变项个数 一元谓词: 一元谓词 表示事物的性质 多元谓词(n元谓词 ≥ 元谓词, 多元谓词 元谓词 n≥2): 表示个体词之间的关系 有关系L, 如 L(x,y): x与y有关系 , L(x,y): x比y高2厘米 : 与 有关系 : 比 高 厘米 注意:多元谓词中, 注意:多元谓词中,个体变项的顺序不能随意改动
9
例1(续) 续
(2) 2 是无理数仅当 3 是有理数 2 在命题逻辑中, 是有理数. 在命题逻辑中 设 p: 2 是无理数,q: 33 : 2是无理数, : 是有理数 符号化为 q→p, 这是假命题 → 在一阶逻辑中, x是无理数 是无理数, x是有理 在一阶逻辑中, 设F(x): x是无理数, G(x): x是有理 数符号化为 F ( ( 22 ) → G (3 )3 ) F ) → G( (3) 如果 如果2>3,则3<4 , 在命题逻辑中, 在命题逻辑中 设 p:2>3,q:3<4. : , : 符号化为 p→q, 这是真命题 → 在一阶逻辑中, 在一阶逻辑中 设 F(x,y):x>y,G(x,y):x<y, : , : 符号化为 F(2,3)→G(3,4) →
《离散数学》第五章

《离散数学》第五章


⊕4b）⊕4c=
a
c)， 满足结合律。 ⊕4(b ⊕4c)，即⊕4满足结合律。
0是单位元，0的逆元是 ，1和3互为逆元，2的逆 是单位元， 的逆元是 的逆元是0， 和 互为逆元 互为逆元， 的逆 是单位元 元是2。 是一个群。 元是 。 <Z4； 4>是一个群。 ⊕ 是一个群
14
定义5-8:如果群 如果群<G; * >的运算 是可交换的，则称该群为 的运算*是可交换的 定义 的运算 是可交换的，
5
三、 子半群和子独异点
定义5-5 定义
<S； >的子代数，则称<T； >是<S； >的子半群。 ； 的子代数，则称 ； 是 ； 的子半群。 的子代数 的子半群
∗
设<S； >是一个半群 ，若 <T； ； 是一个半群 ； ∗
∗
例6
= {2n | n ∈ N} N3 = {3n | n ∈ N}, N4 = {4n | n ∈ N}, L
交换群或阿贝尔群。 交换群或阿贝尔群。
15
二、循环群
1．群中元素的幂 对于任意a∈ ， 对于任意 ∈G， a0=e,
anƮ=e, ( a−1)n+1 = (a−1)n ∗ a−1 (n=0,1,2,…) （*） ） 引进记号 a−n = (a−1)n = a−1 ∗ a−1 ∗ ⋅ ⋅ ⋅ ∗ a−1 ( n个a-1 ) 个 因此（ 因此（ ）式可表示为 (a −1 )0 = e, a−n−1 = a−n * a−1 对于任意整数
1
5.1 半群和独异点 一、半群 半群 定义5-1 定义
二元运算， 二元运算，如果 是半群。 是半群。∗ > < s; 是一个非空集合， 设S是一个非空集合， 是S上的一个 是一个非空集合 上的一个 是可 结 合 的 , 则 称 代 数 系 统
离散数学(刘任任版)第5章答案.ppt

离散数学(刘任任版)第5章答案.ppt


证明：设 e v1v2 ，G中含e的闭链为 。 v v v v 若E E不是回路，则必有 。 1 2 l 1 v v ij l i j 2 （因为回路定义是 ：没有重复点） 从E中去掉 ，得到 v vj i 1 v v v v v v 仍为闭链。如此下去，就可得到含 的回路。 1 2 i j 1 l 1
e v1v2
) 2,则G中必 18、求证:对于图G(p,q),若 (G 含回路.
) 2 证明：．∵ (G v(G )，设v1与v0邻接。 ∴ G中无悬挂点。任取 v 0 v v v v 如此下去，可得G中的一条链 0 1 2 p 又因G是有限图,由此可得一条闭链，由第１７题的 证明过程可知，故此链上必有回路。
证明：令
p 3 ,q C 1
2 2
。作如下 G( p, q)，故G不连通。
21、（1）证明：若 Ｇ(p,q) 是简单图， 且 ,则G 连通. ( G ) p / 2 1
证明：（1）设 。 ( G ) p / 2 1 若G不连通，则G的顶点可划分成两个集合V1 , V 2 ，使得V1与 V2中的顶点互不邻接。 p | V | | V | 不妨设 。 由G是简单图知， 1 2，则| V1 |
vi
d(v) 0
v v V ( G ), i j i, j
d ( v d ( vj ) i )
。
10、求证:在图G（p,p+1）中,至少有一个顶 点v,满足d(v) ≥3.
)，均有d(v) 2 证明：若对任意vv(G ，则有
2 (p 1 ) 2 q d ( v 2 p i)
从而G-v至少有(P-1)-k条边。故G至少有P-1条边。
16.(2)设G（p,q）是连通图，求证:若q > p – 1,则G 中必含回路;
离散数学课件第5章(1)

离散数学课件第5章(1)


Chapter 5
graph theory
CHAPTER 5 Graphs
5.1 Introduction to Graphs 图的概述
5.2 Graph Terminology 图的术语
5.3 Representing Graphs and Graph Isomorphism图的表示和图的同构
b d
c
Solution:
12 2021/5/30
0 0 1 0
AG
1 0
0 0
0 0
0
0
1
1
1
0
5.3 Representing Graphs and Graph Isomorphism
Question:
1. What is the sum of the entries in a row of the adjacency matrix for an undirected graph?
Representing Graphs 图的表 示
Methods for representing graphs: Adjacency lists 邻接表 -- lists that specify all the vertices that are adjacent to each vertex该表规定与图的每个顶点 邻接的顶点 Adjacency matrice 邻接矩阵 Incidence matrices 关联矩阵
5.3 Representing Graphs and Graph Isomorphism
〖Example 2〗 What is the adjacency matrix AG for the following graph G based on the order of vertices a, b, c, d ?
离散数学课件(第5章)

离散数学课件(第5章)


的概率。
02
条件概率的性质
条件概率具有可交换性、可结合性、可分解性和归一性等性质。
03
条件概率的计算公式
条件概率的计算公式为P(A|B)=P(A∩B)/P(B)，其中P(A∩B)表示事件A
和事件B同时发生的概率，P(B)表示事件B发生的概率。
独立性
事件的独立性
如果两个事件之间没有相互影响， 即一个事件的发生不影响另一个 事件的发生，则这两个事件是独
要点二
详细描述
关系的并运算是指两个关系的并集，表示两个关系中都存 在的关联；关系的交运算是指两个关系的交集，表示同时 存在于两个关系的关联；关系的差运算是指两个关系的差 集，表示存在于一个关系但不存在的关联；关系的逆运算 是指一个关系的逆关系，表示元素之间的关联方向相反。 这些运算可以用来对关系进行操作和变换，以得到所需的 关系。
路径与回路
总结词
路径是指一系列节点和边的有序集合，而回 路是指路径中至少有一条边是有向的。
详细描述
路径是指从图中的一个节点出发，经过一系 列的边和节点，最后回到起始节点或有终止 节点的一条路径。在路径中，所有的边都是 无向的。而回路则是指至少有一条边是有向 的路径，即起点和终点相同的路径。在图论 中，回路的概念非常重要，因为许多问题可
立的。
独立性的性质
独立性具有传递性、对称性和可 分解性等性质。
独立性的计算公式
如果事件A和事件B是独立的，则 P(A∩B)=P(A)P(B)，即两个独立 事件的概率乘积等于它们各自的
概率。
05
离散随机过程
随机变量
定义
分类
随机变量是定义在样本空间上的可测函数 ，它将样本点映射到实数轴上。
离散随机变量和连续随机变量。
自考离散数学第5章

自考离散数学第5章

定义5.1.2 设G=<V,E>是一个图，结点v（v V）关联的边数称作该结 点的度数，记为d(v)(或deg(v))。若v有自环，则使d（v）增加2.
deg(v)=1的结点称为悬挂点，度数为奇（偶）数的结点称为奇（偶）结 点。
定理5.1.1 每个图中，结点度数总和等于边数的两倍。
deg(v) 2 | E | vV
为邻接点。 关联于同一结点的两条边称为邻接边。 在图G=<V,E>中，若V≠ᴓ，但E=ᴓ，称这个图为零图，当|V|=n，E=ᴓ时，
称为n阶零图。
第三页，编辑于星期三：八点 四十八分。
5.1 图的基本概念
连接于同一结点间的多条边称为平行边。如果有向边要求方向相同，含 有平行边的任何一个图称为多重图。不含多重边和环的图称为简单图。
Pij= 1,若vi与vj之间至少存在一条路径，
0,若vi与vj之间不存在路径可由图G的邻接矩
阵A得到路径矩阵P，即设Bn=A+A2+...An,再从Bn中将不为零的元素改换 为1.为零的元素不变，这个改换的矩阵，即为路径矩阵。
例2
第十六页，编辑于星期三：八点 四十八分。
5.3 图的矩阵表示
第十七页，编辑于星期三：八点 四十八分。
若一条路中，所有边e1,e2,...,en均不相同，称作迹。若一条路中所有结 点v0,v1,...,vn均不相同（当然边也不相同），则称此路为初级路。若回 路中除v0=vn外其余结点各不相同，所以边也各不相同，则称此回路为 初级回路或圈。有边重复出现的路称为复杂路。有边重复出现的回路称 为复杂回路。
它们分别称为图G的最大度和最小度。
第七页，编辑于星期三：八点 四十八分。
5.1 图的基本概念
离散数学 第五章的课件

离散数学 第五章的课件


xF(x,y,z)yG(x,y,z)
tF(t,y,z)yG(x,y,z) tF(t,y,z)wG(x,w,z)
个体变项符号，其余部分不 变
（换名规则） （换名规则）
或者
xF(x,y,z)yG(x,y,z) xF(x,t,z)yG(x,y,z) xF(x,t,z)yG(w,y,z) （代替规则） （代替规则）
10
实例
例5.4 给定解释I如下： （a）个体域 D＝{2,3}. （b）D中特定元素 a =2 （c）D上的特定函数 f (x) ： f (2) =3, f (3)=2 . （d）D上的特定谓词 F (x) ： F (2)=0, F (3)=1; G (x,y)： G (2,2)= G(2,3)= G(3,2)=1，G(3,3)=0； L (x,y)： L (2,2)= L (3,3)=1， L (2,3)= L(3,2)=0； 求下列各式在I下的真值。 (2) x(F(f(x))∧G(x,f(x))) (F(f(2))∧G(2,f(2)))∨(F(f(3))∧G(3,f(3))) (F(3)∧G(2,3))∨(F(2)∧G(3,2)) (1∧1)∨(0∧1) 1
注意:(3)(4)说明量词的顺序不能随便颠倒
13
实例
例5.5 证明下列等值式。 (1) x(M(x)∧F(x)) x(M(x)→F(x)) (2) x(F(x)→G(x)) x(F(x)∧G(x)) (3) xy(F(x)∧G(y)→H(x,y)) xy(F(x)∧G(y)∧H(x,y)) (4) xy(F(x)∧G(y)∧L(x,y)) xy(F(x)∧G(y)→L(x,y))
或
x(F(x,y) yG(x,y,z)) x(F(x,y) tG(x,t,z))
离散数学第五章习题答案

离散数学第五章习题答案

离散数学第五章习题答案题目1: 定义一个关系R在集合A上，如果对于所有的a, b, c属于A，满足以下条件：- 如果(a, b)属于R，则(b, a)属于R。

- 如果(a, b)属于R且(b, c)属于R，则(a, c)属于R。

证明R是传递的。

答案：根据题目给出的条件，R是对称的和传递的。

首先，对称性意味着如果(a, b)属于R，那么(b, a)也必须属于R。

其次，传递性意味着如果(a, b)和(b, c)都属于R，那么(a, c)也必须属于R。

结合这两个性质，我们可以得出结论：对于任意的a, b, c属于A，如果(a, b)和(b, c)都属于R，那么(a, c)也属于R，从而证明了R的传递性。

题目2: 给定一个函数f: A → B，如果对于A中的每个元素a，都有唯一的b属于B使得f(a) = b，那么称f为单射（或一一映射）。

证明如果函数f是单射，那么它的逆函数f^-1也是单射。

答案：要证明f^-1是单射，我们需要证明对于B中的任意两个元素b1和b2，如果f^-1(b1) = f^-1(b2)，则b1 = b2。

假设f^-1(b1) = a且f^-1(b2) = a'，其中a, a'属于A。

由于f是单射，我们知道f(a) = b1且f(a') = b2。

根据f^-1的定义，我们有b1 = f(a) = f(a') = b2。

因此，如果f^-1(b1) = f^-1(b2)，则b1必须等于b2，这证明了f^-1是单射。

题目3: 证明一个函数f: A → B是满射（或到上映射）当且仅当对于B中的每个元素b，都存在A中的元素a使得f(a) = b。

答案：首先，我们证明如果f是满射，那么对于B中的每个元素b，都存在A 中的元素a使得f(a) = b。

假设f是满射，这意味着B中的每个元素都是A中某个元素的像。

因此，对于B中的任意元素b，我们可以找到一个a属于A，使得f(a) = b。

离散数学导论(盘) 教学课件 作者 王元元 张桂芸 第五章演示文稿-支持高清浏览

离散数学导论(盘) 教学课件 作者 王元元 张桂芸 第五章演示文稿-支持高清浏览


第五章 关 系5.2 关系
5.2.4 关系特性闭包
定理5.17
设R是集合A上任一二元关系，那么 1 如果R是自反的，那么s(R)和t(R)都是自反的。 2 如果R是对称的，那么r(R)和t(R)都是对称的。 3 如果R是传递的，那么r(R)是传递的。
第五章 关
系2. 关系
4.
关系特性闭包
定理5.18
4 称A为R的前域，B为R的陪域。
第五章 关 系5.2 关系
5.2.2 关系的基本运算
定义5.6
称关系R和S相等，如果R与S有相同的
前域和陪域，并且 x y(xRy xSy)
定义5.7
设R是A到B的关系，R的逆关系或逆 （converse
是B到A的关系，记为R~， 规定为 R~= ｛<y,x> xRy｝
如果R为A上的自反、对称、传递的二元 关系。
第五章 关
系3. 等价关系
1.
等价关系
定义5.12
设R为集合A上的等价关系。对每一a A，
a的等价类（equivalent class），记为[a]R
（或简单地记为[a]），指下列集合
[a]R=｛x x A∧xRa｝ a称为[a]R的代表元素。
第五章 关
特性之一，则R1 R2仍有此性质。 2 自反、反自反、对称性对并运算封闭。 3 反自反、对称、反对称性对差运算封闭。 4 对称性对补运算封闭。 5 五大特性对求逆运算均封闭。 6 自反性对合成运算封闭，其他四大特性对合成运算
均不封闭。
第五章 关 系5.2 关系
5.2.4 关系特性闭包
定义5.10
设R是集合A上二元关系，称R "为R的自反闭包 （对称闭包，传递闭包），如果R"满足： （1）R"是自反（对称的，传递的）。 （2）R R"。 （3）对任意A上关系R"" ，若R""满足（1）和（2）
离散数学第五版第五章(耿素云、屈婉玲、张立昂编著)

离散数学第五版第五章(耿素云、屈婉玲、张立昂编著)

称+(G)，+(G)，－(G)，－(G)分别为G的最大出度、 最小出度、最大入度和最小入度。
12
5.1 无向图及有向图
五、握手定理(定理5.1-5.2)
设G=<V,E>为任意无向图，V={1,2,……,n}，|E|=m，则
n
d ( i ) = 2 m
i =1
设D=<V,E>为任意有向图，V={1,2,……,n}，|E|=m，则
20
5.1 无向图及有向图
例5：下列图中那些图具有子图、真子图、生成子图的
关系？
e4 2
1 e5
e1 3
e3 4 e2
(1)
2 e4
1
e5
(2)
e4 1 2
e1 3
e3 4
(3)
1 e1
e3
2
e2 3
1 e1
e3
2
3
1 e1
2
e4
(4)
(5)
(6)
21
5.1 无向图及有向图
23
5.1 无向图及有向图
例3： (1)画出4阶3条边的所有非同构的无向简单图。 (2)画出3阶2条边的所有非同构的有向简单图。
24
5.1 无向图及有向图
例4：下列图中那些图互为同构？
e a
b
d
c
1
4
5
2
3
(1)
(2)
(3)
(4)
(5)
（6）
25
第五章 图的基本概念 5.1 无向图及有向图 5.2 通路、回路、图的连通性 5.3 图的矩阵表示 5.4 最短路径及关键路径
十一、补图的定义（定义5.9）
离散数学课件(第5章)

离散数学课件(第5章)


第五章：代数结构
§5.1 代数系统的引入 1、运算 【定义5.1.1】 设A是非空集合，一个从An到B的 映射,称为集合A上的n元运算。简称为n元运算。 如果B A，则称该n元运算是封闭的。 在定义5.1中，当n=1时，f称为集合A上的一 元运算；当n=2时，f称为集合A上的二元运算。 在讨论抽象运算时，“运算”常记为“*”、 “∘”等。设*是二元运算，如果a与b运算得到c， 记作a*b=c；若*是一元运算，a的运算结果记 作*a或*(a)。
第五章：代数结构
4.吸收律 【定义5.2.4】 设*和∘是非空集合A上的两个可交换的二元运算， 如果对于任意a,bA，有 a*(a∘b)=a ；a∘(a*b)=a 则称运算∗和运算∘满足吸收律。 【例5.7】设N为自然数集合，*和∘是集合N上的二元运算，定义 为： aN，bN a*b=max(a,b)， a∘b=min(a,b) 验证运算*和∘适合吸收律。 解：aN，bN 若a＞b，a*(a∘b)=a*min(a,b)=a*b=max(a,b)=a 若a＜b，a*(a∘b)=a*min(a,b)=a*a=max(a,a)=a 若a＝b，a*(a∘b)=a*min(a,b)=a*a=max(a,a)=a 即 a*(a∘b)=a 同理可证a∘(a*b)=a ∘适合吸收律。 因此运算*和
河南理工大学电子教案
《离散数学》教案
计算机科学与技术学院
课程学时：64 主 讲：宋 成
第三篇：代数系统
本篇用代数方法来研究数学结构，故 又叫代数结构，它将用抽象的方法来研 究集合上的关系和运算。 代数的概念和方法已经渗透到计算 机科学的许多分支中，它对程序理论， 数据结构，编码理论的研究和逻辑电路 的设计已具有理论和实践的指导意义 本篇讨论一些典型的代数系统及其 性质。

离散数学第五章

第五章函数Function函数在数学、应用数学等许多领域，尤其计算机科学领域有着极其重要的作用。

函数的思想、概念和应用无处不在，无时不在。

它主要是研究变量之间的关系和规律。

函数的划分有很多种。

有线性与非线性之分、连续与离散之分。

例如，kx x f y ==)( 2211)(x c x c x g y +== bx ce x h y ==)(5.1 函数假定A ，B 是两个非空集合，f : A→B ，称f 为A 到B 上的函数，对每个a ∈A , 有唯一的f (a)∈B, 记做b = f(a)。

函数也叫映射mappings 或变换transformations （错误）a 叫做函数f 的自变量argument ，b 被称为因变量，b=f (a)叫做函数的值value ，也叫a 的像。

例1. A ＝{1,2,3,4}, B={a,b,c,d},c d a a B A f →→→→→4,3,2,1,:，则 f 是一个函数。

也可以简单记为，f ={(1,a), (2,a), (3,d), (4,c)}另外,ca b a A B g →→→→→4,2,1,1,: g={(1,a), (1,b), (2,a), (4,c)}因为对于1来说，1∈A , 不是唯一的f (1)∈B 与之相对应, f (1)=a, 并且f (1)=b, 因此g 就不是一个函数。

例2．f ：Z→Z ，f (a)=⎩⎨⎧是奇数是偶数a if a if 1f 是函数。

例3． 恒等函数1A (a)=a 是函数。

正如，我们在第四章里表述的，函数 f : A→B ，b=f(a), 是一个特殊的二元关系，我们知道，由函数f 可以确定一个关系f R ，简单地，可以表示为(a,b)∈f R ，或 a f R b 。

关系fR 的特征函数为 ⎩⎨⎧==否则0)(1),(a f b b a R f 或者简记为⎩⎨⎧==否则0)(1),(a f b b a f 因此，这样一来，我们以前所讨论的有关集合或关系的运算和性质对于函数来说，就可以完全适用。

离散数学课件-第5章-5、6

哈密顿通路是一个访问图G中每个顶点次数有且仅有一次的通路
A Hamilton circuit (or Hamilton cycle) is a cycle which visits every vertex exactly once, except for the first vertex, which is also visited at the end of the cycle.
v2
ቤተ መጻሕፍቲ ባይዱ
v7 v6
v1
v3
v5
v8
v4 v9
依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的边，则此顶点亦 可去也。 b、去某边后不能造成图形的不连通。
v2
v6
v7
v1
v3
1
v5
v8
v4
v9
(1)先去掉(v2,v4)
依序去掉相连的边但必须注意下列两条件： a、如果某边去掉后会导致某点无连通的 边，则此顶点亦可去。 b、去某边后不能造成图形的不连通。
23
2013-1-11
A directed multigraph having no isolated vertices has an Euler path but not an Euler circuit if and only if 一个没有孤立顶点的有向多重图含有欧拉通路但不含欧拉 回路的充要条件是： -- the graph is weakly connected 弱连通的 -- the in-degree and out-degree of each vertex are equal for all but two vertices, one that has in-degree 1 larger than its out-degree and the other that has outdegree 1 larger than its in-degree. 除去两个顶点外每个顶点的出度和入度相等，其中 一个顶点的出度比入度大1，另一个顶点的入度比出度 大1.

自考 离散数学目录

离散数学
第1章命题演算
1.1 命题概念
1.2 复合命题与联结词
1.3 命题公式与真值表
1.4 等价变换与蕴含式
1.5 最小联结词组与范式
1.6 推理理论
第2章谓词演算
2.1 谓词的概念与表示
2.2 量词与合式公式
2.3 谓词演算的等价式与蕴含式2.4 前束范式
2.5 谓词演算的推理理论
第3章集合与函数
3.1 集合的基本概念
3.2 集合的运算
3.3 笛卡尔积与关系
3.4 关系的表示与关系性质
3.5 关系运算与闭包
3.6 相容关系与覆盖
3.7 等价关系与划分
3.8 序关系
3.9 函数的概念
3.10 复合函数与逆函数
第4章代数结构
4.1 代数系统
4.2 半群与独异点
4.3 群与子群
4.4 环与域
4.5 格与子格
4.6 分配格与有补格
4.7 布尔代数
第5章图论
5.1 图的基本概念
5.2 路与回路图的连通性5.3 图的矩阵表示
5.4 欧拉图与汉密尔顿图5.5 平面图
5.6 树及应用
参考书目
离散数学自学考试大纲
出版前言
一、课程的性质及其设置目的和要求
二、课程内容与考核目标
第1章命题演算
第2章谓词演算
第3章集合与函数
第4章代数结构
第5章图论
三、有关说明与实施要求
附录题型举例
后记。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

时，称为n阶零图。
5.1 图的基本概念
连接于同一结点间的多条边称为平行边。如果有向边要求方向相同，
含有平行边的任何一个图称为多重图。不含多重边和环的图称为简单 图。
定义5.1.2 设G=<V,E>是一个图，结点v（v V）关联的边数称作该结
点的度数，记为d(v)(或deg(v))。若v有自环，则使d（v）增加2.
5.4 欧拉图与汉密尔顿图



5.4 欧拉图与汉密尔顿图



5.5 平面图
定义5.5.1 若一个图能画在平面上，使它的边互不相交（除在结点处），
则称该图为平面图。画出的没有边交叉出现的图G，亦称为G的一个平 面嵌入。
K3,3与K5是非平面图。 n点完全图Kn，当n≦4，Kn是平面图。当n≧5时，Kn是非平面图。 定义5.5.2 设G是一个连通平面图（G的某个平面嵌入），G的边将G所
式n-m+r=2。


定理5.5.2 设连通平面图G，共有n个结点，m条边，r个面，则欧拉公 例:证明当每个结点的度数大于等于 3时，不存在有7条边的简单连通图。
定理5.5.3 设G是一个有v个结点e条边的连通简单平面图，若v≧3,则
e≦3v-6
例：判定K5不是平面图。
5.6 树及应用
5.3 图的矩阵表示
定义5.3.2 设G是n个结点，无多重边的图，n×n矩阵称为路径矩阵（可
达性矩阵），记为P(G)=(Pij),其中

Pij=
1,若vi与vj之间至少存在一条路径，

0, 若 vi 与 vj 之间不存在路径可由图 G 的邻接 矩阵A得到路径矩阵P，即设Bn=A+A2+...An,再从Bn中将不为零的元素 改换为1.为零的元素不变，这个改换的矩阵，即为路径矩阵。
例2
5.3 图的矩阵表示
5.4 欧拉图与汉密尔顿图

哥尼斯堡七桥问题


定义5.4.1 给定无孤立结点图G，若存在一条路，经过图中每边一次且
仅一次，该条路称为欧拉路；若存在一条回路，经过图中每边一次且 仅一次，该回路称为欧拉回路。存在欧拉回路的图，称为欧拉图。
定理5.4.1 无向图G有一条欧拉路，当且仅当G是连通的，且有零个或
个结点入度等于出度。一个有向图G具有单向欧拉路，当且仅当是可达 的，且除两个结点外，每个结点入度等于出度，而这两个结点中，一 个结点的入度比出度大1，另一个结点的入度比出度小1.
定义5.4.3 给定图G，若存在一条路，经过图中每个结点恰好一次，这
条路称为汉密尔顿路，若存在一条回路，经过图中每个结点恰好一次， 这条路称为汉密尔顿回路。具有汉密尔顿回路的图称作汉密尔顿图。
5.4 欧拉图与汉密尔顿图

例2.今有a,b,c,d,e,f,g7人，已知下列事实： a会讲英语； b会讲英语和汉语； c会讲英语、意大利语和俄语； d会讲日语和汉语；


e会讲德语和意大利语；
f会讲法语、日语和俄语； g会讲法语和德语。 试问这7个人应如何排座位，才能使每个人和他身边的人交谈？
5.2 路与回路 图的连通性
5.2 路与回路 图的连通性

定义5.2.4 设无向图G=<V,E>为连通图，若有点集v1 V,使图G删除了
v1的所有结点后得到的子图是不连通的，而删除了v1的任何真子集后 所得到的子图仍是连通图，则称v1 是G 的一个点割集。若某一个结点 构成一个点割集，则称该结点为割点。
定理5.2.1 若图G中每个结点度数至少为2，则G包含一条初级回路。
5.2 路与回路 图的连通性



定义5.2.2 在无向图G中，结点u和v之间若存在一条路，则称结点u和v
是连通的。若图G中任何两个不同结点之间存在一条路，则称G为连通 图，否则G为不连通图。 点vi到vj存在路，则从vi到vj必存在长度小于等于n-1的一条路。
度，记为deg+(v)；以结点v为终点的弧数称为v的入度，记为deg-(v)。 结点的出度与入度之和就是该结点的度数。deg(v)=deg+(v)+deg-(v)
定理5.1.3 在有向图中，所以结点的入度之和等于所有结点出度之和。 定义5.1.5 对于无向图G=<V,E>，记
它们分别称为图G的最大度和最小度。
5.6 树及应用

例1


5.6 树及应用

图称为有向树。


定义5.6.4 如果有向图在不考虑边的方向时，是一棵树，那么这个有向 定义5.6.5 若一棵有向树，恰有一个结点入度为0，其余结点的入度均
为1，则称该有向树为根数。入度为0的结点称为根，出度为0的结点称 为叶，出度不为0的结点称为分枝点或内点。
定义5.2.5 设无向图G=<V,E>为连通图，若有边集e1 E,使图G删除了
e1的所有边后得到的子图是不连通的，而删除了e1的任何真子集后所 得到的子图仍是连通图，则称e1 是G的一个边割集。若某一个边构成 一个边割集，则称该结点为割边或桥。
5.3 图的矩阵表示

则有矩阵M=(mij),其中mij= 1,若vi与vj邻接， 0,若vi与vj不邻接,
(G) max{deg(v) | v V }, (G) min{deg(v) | v V }
5.1 图的基本概念
定义5.1.6 在无向图G=<V,E>中，如果每个结点的度是K，则图G称为K
度正则图。
定义5.1.4 在简单无向图G=<V,E>中，如果V中的每个结点都与其余的
两个奇数度结点。
推论：无向图G具有一条欧拉回路，当且仅当G是连通的，且所有结点
度数都是偶数。
七桥问题解答
例1
一笔画
5.4 欧拉图与汉密尔顿图
5.4 欧拉图与汉密尔顿图
5.4 欧拉图与汉密尔顿图
5.4 欧拉图与汉密尔顿图

路）称作单向欧拉路（回路）。


定义5.4.2 给定有向图G，通过图中每一边且仅一次的一条单向路（回 定理5.4.2 有向图G具有一条单向欧拉回路，当且仅当是可达的，且每
定理5.2.2 设有G=<V,E>，V的结点数|V|=n，称该图为n阶图，若从结 在有向图中，从结点u到v有一条路，则称从u到v是可达的。 定义5.2.3 在简单有向图G中，
任何一对结点间，至少有一个结点到另一个结点是可达的，则称这个 图是单侧连通的。
如果对于图G中任何一对结点，两者之间是相互可达，则称这个图是强 连通。 如果在图G中，略去边的方向，将它看成无向图之后，图是连通的，则 该图称为弱连通。
所有结点邻接，则该图称为完全图，记为Kn，n是|V|。
n个结点的完全图有n个端点及n(n − 1) / 2条边。它是(n − 1)正则图。
5.1 图的基本概念
定义5.1.7 设图G=<V,E>，如有图G'=<V',E'>,且E' E，V' V，则称
G'是G的子图。如果G的子图包含G的所有结点，即E' E，V' =V，则 G'是G的生成子图。
定义5.6.6 设u是有根树的分枝点，若从u到w有一条弧(u,w),则称w为u
的儿子或称u为w的父亲。若一个结点有两个儿子，则这两个儿子之间 称为兄弟。若从u到z有一条有向路，则称z是u的子孙或称u是z的祖辈。
从根到某一结点v的路的长度，称为v 的层数，从根到叶的最大层数，
称为根数的高。
定义5.6.7 在一棵有向树中，在每一级的结点都指定某种次序，称树为
有序树。
5.6 树及应用



定义5.6.8 在根数中，若每个结点的出度小于等于m，则称这棵树为m
叉树。如果每一个结点的出度恰好等于 m或0，则称这棵树为完全m叉 树，若其所有树叶层次相同，称为正则m叉树。
时，这条路称为回路。
若一条路中，所有边e1,e2,...,en均不相同，称作迹。若一条路中所有
结点v0,v1,...,vn均不相同（当然边也不相同），则称此路为初级路。 若回路中除v0=vn外其余结点各不相同，所以边也各不相同，则称此回 路为初级回路或圈。有边重复出现的路称为复杂路。有边重复出现的 回路称为复杂回路。


定义5.3.1 设G是n个结点，无多重边的图，设结点依次标记v1,v2,...,vn
称M(G)为图G的邻接矩阵。
例1
5.3 图的矩阵表示
定理5.3.1 设M是n个结点的简单图G的邻接矩阵，Mk=(mij(k))是M的k次
幂，则在Mk中mij(k)等于结点vi和vj之间长度k的路径的数目。
5.2 路与回路 图的连通性
定义5.2.1 给定图G=<V,E>设v0,v1,...,vn V，e1,e2,...,en E,其中ei是
关联于结点vi-1,vi的边。交替序列v0e1v1e2...env称为联结v0到vn的路。
v0和vn分别称作路的起点和终点，边的数目n称作路的长度。当v0=vn
离散数学
第五章 图论
主要内容 5.1图的基本概念 5.2路与回路 图的连通性 5.3图的矩阵表示 5.4欧拉图与汉密尔顿图 5.5平面图 5.6树及其应用
5.1 图的基本概念
定义5.1.1 一个图是二元组<V,E>,其中V是非空结点集，E是连接结点
的边集。
在图中每条边都用无序偶表达，这个图的每条边都是无向边，如果图

定义5.6.1 一个连通且无回路的无向图称为树。