离散数学(软件)课程第14章

格式：pdf
大小：899.94 KB
文档页数：59

下载文档原格式

大连理工大学软件学院离散数学习题答案

目录第一章命题逻辑 (2)第二章谓词逻辑 (9)第三章集合论习题答案 (13)第四章二元关系习题答案 (21)第五章函数习题答案 (42)第六章代数系统习题答案 (51)第七章群与环习题答案 (57)第八章格与布尔代数习题答案 (66)第九章图的基本概念及其矩阵表示 (71)第十章几种图的介绍 (82)第十一章树 (90)第一章命题逻辑1.（1）不是命题；（2）不是命题；（3）不是命题；（4）是命题；（5）是命题；2.（1）并非大连的每条街都临海；（2）2不是一个偶数或者8不是一个奇数；（3）2不是偶数并且-3不是负数；3.（1）逆命题：如果我去公园，那么天不下雨。

否命题：如果天下雨，我将不去公园。

逆否命题：如果我不去公园，那么天下雨。

（2）逆命题：如果我逗留，那么你去。

否命题：如果你不去，那么我不逗留。

逆否命题：如果我不逗留，那么你不去。

（3）逆命题：如果方程无整数解，那么n是大于2的正整数。

否命题：如果n不是大于2的正整数，那么方程有整数解。

逆否命题：如果方程有整数解，那么n不是大于2的正整数。

（4）逆命题：如果我不能完成这项任务，那么我不获得更多的帮助。

否命题：如果我获得更多的帮助，则我能完成这项任务。

逆否命题：如果我能完成这项任务，则我获得更多的帮助。

4.（1）T；（2）T；（3）T；（4）F；5.6.（1）P:他聪明；Q:他用功；命题：P∧Q。

（2）P:天气好；Q:我骑车上班；命题：Q→P。

（3）P:老李是球迷；Q:小李是球迷；命题：P∨Q。

（4）P:休息好；Q:身体好；命题：Q→P。

7.8.9.（1）（P∧Q）→R；（2）┓P；（3）（┓P∧┓Q）→┓R10.不依赖于命题变元的真值指派，而总取T（1）的命题公式，称为重言式（永真式）；不依赖于命题变元的真值指派，而总取F（0）的命题公式，称为永假式（矛盾式）；至少存在一组真值指派使得命题公式取值为T的命题公式称为可满足的。

本题可用真值表求解：（4）得真值表如下：1，故为重言式。

离散数学(第十四章)

