下载文档原格式
第十章部分课后习题参考答案4．判断以下集合对所给的二元运算是否封闭： （1） 整数集合Z 和普通的减法运算。
封闭,不满足交换律和结合律，无零元和单位元 （2） 非零整数集合普通的除法运算。
不封闭（3） 全体n n ⨯实矩阵集合（R ）和矩阵加法与乘法运算，其中n2。
封闭 均满足交换律，结合律，乘法对加法满足分配律； 加法单位元是零矩阵，无零元；乘法单位元是单位矩阵，零元是零矩阵；（4）全体n n ⨯实可逆矩阵集合关于矩阵加法与乘法运算，其中n 2。
不封闭（5）正实数集合和运算，其中运算定义为：不封闭 因为 +∉-=--⨯=R 1111111 （6）n关于普通的加法和乘法运算。
封闭，均满足交换律，结合律，乘法对加法满足分配律 加法单位元是0，无零元；乘法无单位元（1>n ），零元是0；1=n 单位元是1 （7）A = {},,,21n a a a n运算定义如下：封闭 不满足交换律，满足结合律， （8）S =关于普通的加法和乘法运算。
封闭 均满足交换律，结合律，乘法对加法满足分配律 （9）S = {0,1},S 是关于普通的加法和乘法运算。
加法不封闭，乘法封闭；乘法满足交换律，结合律 （10）S =,S 关于普通的加法和乘法运算。
加法不封闭，乘法封闭，乘法满足交换律，结合律5．对于上题中封闭的二元运算判断是否适合交换律，结合律，分配律。
见上题7．设 * 为+Z 上的二元运算+∈∀Z y x ,，X * Y = min ( x ，y ),即x 和y 之中较小的数.(1)求4 * 6，7 * 3。
4, 3(2)* 在+Z 上是否适合交换律，结合律，和幂等律？ 满足交换律，结合律，和幂等律(3)求*运算的单位元，零元与+Z 中所有可逆元素的逆元。
单位元无，零元1, 所有元素无逆元8．Q Q S ⨯=Q 为有理数集，*为S 上的二元运算，<a,b>,<x,y >S 有< a ，b >*<x ，y> = <ax ，ay + b>（1）*运算在S 上是否可交换，可结合？是否为幂等的？ 不可交换：<x,y>*<a,b >= <xa ，xb +y>≠< a ，b >*<x ，y>可结合：(<a,b >*<x,y>)*<c,d>=<ax ，ay + b>*<c,d>=<axc ，axd +(ay+b) > <a,b >*(<x,y>*<c,d>)=<a, b>*<xc,xd+y>=<axc ，a(xd +y)+b > (<a,b >*<x,y>)*<c,d>=<a,b >*(<x,y>*<c,d>) 不是幂等的（2）*运算是否有单位元，零元？ 如果有请指出，并求S 中所有可逆元素的逆元。
第一章命题逻辑基本概念课后练习题答案4.将下列命题符号化，并指出真值：（1）p∧q,其中，p:2是素数，q:5是素数,真值为1；（2）p∧q,其中，p:是无理数，q:自然对数的底e是无理数,真值为1；（3）p∧┐q,其中，p:2是最小的素数，q:2是最小的自然数,真值为1；（4）p∧q,其中，p:3是素数，q:3是偶数,真值为0；（5）┐p∧┐q,其中，p:4是素数，q:4是偶数,真值为0.5.将下列命题符号化，并指出真值：（1）p∨q,其中，p:2是偶数，q:3是偶数,真值为1；（2）p∨q,其中，p:2是偶数，q:4是偶数,真值为1；（3）p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；（4）p∨q,其中，p:3是偶数，q:4是偶数,真值为1；（5）┐p∨┐q,其中，p:3是偶数，q:4是偶数,真值为0；6.（1）(┐p∧q)∨(p∧┐q),其中，小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨；（2）(p∧┐q)∨(┐p∧q),其中，p：刘晓月选学英语，q：刘晓月选学日语；.7.因为p与q不能同时为真.13.设p:今天是星期一，q:明天是星期二，r:明天是星期三：（1）p→q，真值为1（不会出现前件为真，后件为假的情况）；（2）q→p，真值为1（也不会出现前件为真，后件为假的情况）；（3）p q，真值为1；（4）p→r，若p为真，则p→r真值为0，否则，p→r真值为1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。
（1）p∨(q∧r)⇔0∨(0∧1) ⇔0（2）（p↔r）∧(﹁q∨s) ⇔（0↔1）∧(1∨1) ⇔0∧1⇔0.（3）（⌝p∧⌝q∧r）↔(p∧q∧﹁r) ⇔（1∧1∧1）↔ (0∧0∧0)⇔0(4)（⌝r∧s）→(p∧⌝q) ⇔（0∧1）→(1∧0) ⇔0→0⇔117．判断下面一段论述是否为真：“π是无理数。
并且，如果3是无理数，则2也是无理数。
另外6能被2整除，6才能被4整除。
习题一鮮答或提示1•⑴设P:他是本片的编剧，Q:他是本片的导決。
P A Q(2) 瑕P：级行利率吟低.Q:肢价上扬。
P→Q(3) 沒P:级行利率阵低.Q:股价上升。
〜(P→Q)(4) 设P：这个对象是占堀空问的∙Q:这个对象是有质量的R：这个对象是不飾变化的、S:这个对象称为场填。
P A Q A R→S(5) 沒P:他今天乘火车去了，Q：他今天随嵌行团去了九杀沟。
PVQ(6) 瑕P:小身体单萍，瑕Q:小圾少生病■没R:小头脑好使。
P A Q A R(7) 役P：这个人不枳庐丄真面Iu 设Q：这个人身A庐丄中。
QTR(8) 锻P：両个三角形柯似.没Q：两个三角形的对应角相普或者对应边成比例。
P<→Q(9) 沒P:-个整數能彼6整除，沒Q:这个整欽能彼2和3整除。
P→Q设R:-个整數能後3整徐，很S:这个整数的各住.数字之和也能彼3整除。
RTS2、(1)命題T(2) 命题T/F(3) 不是命题，因为真值无出确主。
⑷命题T(5)不是命题。
⑹命题T(7) 命题T/F(8) 不是命題，是悸论。
5、CU 证：〜((〜PAQJ V (〜PA〜Q丿)V CPAQJO (〜C〜PAQJ A〜(〜PA〜Q丿)V CPAQ丿o ( CPV 〜Q丿A CPVQJ ) V (PAQJO CPV (〜QVQJ ) V (PAQ)OPV CPAQ) OP(3) ⅛: Pf(QVR)o 〜PV(QVR)O 〜PVQV 〜P∖∕Ro C〜PVQJ V C〜PVR丿O(PfQ丿V (PfR丿6. 解：如系PVQoQ∖∕R∙不能靳走POR。
Q=T⅛, PVQ O QVR艳成立。
⅛r> PΛQ<=>QΛR,不能餅丈PoRO 因Q=F J⅛,PAQ O QAR怛成丈。
如系〜Po〜R, JK PORo8、把下刃冬丸用f寻价表承出来：(1) 豹CPAQJ 7〜TO C(PfQ) f (Pf Q丿V CPfP丿OCC(PfQf(PfQ)丿t C(PfQ)I(PtQ)J ) t (CPtPJ t (P↑?)) ⑶鮮：CP→ (QV〜R丿)A〜PO (〜PV (QV〜R丿)A〜Po ( CPtPJ V ΓQV CRtRJ )丿A (PtPJ ；O((PfP丿V ( CQ↑QJ t (CRtR) ↑ (^↑R) ) ) ) A CPtPJo ( ( CPtPJ t CP↑P> JtCC (QtQJ t ( (Rf R丿↑ CRtR) ) ) ↑(CQtQ) t ( (RfR丿t CRfR丿))))^ CPtP)OCL CPtPJ t CPtP) JtCr CQtQJ t ( CRtRJ t CRfR丿))↑ (ΓQtQJ ↑ ( CR↑RJ t CRfR丿))))↑(PW JtCCr CPtPJ ↑ (PfP丿) t (((Q↑Q) ↑ CCRtR丿t fR↑RJ ) ) ↑( CQtQJ t CfRfR丿t CRtRJJ))J t CPtP))9. ⅛E: ∙.∙ PVQ<=>---------- P VQ<=> (r~P∕ →QPAQ<≡>~ (〜PV〜Q丿O〜CPf〜Q丿而｛〜，V,八｝是功能克备.°.｛〜，f｝是功能完务集，〜，一►不能JL相表示，故｛〜・f｝是最小功能克备為。
四川大学离散期末考试题附标准答案本文档记录了四川大学离散数学期末考试相关的题目，并提供了每个问题的标准答案。
离散数学作为一门重要的数学基础课程，为计算机科学、信息技术以及其他相关学科提供了重要的理论支持。
通过解析这些题目和答案，可以加深对离散数学的理解，提升解题能力。
1. 题目1问题：设A、B、C三个集合满足：A={1,2,3,4,5}，B={3,4,5,6,7}，C={4,5,6,7,8}。
求(A∪B)∩C。
答案：集合A∪B表示将集合A和集合B中的元素合并，去重得到的结果集合。
∩表示求两个集合的交集。
因此，(A∪B)∩C表示先将集合A和集合B合并去重，然后再和集合C求交集。
具体操作如下： 1. 将集合A和集合B的元素合并：A∪B = {1,2,3,4,5,6,7}。
2. 将(A∪B)与集合C求交集：(A∪B)∩C = {4,5}。
所以，(A∪B)∩C = {4,5}。
2. 题目2问题：对于一个图G=(V, E)，其中V={a, b, c, d, e}表示节点集合，E表示边集合。
给定边集E = {(a, b), (b, c), (c, d), (d, e), (e, a)}，请问该图是否是欧拉图？答案：欧拉图是指一类特殊的连通图，可以经过每条边且每条边只经过一次的路径称为欧拉路径。
具有欧拉路径的图称为欧拉图或半欧拉图。
欧拉图有以下两个性质： - 每个顶点的度数都是偶数，或者只有两个顶点的度数是奇数，其余顶点的度数都是偶数。
- 图是连通的。
对于给定的图G=(V, E)，需要满足以上两个性质才能判断该图是否是欧拉图。
具体操作如下： 1. 统计每个顶点的度数： - a的度数为2 -b的度数为2 - c的度数为2 - d的度数为2 - e的度数为2由此可知，每个顶点的度数都是偶数，满足欧拉图的第一个性质。
2. 判断图是否是连通的：通过观察边集E = {(a, b), (b, c), (c, d), (d, e), (e, a)}，可以看出这个图是一个环，即从任意一个顶点出发，可以经过每条边且每条边只经过一次返回原点。
《离散数学》课后习题答案《离散数学》简介1、集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数2、图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用3、代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4、组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理5、数理逻辑部分：命题逻辑、一阶谓词演算、消解原理离散数学被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。
教学方式以课堂讲授为主，课后有书面作业、通过学校网络教学平台发布课件并进行师生交流。
《离散数学》学科内容随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。
离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型;又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
离散数学是传统的逻辑学，集合论(包括函数)，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数(包括代数系统，群、环、域等)，布尔代数，计算模型(语言与自动机)等汇集起来的一门综合学科。
离散数学的应用遍及现代科学技术的诸多领域。
离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。
作业答案：图论部分P165:习题九1、 给定下面4个图（前两个为无向图，后两个为有向图）的集合表示，画出它们的图形表示。
（1）111,G V E =<>，112345{,,,,}V v v v v v =，11223343345{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （2）222,G V E =<>，21V V =，11223344551{(,),(,),(,),(,),(,)}E v v v v v v v v v v = （3）13331,,,D V E V V =<>=31223324551{,,,,,,,,,}E v v v v v v v v v v =<><><><><> （4）24441,,,D V E V V =<>=31225523443{,,,,,,,,,}E v v v v v v v v v v =<><><><><> 解答： （1） （2）10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样的图。
（1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个奇度顶点 。
14、设G 是(2)n n ≥阶无向简单图，G 是它的补图，已知12(),()G k G k δ∆==，求()G ∆，()G δ。
解答：2()1G n k ∆=--；1()1G n k δ=--。
15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双射函数。
解答：（c ）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1（d ）同构，同构函数为16、画出所有3条边的5阶简单无向图和3条边的3阶简单无向图。
四川大学离散数学（冯伟森版）课后习题答案习题参考解答（图论部分）习题十1. 设G 是一个(n ，m)简单图。
证明：，等号成立当且仅当G 是完全图。
证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限max(d(v)) ≤ n-1, G 图的总点度上限为max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。
根据握手定理，G 图边的上限为max(m) ≤ n(n-1)/2,所以。
（2） =〉G 是完全图因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。
所以，G 的每个结点的点度都为n-1，G 为完全图。
G 是完全图 =〉因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数。
■2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。
证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。
与题设m = n+1，矛盾。
因此，G 中存在顶点u ，d （u ）≥3。
■3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。
因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。
可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。
最后，将奇数序列对应的点两两一组，添加连线即可。
下面以（2）为例说明：(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) v 1v 5v 3v 4v 2将奇数3，3 对应的结点v 2,v 3一组，画一条连线其他序列可以类式作图，当然大家也可以画图其它不同的图形。
■4．证明：在（n ，m ）图中。
证明：图的点度数是一组非负整数{d(v 1),d(v 2)…d(v n )}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。
对应到图的术语及为：最大值为，最小值为δ，平均值= (d(v 1)+d(v 2)…+d(v n ))/n = 2m/n,所以。
■5．证明定理10.2。
【定理10.2】对于任何（n ,m ）有向图G =（V ，E ），证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。
因此，上述关系等式成立。
■6．设G 是（n ，m ）简单二部图，证明：。
证明：本题目，我们是需要说明n 阶的简单二部图的边数的最大值 = 即可。
设n 阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n 。
此种情况下，当G 为完全二部图时，有最多的边数，即max(m) = |V1||V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n 阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。
及max(max(m)) = ,所以n 阶二部图(n,m), ■v 1 v 5v 3v 4v 2v 1v 5v 3v 4v 27. 无向图G 有21条边，12个3度数结点，其余结点的度数均为2，求G 的阶数n 。
解：根据握手定理有：21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■8．证明：完全图的点诱导子图也是完全图。
证明：方法1为证明此结论，我们先证两个引论：引论1：设G(V,E)为母图，,则G 的任意子图G'(V ’,E ’)是G 关于V ’的点诱导子图G''(V ’,E ’’)的子图。
引论2：引论1中G ’’(V ’,E ’’)的任意点诱导子图，也是G 图的点诱导子图。
证明：略，请读者证明。
设有完全图Kn( n ≥1),现根据其p 阶点诱导子图作归纳证明。
Kn 的1阶点诱导子图，显然是完全图，且都是K1图。
当n ≥2，Kn 的2阶点诱导子图，显然是完全图，且都是K2图假设Kn 的p(n >p >2)阶点诱导子图，为Kp 图，那么对任意的p+1阶点诱导子图G ，根据引理2结论，G 的任意p 阶点诱导子图G ’为Kn 的p 阶点诱导子图，且为Kp 图。
因此，G 必为Kp+1图。
根据以上论证可得原命题成立■ 方法2因为完全图的任意两个顶点均邻接，所以点导出子图任意两个顶点也邻接，为完全图。
■ 9．若，称G 是自补图。
确定一个图为自补图的最低条件；画出一个自补图来。
解：设G 为(n,m)图，为(n,m`)图，根据补图的定义有，至少应该满足m+m`=n(n-1)/2 (1) 根据同构的定义有，至少应该满足m=m` (2)(1),(2)联立求解得：m=n(n-1)/4, 及一个图为自补图，最低条件为结点数为4的倍数或为4的倍数加1。
图示略■10．判断图10.29中的两个图是否同构，并说明理由。
图9-1.15解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。
因此这两个图不可能同构■11．证明：图10.30中的两个图是同构的。
图10.29解：略■12. 求具有4个结点完全图K 4的所有非同构的生成子图。
解：我们可以把生成子图按总度数不同进行分类，不同总度数的子图类决不同构。
总度数相同的子图类中，再去找出不同购的子图。
因此求解如下：Σd(v) = 0: (0,0,0,0) =2: (1,1,0,0)=4: (2,1,1,0) (1,1,1,1)=6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3)总共10个不同构生成子图■13. 设有向图D=如下图10.31所示。
(1) 在图中找出所有长度分别为1，2，3，4的圈(至少用一种表示法写出它们，并以子图形式画出它们)。
(2) 在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。
解：(1)图10.30(2)子图略长度为三的回路：Ae 1Ae 1Ae 1A,Ae 1Ae 3De 2A,Ae 4Be 7Ce 5A,Ae 4Be 8Ce 5A长度为四的回路：AAAAA ，AAADA ，AABe 7CA,AABe 8CA,ABe 7CDA,ABe 8CDA长度为五的回路：AAAAAA,AAAADA,AAABe 7CA,AAABe 8CA,AABe 7CDA,AABe 8CDA, AADADA,AAAe 4Be 7Ce 5A,AAAe 4Be 8Ce 5A, ADAe 4Be 7Ce 5A,ADAe 4Be 8Ce 5A ■14. 试证明在任意6个人的组里，存在3个人相互认识，或者存在3个人相互不认识。
证明：设A 为6人中的任一人，那么A 要么至少与3人认识，要么至少与3人不认识，二者必居其一。
假设A 与B ，C ，D 三人认识，如果B ，C ，D 三人互不认识，结论成立如果B ，C ，D 三人中，至少有两人相互认识，则它们和A 一起，构成相互认识的3人，结论成立。
同理，A 至少与3人不认识，结论也成立。
因此，题设结论成立■15. 若u 和v 是图G 中仅有的两个奇数度结点,证明u 和v 必是连通的。
证明：反证法，假设u 和v 不连通，那么他们必然分布于此图的两个连通分支中。
那么它们将分别是各连通分支中唯一的奇数度结点。
根据握手定理，一个图中奇度点的个数为偶数。
而两个连通分支中，奇度点的个数为奇数。
矛盾。
矛盾的产生，是由于假设不连通导致的，因此，题设结论成立■16. 证明:G 是二部图当且仅当G 的回路都是偶长回路。
证明：设二部图G ，顶点分为两个集合V1 ，V2 充分性：先证明在二部图中，奇长路的道路的两个端节点一定分别在两个顶点集合中，对道路长度使用归纳法，（1）当道路长度为1是，根据二部图的定义，每条边的两个顶点分别在两个点集合中，结论成立（2）假设道路长度为2n-1 ( n ≥2)时结论成立（3）当道路长度为2n+1时，设P=v 1v 2…v 2n-1v 2n v 2n+1,在此路径上删除最后两个结点，那C=AAC=ADA C=Ae 4Be 7Ce 5AC=Ae 4Be 8Ce 5A C=Ae 4Be 7Ce 6De 2AC=Ae 4Be 8Ce 6De 2A么道路P将变为长度为2n-1的奇长道路，根据假设，v1,v2n-1分别在两个顶点集合中，那么v2n和v1在同一顶点集合中，而v2n+1和v1在不同顶点集合，结论成立因为G中的任何回路，写成道路的形式，起点和终点时一个结点，当然在同一个顶点集合中，因此长度必为偶数；必要性：（仅对连通分支证明）在图中任意取一点着色为白色，将和此点最短距离为奇数的点着色为黑点，为偶数的着色为白点，那么将结点分为白色和黑色连个点集，任何同色点之间没有边相连。
否则将形成奇数长度的回路，例如同色结点v1，v2 相邻，那么从初始着色点v开始通过最短路径可以形成如下回路v…v1v2…v,因为v…v1,v2…v长度和为偶数，那么回路v…v1v2…v长度为奇数，与题设矛盾。
所以是二部图17.设(n, m)简单图G满足,证明G必是连通图。
构造一个的非连通简单图。
证明：假设G不连通，分支G1，G2．．Ｇｋ，那么他们的边数的最大值ｍａｘ（ｍ）＝Σ（ｎｉ－１）ｎｉ／２≤Σ（ｎｉ－１）（ｎ－１）／２＝（ｎ－１）／２Σ（ｎｉ－１）＝（ｎ－１）（ｎ－ｋ）／２，所以，只有当k=1时，才能满足题设要求，G是连通图。
如果将顶点集合分成两个点集，|V1|=1，|V2|=n-1,构成如下的有两个分支的非连通简单图，G1=（1，0），G2=Kn-1,满足题设条件■18. 设G是阶数不小于3的连通图。
证明下面四条命题相互等价:(1）G无割边；(2) G中任何两个结点位于同一回路中；(3) G中任何一结点和任何一边都位于同一回路中；(4) G中任何两边都在同一回路中。
证明：（1）=〉（2）因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p’,以此类推，可以找到一条核p每条边都不相同的p’’=v…u,这样p和p’’就构成了一条回路。