8
实例
强连通
单连通
弱连通
二部图
定义14.23 设 G=<V,E>为一个无向图，若能将 V分成 V1和V2 (V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是一个属于V1，另一个属于V2，则称 G 为二部图 ( 或称二分图、偶图等 )，称V1和V2为互补顶点子集，常将二部图G 记为<V1,V2,E>.
m 2 ( j 1,2,...,m ) ( 2) m d ( v ) ( i 1, 2,...,n) ( 3) m 2m
n i 1 m ij j 1 ij i ij i, j
(4) 平行边的列相同
13
无向图的关联矩阵
例如 M(G)=
211000 010111 000011 000000 001100
1. 删除顶点及删除边 Gv ——从G中将v及关联的边去掉 GV——从G中删除V中所有的顶点 Ge ——将e从G中去掉 GE——删除E中所有边 2. 点割集与边割集点割集与割点定义14.16 G=<V,E>, VV V为点割集——p(GV)>p(G)且有极小性 v为割点——{v}为点割集定义14.17 G=<V,E>, EE E是边割集——p(GE)>p(G)且有极小性 e是割边（桥）——{e}为边割集
6
有向图的连通性
定义14.20 D=<V,E>为有向图 vi vj（vi 可达 vj）——vi 到vj 有通路 vi vj（vi 与vj 相互可达）性质具有自反性(vi vi)、传递性具有自反性、对称性、传递性 vi 到vj 的短程线与距离类似于无向图中，只需注意距离表示法的不同 (无向图中d(vi,vj)，有向图中d<vi,vj>) 及 d<vi,vj>无对称性

《离散数学(软件)》教学大纲

《离散数学（软件）》课程教学大纲课程编号：18084制定单位：用友软件学院制定人（执笔人）：赵晓平审核人：尹爱华制定（或修订）时间：2010年8月20日江西财经大学教务处《离散数学》课程教学大纲一、课程总述二、教学时数分配三、单元教学目的、教学重难点和内容设置绪论【教学目的】使学生了解学习离散数学的目的和意义，同时掌握离散数学的学习方法。

【重点难点】怎样学习离散数学。

【教学内容】1、《离散数学》学什么；2、为什么学习《离散数学》；3、怎样学习《离散数学》。

命题逻辑的基本概念【教学目的】掌握命题的概念及其表示法，掌握五个联结词的概念及性质、真值表，理解原子命题、复合命题，掌握命题公式与翻译，掌握命题公式的生成及利用真值表对命题公式的判定，了解其它联结词。

【重点难点】重点：命题和命题公式、五个联结词的性质、真值表。

难点：命题的翻译。

【教学内容】命题与联结词命题公式及其赋值命题逻辑等值演算【教学目的】熟悉掌握常用的命题等价公式和蕴涵公式，命题公式的等价公式，重言式与蕴含式推理理论，掌握小项与大项的定义及其性质，熟练掌握求一个命题公式的主析取公式和主合取范式，了解联结词的完备集。

【重点难点】重点：命题公式的等值演算，等价公式、重言式与蕴含式的性质，命题公式的范式。

难点：求命题公式的主析取公式和主合取范式。

【教学内容】等值式析取范式与合取范式联结词的完备集命题逻辑的推理理论【教学目的】了解推理的形式结构，理解推理理论的有效结论，了解判别有效结论的方法，掌握自然推理系统，理解掌握P规则、T规则、CP规则进行命题演算的推理。

【重点难点】重点：推理的形式结构和自然推理系统。

难点：命题的推理理论和方法。

【教学内容】推理的形式结构自然推理系统P一阶逻辑基本概念【教学目的】掌握谓词与量词的概念，掌握约束变元与自由变元的概念，了解命题逻辑的知识和命题逻辑与谓词逻辑的联系与区别。

理解命题函数、复合命题函数的概念，掌握谓词公式的翻译。

西北工业大学《离散数学》课件-第14章

{a} {a}{b} {b{}a,b{}a,b} x x ∼x ∼x {a} {a}{b} {b}{a,b{}a,b} {a,b{}a,b} {a} {a} {a} {a} {a.b{}a.b{}b} {b} {a} {a} {a} {a} {b} {b} {b} {b{}a,b{}a,b} {a} {a} {b} {b} {b} {b} {a,b{}a,b}{a,b{}a,{bb}} {b}{a} {a} {a,b{}a,b}
的逆元
12
实例
集合运算
Z,Q,R 普通加法+ 普通乘法
单位元
0 1
零元无 0
Mn(R) P(B)
矩阵加法+ 矩阵乘法
并交对称差
n阶全0矩阵 n阶单位矩阵
B
无 n阶全0
矩阵
B 无
逆元
x逆元x x逆元x1 (x1给定集合)
X逆元X X的逆元X1 （X可逆）
的逆元为 B的逆元为B X的逆元为X
交与对称差对可分配无
10
特异元素：单位元、零元
定义14.7-9 设◦为S上的二元运算, (1) 如果存在el (或er)S，使得对任意 x∈S 都有
el◦x = x (或 x◦er = x)，则称el (或er)是S中关于◦运算的左(或右)单位元. 若e∈S关于◦运算既是左单位元又是右单位元，则称e为S上关于◦运算的单位元. 单位元也叫做幺元.
2
14.1 代数系统的基本概念
定义14.1 设S为集合，函数f：SSS 称为S上的二元运算，简称为二元运算．函数 f:S→S 称为S上的一元运算，简称一元运算. S 中任何元素都可以进行运算，且运算的结果惟一． S 中任何元素的运算结果都属于 S，即 S 对该运算封闭．

离散数学-近世代数-代数结构

添加标题
例：代数系统(N，+，×)。其中+，×分别代表通常数的加法和乘法。
添加标题
是否满足交换律？
添加标题
单位元( 幺元)
一个代数系统(S，*)，若存在一个元素eU，使得对 xS，有：e * x =x * e = x，则称 e 为对于运算“ * ”的单位元,也称幺元。注意：单位元是跟运算有关系的，不同的运算可能单位元是不一样的。
解：作双射 f：A1A2，f(1)=b, f(2)=d, f(3)=c, f(4)=a
a
b
c
d
a
b
b
b
d
b
a
a
d
b
c
c
b
c
a
d
a
a
c
d
*
1
2
3
4
1
4
1
2
4
2
4
2
3
4
3
1
4
3
3
4
1
2
1
1
设代数系统V1=(A1，*)，V2=(A2，º)，其中A1={1，2，3，4}， A2={a，b，c，d}， * 和 º 的运算分别如下表，V1 和 V2 是否同构？
等幂律
设 * 是定义在集合A上的一个二元运算，如果对于任意的xA，都有x * x = x，则称 * 运算是等幂的。例: S={1,2,4}，在集合 p(S) 定义两个二元运算，∩，∪，分别表示集合的“并”运算和集合的“交”运算，∩，∪是等幂的？解：对于任意的A p(S) ，有A∩A=A；A∪A=A 因此运算∩，∪都满足等幂律。
性质、定理
定理一个代数系统，其零元若存在，则唯一。定理一个代数系统(S，)，若集合 A 中元素的个数大于1，且该代数系统存在幺元 e 和零元θ，则θe。证明：用反证法，设θ=e，则对于任意的xA，必有 x = ex = θx =θ= e，即对于A中所有元素都是相同的，这与A中含有多个元素相矛盾。

离散数学第14章课件PPT-高等教育出版社-屈婉玲-耿素云-张立昂主编(高等教学)

支，其个数 p(G)=k (k1)； k=1，G连通
行业材料
21
短程线与距离
(3) 短程线与距离 ① u与v之间的短程线：uv，u与v之间长度最短的通路 ② u与v之间的距离：d(u,v)——短程线的长度 ③ d(u,v)的性质： d(u,v)0, u≁v时d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)
易知，强连通单向连通弱连通
判别法定理14.8 D强连通当且仅当D中存在经过每个顶点至少一次的回路定理14.9 D单向连通当且仅当D中存在经过每个顶点至少一次的通路
行业材料
27
二部图
定义14.23 设 G=<V,E>为一个无向图，若能将 V分成 V1和V2 (V1V2=V，V1V2=)，使得 G 中的每条边的两个端点都是一个属于V1，另一个属于V2，则称 G 为二部图 ( 或称二分图、偶图等 )，称V1和V2为互补顶点子集，常将二部图G 记为<V1,V2,E>. 又若G是简单二部图，V1中每个顶点均与V2中所有的顶点相邻，则称G为完全二部图，记为 Kr,s，其中r=|V1|，s=|V2|.
vV
vV1
vV2
由于2m, d(v) 均为偶数，所以 d(v) 为偶数，但因为V1中
vV2
vV1
顶点度数为奇数，所以|V1|必为偶数.
行业材料
10
握手定理应用
例1 无向图G有16条边，3个4度顶点，4个3度顶点，其余顶点度数均小于3，问G的阶数n为几？
解本题的关键是应用握手定理. 设除3度与4度顶点外，还有x个顶点v1, v2, …, vx，则
i 1
i 1
i 1
本定理的证明类似于定理14.1

离散数学第14讲

1
知识回顾
定义为集合，中元素为第一元素，中设A，B为集合，用A中元素为第一元素，B中，为集合中元素为第一元素元素为第二元素构成有序对。元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和的笛卡儿积，序对组成的集合叫做和B的笛卡儿积，记作A×B。 × 。笛卡儿积的符号化表示为：笛卡儿积的符号化表示为： A × B={<x,y>|x ∈ A ∧ y∈ B} ∈
OBVIOUS: R是A上的传递关系 R。R ⊆ R 是上的传递关系。
7
知识回顾
等价关系与划分
是非空集合A上的关系是自反的、定义设R是非空集合上的关系。若R是自反的、对称的是非空集合上的关系。是自反的和传递的，则称R是A上的等价关系。和传递的，则称是上的
是非空集合A上的等价关系定义设R是非空集合上的等价关系， ∀x∈A，令是非空集合上的等价关系，， [x]R={y| y ∈ A ∧ xRy} 称 [x]R为x关于的等价类，简称为x的等价类，简记为[x]或x。关于R的等价类，简称为的等价类，简记为或。关于的等价类是非空集合A上的等价关系定义设R是非空集合上的等价关系，以R的所有等价类作是非空集合上的等价关系，的所有等价类作为元素的集合称为A关于的商集，记作A/R，即为元素的集合称为关于R的商集，记作关于， A/R={[x]R| x ∈ A }
证明：证明：
设A={x1, x2 ,…, xn},构造相容类序列构造相容类序列构造 C0 ⊂ C1 ⊂ C2 ⊂… ⊂ Cn，其中 0 =C 其中C 其中k是满足不属于C 是满足x 且Ci+1 = Ci ∪{xk} ，其中是满足 k不属于 i而xk与Ci中各元素都有相容关系的最小下标。各元素都有相容关系的最小下标。由于A的元素个数有限所以至多经过n-|C|步，就可的元素个数有限，由于的元素个数有限，所以至多经过步使此过程结束，此时的相容类就是要找的最大相容使此过程结束，此时的相容类就是要找的最大相容类。

离散数学刘任任版第14章答案.ppt

x 和y 的作用域： (R(x, y) Q(x, z)
x 的作用域： H (x, y)
5．设谓词公式。判定以下改名是否正确：
x (P(x, y) Q(x, z))
(1)u(P(u, y) Q(x, z))
错误
(2)u(P(u, y) Q(u, z))
正确
(3) x(P(u, y) Q(u, z))
x0 D或y0 D, 使得G（x0,y）或G（x, y0）为假，
于是，此xo或yo亦弄假 yxG(x, y)
（2） xyG(x，y) yxG(x，y)
证：设D是论域，I是G（x, y）的一个解释。
（a)若 xyG(x，y) 在 I 下的为真，则在 I 下,有
8．
• (1) x(G(x) H ) xG(x) H
• (2) x(G(x) H ) xG(x) H
• 证明（1）
x(G(x) H ) x(7G(x) H ) x7G(x) H 7(xG(x)) H xG(x) H
• 证明（2）
x(G(x) H ) x(7G(x) H ) x7G(x) H 7(xG(x)) H xG(x) H
解：P(x) : x是实数，Q(x) : x是有理数. x(P(x) Q(x))
(2)有些实数是有理数。解：P(x) : x是实数，Q(x) : 是有理数。
xyPx Q(x)。
(3)并非所有实数都是有理数。解：P(x) : x是实数，Q(x) : x是有理数. x(P(x) Q(x)) (4)如果明天天气好, 有一些学生将去公园. 解 : P(x) : x是公园, S(x) : x是学生,W :明天天气好. W x(P(x) S(x))
离散数学
习题解答
1、

离散数学课程教学大纲

离散数学课程教学大纲一、课程简介本课程是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。

离散数学主要是研究离散量的结构和相互关系，具体内容包括数理逻辑、集合论、代数系统、图论。

它综合了计算机科学中所用到的研究离散量的各个数学课题，并进行系统、全面的论述。

通过本课程的学习，使学生掌握高级科研人员或高级技术人员必备的离散数学基本理论和基本方法，同时，结合本课程的特点，可以培养学生的抽象思维和缜密的概括能力，为进一步学习专业课打好基础，并为学生今后处理离散信息，解决计算机科学各个领域中提出的有关离散量的理论问题，提高专业理论水平，为从事计算机的应用提供必要的描述工具和理论基础。

课程教学强调培养学生的独立思考能力、科学思维方法和求知创新精神。

最终使学生能够在众多的概念、定理中抽象出最重要、最根本的理论，并将这些基本的概念和定理透彻理解，自如运用，从而达到掌握离散数学的教学要求。

二、课程目标（一）课程具体目标1. 掌握计算机工程技术实践所需的离散量的数学知识：数理逻辑、集合论、图论，并能够运用于解决计算机软件工程领域的复杂工程问题；2. 掌握计算机学科基础理论，并能够用于解决复杂工程问题；3. 能够运用离散数学知识表述复杂工程问题；4. 能够运用数理逻辑和图论知识对所选模型的理论正确性进行分析和推理。

（二）课程目标与专业毕业要求的关系表1 本课程对专业毕业要求及其指标点的支撑（三）课程对解决复杂工程问题能力的培养在课程理论知识讲授环节，注重培养学生对软件工程中所涉及到的离散量的数学的深入理解，使学生掌握解决软件工程领域复杂工程问题所需的基本离散数学理论，并通过适当的课后作业锻炼和检验学生解决复杂工程问题的能力。

在课程考核环节，根据课程支撑的课程目标选择合适的考核方式，考题设置应完全覆盖课程支撑的课程目标，考题设计应充分考虑学生解决复杂工程问题所需的知识和能力，考题的难度和深度应能够体现复杂工程问题的特征。

《离散数学》完整课件

第三节复合关系与逆关系
本节讨论关系的复合运算与逆运算极其性质;主要考虑了下列问题:
1.关系的复合是否满足交换律、结合律、关系的复合对于集合的并(交)是否有分配律;
2.关系的复合运算与逆运算在关系图和关系矩阵上的反应;
3.关系的复合运算与关系的逆运算之间的运算规律.
返回本章首页
11 2021/6/7
|A|<|B|三条中有且仅有一条成立；
2.Bernstein定理:设A,B是两个集合,若|A|≥|B| 且|A| ≤ |B|,则集合A,B等势;
3.设A是任意集合,P(A)为A的幂集,则P(A)的基数大于A的基数.
返回本章首页
23 2021/6/7
本章小结
本章的主要内容有：集合的等势、有限集与无限集、可数集与不可数集、较为常见的集合的基数等.集合的基数反映了集合的元素的多少，它是集合的一种性质，一种与该集合等势的集合构成的集合族的共同性质.
返回本章首页
17 2021/6/7
第九节复合映射与逆映射
映射的复合就是关系的复合,须注意的是复合的次序,主要内容有:
1.映射的复合具有结合律,但不符合交换律; 2.区分了左逆与右逆；给出里左逆、右逆
与单射、满射之间的关系； 3.可逆与左、右逆之间的关系.
返回本章首页
18 2021/6/7
本章小结
1.本节首先给出了公式的蕴涵关系的三个等价定义,及蕴涵关系具有的性质,给出了15个基本蕴涵式；
2.把蕴涵概念推广,得到公式的逻辑结果的定义；
3.为了研究推理，还引进演绎的概念；
4.用实例说明推理方法.
返回本章首页
30 2021/6/7
第六节形式演绎

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

G的最大度(G)=max{d(v)| vV} G的最小度(G)=min{d(v)| vV}
例如 d(v5)=3, d(v2)=4, d(v1)=4,
(G)=4, (G)=1,
v4是悬挂顶点, e7是悬挂边, e1是环。
11
设D=<V,E>为有向图, vV, v的出度d(v)：v作为边的始点次数之和 v的入度d+(v)：v作为边的终点次数之和 v的度数(度) d(v)：v作为边的端点次数之和 d(v)= d+(v)+ d-(v)
接于vi .
vi
vj
定义标定图：顶点或边带标记。
非标定图：顶点或边不带标记。
如
a
c
b
d
7
4、邻域和关联集
设无向图G, vV(G)
v的邻域
v的闭邻域
v的关联集
先
v
后
设有向图D, vV(D) 驱
继
v的后继元集
v的先驱元集
v的邻域
v的闭邻域
8
5、多重图与简单图
定义 (1)平行边：在无向图中,关联同一对顶点的无向边多于1条. 在有向图中,关联同一对顶点的有向边多于1条，且这些边的始点和终点相同(同向)。重数：平行边的条数.
5
3、顶点和边的关联与相邻
定义设ek=(vi, vj)是无向图G=<V,E>的一条边, 称vi, vj 为ek的端点, ek与vi ( vj)关联. 若vi vj, 则称ek与vi ( vj) 的关联次数为1;若vi = vj, 则称ek为环, 此时称ek与vi 的关联次数为2; 若vi不是ek端点, 则称ek与vi 的关联次数为0. 无边关联的顶点称作孤立点.
定义设无向图G=<V,E>, vi,vjV, ek,elE, 若(vi,vj) E,
则称vi,vj相邻; 若ek,el至少有一个公共端点, 则称
ek,el相邻. vi
vj
(vi,vj)
ek el
6
对有向图有类似定义. 设ek=vi,vj是有向图的一条
边,又称vi是ek的始点, vj是ek的终点, vi邻接到vj, vj邻
D的最大出度(D), 最小出度(D) 最大入度+(D), 最小入度+(D) 最大度(D), 最小度(D)
例如 d(a)=4, d+(a)=1, d(a)=5, d(b)=0, d+(b)=3, d(b)=3,
(D)=4, (D)=0, +(D)=3, +(D)=1, (D)=5, (D)=3.
12
例如图，V={v1, v2, …,v5}, E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}
2
有向图 D=<V,E>, 其中 (1) V同无向图的顶点集, 元素也称为顶点. (2) E是笛卡尔积VV的多重子集，其元素称为有向边，简称边.
如右图，试写出它的V和E。
注意：图的数学定义与图形表示，在同构的意义下是一一对应的。
3
一般地，用小圆圈（或实心点）表示顶点，用顶点间的连线表示无向边，用有方向的连线表示有向边。如
u
vu
v
(u, v)
(起点) <u, v> (终点)
例1 设D=<V, E>，V={a, b, c, d, e}，E={<a, a>, <a, b>, <a, b>, <b, a>, <b, c>, <c, d>, <d, b>}，画图。42、几个特殊的图
通常用G表示无向图, D表示有向图, 也常用G泛指无向图和有向图, 用ek表示无向边或有向边. V(G), E(G) —表示图G的顶点集, 边集. |V(G)|, |E(G)| —表示图G的顶点数集（阶）和边数. n 阶图：n个顶点的图有限图：V, E都是有穷集合的图零图：E= 平凡图：1 阶零图空图：V= 基图：用无向边代替D的所有有向边所得到的无向图称作D的基图。
14
8、图的度数列
(1) 设无向图G的顶点集V={v1, …, vn} G的度数列: d(v1), d(v2), …, d(vn) 如右图度数列:4,4,2,1,3
(2) 设有向图D的顶点集V={v1, v2, …, vn} D的度数列: d(v1), d(v2), …, d(vn) D的出度列: d(v1), …, d(vn) D的入度列: d+(v1), …, d+(vn)
2·x=2×16 ∴ x=16 (2) 21条边, 3个4度的顶点, 其余顶点的度数均为3。解：设顶点数为x，由握手定理，有
4×3+3×(x-3)=2×21 ∴ x=13 (3) 24条边，每个顶点的度数均相同。解：设顶点数为x，顶点的度数为y，则x·y= 2×24
∴整数解(x, y)有：(2, 24), (24, 2), (3, 16), (16, 3), (4, 12), (12, 4), (6, 8), (8, 6) 8种。
第十四章图的基本概念
14.1 图
无向图与有向图几个特殊的图顶点和边的关联与相邻邻域和关联集简单图与多重图顶点的度数
握手定理图的度数列图的同构完全图与正则图子图补图
1
1、无向图与有向图
多重集合：元素可以重复出现的集合。无序积：AB={(x,y) | xAyB} 。无向图 G =<V,E>, 其中 (1) V为顶点集，元素称为顶点. (2) E为VV的多重子集，其元素称为无向边，简称边.
(2) 简单图：既无平行边也无环的图. (3) 多重图：含平行边的图.
注意：简单图是极其重要的概念
9
例2
e5和e6 是平行边重数为2
不是简单图
e2和e3 是平行边,重数为2 e6和e7 不是平行边不是简单图
10
6、顶点的度数
设G=<V, E>为无向图, vV, v的度数(度) d(v)：v作为边的端点次数之和悬挂顶点：度数为1的顶点悬挂边：与悬挂顶点关联的边
7、图论的基本定理—握手定理
定理任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数.
d(v) 2m d(v) d(v) m
推论在任何无向图和有向图中，奇度顶点的个数必为偶数.
13
例3 下列各图中各有多少个顶点？ (1) 16条边，每个顶点的度数均为2。解：设顶点数为x，由握手定理，有