SCUT2008

一、填空题

  1. 求合式公式xP(x)xQ(x,y)前束范式

    答案xz(P(x)Q(z,y))

    前束范式(Prenex Normal Form)是数理逻辑中谓词逻辑公式的一种标准形式。以下是关于前束范式的详细介绍:

    定义

    一个谓词逻辑公式称为前束范式,如果它具有以下形式:(Q1x1)(Q2x2)(Qkxk)B,其中Qii=1,2,,k)是量词(),xi是个体变元,B是不含量词的谓词公式(称为母式或基式)。

    特点

    1. 量词前置:所有的量词都被集中在公式的开头,按照一定的顺序排列,后面跟着一个不含任何量词的公式。
    2. 清晰的量词辖域结构:每个量词的辖域(即量词作用的范围)在形式上一目了然,有助于对公式进行逻辑分析和推理。

    示例

    1. 公式xy(P(x,y)Q(x,y))是前束范式,其中xy是量词,P(x,y)Q(x,y)是母式。
    2. 而公式x(P(x)yQ(y))虽然量词都在前面,但它不是前束范式,因为连接了两个包含量词的部分,不满足母式不含量词的要求。通过等价变换可以化为前束范式,如xy(P(x)Q(y))

    转换为前束范式的方法

    1. 消除量词前的否定符号:利用量词否定等价式,如¬xP(x)x¬P(x)¬xP(x)x¬P(x),将否定符号移到量词后面。
    2. 约束变元换名:如果存在不同量词约束的变元同名,为了避免混淆,使用换名规则,将其中一个变元换为其他未使用过的变元。例如,x(P(x)xQ(x))可换名为x(P(x)yQ(y))
    3. 将量词移到公式前面:利用量词辖域扩张与收缩等价式,如x(P(x)Q)(xP(x)Q)x不在Q中自由出现),x(P(x)Q)(xP(x)Q)x不在Q中自由出现)等,将量词逐步移到公式的最前面。
  2. 设集合A={a,b,{a,b},}B={{a,b},},求BA=?

    答案。因为A包含B中的全部元素,所以BA=

  3. pq的真值为0r的真值为1,则命题(pq)r的真值是:。

    答案:1。只有当(p\andq)为真,且r为假时,(p\andq)\rarrr为假,其余为真。

  4. R是在正整数集合Z+上如下定义的二元关系:

    R={(x,y)(x,y\Z+)\andx+y=10}

    则它一共有?个有序对,且有自反性、对称性、传递性、反自反性和反对称性各性质中的 ? 性质。

    答案:共有 9 个有序对,(1,9)(2,8),(3,7)······(9,1),可以发现存在(1,9)(9,1)这样的有序对,所以满足对称性

  5. 公式x(P(x)Q(x,y))S(x)中的自由变元为?,约束变元为?

    答案:自由变元为Q(x,y)中的yS(x)中的x,约束变元为Q(x,y)中的xP(x)中的x

    1. 自由变元与约束变元的定义
    • 约束变元是在量词的辖域内出现的变元,并且该变元被量词所约束。
    • 自由变元是在公式中出现但不受任何量词约束的变元。
    1. 分析公式x(P(x)Q(x,y))S(x)中的变元
    • 对于x(P(x)Q(x,y))这部分:
    • x在量词的辖域内,并且受到的约束,所以x在这里是约束变元。同时xP(x)Q(x,y)中出现,都受到前面x的约束。
    • yQ(x,y)中出现,但是没有任何量词对y进行约束,所以y是自由变元。
    • 对于S(x)这部分:x在这里没有被任何量词约束(前面的x的辖域到Q(x,y)结束),所以x是自由变元。 综上,公式x(P(x)Q(x,y))S(x)中的自由变元为Q(x,y)中的yS(x)中的x;约束变元为Q(x,y)中的xP(x)中的x
  6. 设有命题T(x):x是火车,C(x):x是汽车,Q(x,y):x跑得比y快,那么命题“有的汽车比一些火车跑得快”的逻辑表达式是?

    答案x(C(x)y(T(y)Q(x,y)))

    1. 首先分析命题“有的汽车比一些火车跑得快”的含义:
    • “有的汽车”表示存在一个x,使得x是汽车,这可以用xC(x)来表示。
    • “比一些火车跑得快”,这里需要引入另一个变量y表示火车,即存在一个yy是火车,并且x跑得比y快,这可以表示为y(T(y)Q(x,y))
    1. 然后将两部分结合起来:
    • 因为要同时满足x是汽车并且存在火车y使得xy快,所以用逻辑连接词xC(x)y(T(y)Q(x,y))连接起来,得到x(C(x)y(T(y)Q(x,y)))。 具体书写步骤如下:
    • 步骤一:表示存在汽车,即xC(x)
    • 步骤二:对于存在的汽车x,表示存在火车y使得xy快,即y(T(y)Q(x,y))
    • 步骤三:将上述两步用连接起来,得到最终表达式x(C(x)y(T(y)Q(x,y)))
  7. Gnm条边的无向图,若G连通且m=?,则G是无向树。

    答案n1

    这里的n阶指的是n个顶点,所以是n个顶点m条边,根据树的性质,可以得到m=n1

  8. X={1,2,3}f:XXg:XXf={1,2,2,3,3,1}g={1,2,2,3,3,3},则f1g=?gf=?

    答案{1,3,2,3,3,2}{1,3,2,1,3,1}

    1. 首先求f1
    • 已知f={1,2,2,3,3,1},那么f1={2,1,3,2,1,3}
    1. 然后求f1g
    • 对于f1g,先计算g(1)=2,再计算f1(2)=1,所以(f1g)(1)=1
    • 计算g(2)=3,再计算f1(3)=2,所以(f1g)(2)=2
    • 计算g(3)=3,再计算f1(3)=2,所以(f1g)(3)=2
    • 综上,f1g={1,1,2,2,3,2}
    1. 接着求gf
    • 对于gf,先计算f(1)=2,再计算g(2)=3,所以(gf)(1)=3
    • 计算f(2)=3,再计算g(3)=3,所以(gf)(2)=3
    • 计算f(3)=1,再计算g(1)=2,所以(gf)(3)=2。 综上,gf={1,3,2,3,3,2}。 所以f1g={1,1,2,2,3,2}gf={1,3,2,3,3,2}
  9. 不能再分解的命题称为原子命题,至少包含一个联结词的命题称为复合命题

  10. 连通无向图G含有欧拉回路的充分必要条件是G中所有顶点的度数均为偶数

  11. 设集合A={,{a}},则A的幂集为,|P(A)|=?

    答案P(A)={,{},{{a}},{,{a}}},4。

    幂集的大小为2n,其中n为元素个数。

  12. G=V,EG=V,E为两个图(同为无向图或有向图),EEVV,则称GG的子图,EEV=V,则称GG的生成子图。

二、单选题 (本大题共 12 小题,每小题 2 分,共 26 分)

  1. 下列命题公式为重言式的是(B) A. (p¬p)q B. p(pq) C. q¬q D. (pp)q

    答案:B。重言式,即永真式。

    1. 对于选项 A:
    • 公式(p¬p)q,其中p¬p恒为真(排中律),但是当q为假时,整个式子为假,所以它不是重言式。
    1. 对于选项 B:
    • 公式p(pq),当p为真时,pq一定为真,根据蕴含式的定义,前件真后件真,整个式子为真;当p为假时,根据蕴含式的定义,前件假整个式子为真。所以无论pq取何值,该公式都为真,它是重言式。
    1. 对于选项 C:
    • 公式q¬q恒为假(矛盾律),所以它不是重言式。
    1. 对于选项 D:
    • 公式(pp)qpp恒为真,但是当q为假时,整个式子为假,所以它不是重言式。
  2. 下列语句中为命题的是(D) A. 你好吗? B. 人有6指。 C. 我所说的是假的。 D. 明天是晴天。 答案:D。

    1. 首先分析命题的定义:
    • 命题是能够判断真假的陈述句。
    1. 然后看选项 A:
    • “你好吗?”这是一个疑问句,不是陈述句,所以它不是命题。
    1. 再看选项 B:
    • “人有6指”,这句话虽然是陈述句,但是它的真假取决于具体情况,在没有明确的语境或定义下,无法确定其真假,所以它不是命题。
    1. 接着看选项 C:
    • “我所说的是假的”,这句话会产生自指的矛盾情况,无法确定其真假,所以它不是命题。
    1. 最后看选项 D:
    • “明天是晴天”是一个陈述句,并且在给定的时间(明天)到来后,可以判断其真假,所以它是命题。
  3. D=V,E为有向图,V={a,b,c,d,e,f}E={a,b,b,c,a,d,d,e,f,e}是(C) A. 强连通图 B. 单向连通图 C. 弱连通图 D. 不连通图

    答案:注意是有向图,选择 C。

    1. 首先明确各种连通图的定义:
    • 强连通图:在有向图中,如果对于每一对顶点uv,都存在从uv和从vu的路径,则称该有向图是强连通图。
    • 单向连通图:如果对于有向图中的任意两个顶点uv至少存在从uv或者从vu的路径,则称该有向图是单向连通图
    • 弱连通图:将有向图的所有有向边替换为无向边后得到的无向图是连通的,则称该有向图是弱连通图
    • 不连通图:如果图中存在顶点对,它们之间没有路径相连(无论是有向路径还是无向路径,在有向图中考虑无向路径时是将边视为无向的情况),则称该图是不连通图。
    1. 然后分析给定的有向图D
    • 把有向图D的有向边替换为无向边后,得到的无向图是连通的(可以通过简单观察或者尝试从任意一个顶点出发能否到达其他顶点来判断,例如从a可以通过bc到达e,从a也可以通过d到达e等)。
    • 但是,在有向图D中,例如从ea就不存在路径,不满足强连通图的定义;同时也不满足单向连通图的定义(存在一些顶点对,既没有从一个到另一个的有向路径,也没有反向的有向路径)。
  4. 集合A={a,b,c}上的下列关系矩阵中符合偏序关系条件的是() A. (1010011000111101) B. (101010101) C. (101110001) D. (111010011)

    答案:D。

    偏序关系的定义及性质

    1. 自反性:对于集合A中的任意元素a,都有(a,a)R。在关系矩阵中体现为主对角线元素全为1
    2. 反对称性:如果(a,b)R(b,a)R,那么a=b。在关系矩阵中,如果ijaij=1,则aji=0
    3. 传递性:若(a,b)R(b,c)R,则(a,c)R。从关系矩阵角度看,如果aij=1ajk=1,那么aik=1

    对选项 A 的分析

    关系矩阵(1010011000111101)

    • 主对角线元素全为1,满足自反性。
    • 满足反对称性。
    • 传递性不满足,缺少1,2的关系

    对选项 B 的分析

    关系矩阵(101010101)

    • 主对角线元素全为1,满足自反性。
    • i=1j=3a13=1,当i=3j=1a31=1,且13,不满足反对称性,所以选项 B 不符合偏序关系条件。

    对选项 C 的分析

    关系矩阵(101110001)

    • 主对角线元素全为1,满足自反性。
    • 满足反对称性。
    • 缺少传递性。

    对选项 D 的分析

    关系矩阵(111010011)

    • 主对角线元素全为1,满足自反性。
    • 对于反对称性,不存在ij使得aij=1aji=1的情况,满足反对称性。
    • 对于传递性,例如a12=1a23=0,此时不需要考虑a13是否为1(因为传递性的前提是两个关系都存在);再看a13=1,可以看作是因为a11=1a13=1(从aa再到c的一种特殊传递情况,因为a到自身的关系总是存在的);其他情况也都满足传递性。所以选项 D 符合偏序关系条件。
  5. A={1,2,3}A上二元关系S={1,1,1,2,3,2,3,3},则S是(B) A. 自反关系 B. 传递关系 C. 对称关系 D. 反自反关系 答案:B

    1. 首先明确各种关系的定义:
    • 自反关系:对于集合A中的每一个元素a,都有(a,a)R
    • 传递关系:如果(a,b)R(b,c)R,那么(a,c)R
    • 对称关系:如果(a,b)R,那么(b,a)R
    • 反自反关系:对于集合A中的每一个元素a,都有(a,a)R
    1. 然后分析关系S
    • 对于自反关系,集合A={1,2,3},但是(2,2)S,所以S不是自反关系。
    • 对于传递关系,有(1,2)S(3,2)S,不存在(1,3)这种情况,不会出现违背传递性的情况,其他元素对之间也满足传递性定义(例如(1,1)S(1,2)S(1,2)S满足传递;(3,2)S(3,3)S,不存在(2,3)S所以也满足传递等),所以S是传递关系。
    • 对于对称关系,(1,2)S,但是(2,1)S,所以S不是对称关系。
    • 对于反自反关系,因为(1,1)S(3,3)S,所以S不是反自反关系。
  6. A={a,b,c,d}A上的等价关系R={a,b,b,a,c,d,d,c}IA,则对应于RA的划分是(D) A. {{a},{b,c},{d}} B. {{a,b},{c},{d}} C. {{a},{b},{c},{d}} D. {{a,b},{c,d}}

    答案:D。注意等价关系的三个前提:自反性,对称性,传递性

    1. 首先明确等价关系与划分的关系:
    • 等价关系会将集合划分为互不相交的子集(等价类),使得同一子集中的元素相互等价(在关系R下)。
    1. 然后分析等价关系R
    • 对于a,b,b,aR以及IA中包含a,a,b,b,这说明ab是等价的,它们属于同一个等价类,即{a,b}
    • 对于c,d,d,cR以及IA中包含c,c,d,d,这说明cd是等价的,它们属于同一个等价类,即{c,d}
    1. 最后看选项:
    • 选项 A 中{b,c}不符合ab等价、cd等价的情况。
    • 选项 B 中{c}{d}没有将cd放在同一个等价类中。
    • 选项 C 中没有体现出ab等价、cd等价形成的等价类。
    • 选项 D 中{{a,b},{c,d}}正确地反映了由等价关系R确定的A的划分。
  7. 以下非负整数列可简单图化为一个欧拉图的是(D) A. {2,2,2,2,0} B. {4,2,6,2,2} C. {2,2,3,4,1} D. {4,2,2,4,2}

    答案:D。

    1. 首先明确欧拉图的判定条件:
    • 一个无向图是欧拉图当且仅当该图是连通的且所有顶点的度数均为偶数。
    1. 然后分析每个选项所代表的图的度数序列:
    • 选项 A:{2,2,2,2,0},有一个顶点度数为0,这意味着该图不连通(孤立顶点),所以不能是欧拉图。
    • 选项 B:{4,2,6,2,2},所有顶点度数之和为4+2+6+2+2=16,根据握手定理(在无向图中,所有顶点的度数之和等于边数的两倍),边数为16÷2=8。但是如果尝试构建这样一个图,会发现无法满足所有顶点度数的要求(例如,一个顶点度数为6,很难在只有8条边且其他顶点度数较小的情况下构建出符合条件的图),所以该序列不能简单图化为欧拉图。
    • 选项 C:{2,2,3,4,1},其中有顶点度数为31,不满足所有顶点度数均为偶数的条件,所以不能是欧拉图。
    • 选项 D:{4,2,2,4,2},所有顶点度数均为偶数,并且可以尝试构建出一个连通的图满足这些度数要求(例如,一个五边形,其中两个不相邻顶点之间再加两条边,就可以使五个顶点的度数分别为4,2,2,4,2),所以该序列可以简单图化为欧拉图。
  8. 设论域D={a,b},与公式xA(x)等价的命题公式是(C) A. A(a)A(b) B. A(a)A(b) C. A(a)A(b) D. A(b)A(a)

    答案:C。

  9. 一棵树有34度顶点,42度顶点,其余都是树叶,求这棵树有多少个树叶顶点(B) A. 12 B. 8 C. 10 D. 13

    答案:B。使用握手定理解决即可。

    1. 首先设树叶顶点的个数为x
    2. 然后根据树的性质,树的边数m=n1(其中n是顶点数),以及握手定理(所有顶点的度数之和等于边数的两倍)来计算。
    • 已知有34度顶点,其度数和为3×4=12;有42度顶点,其度数和为4×2=8;树叶顶点度数为1x个树叶顶点度数和为x
    • 那么所有顶点的度数之和为12+8+x
    • 顶点数n=3+4+x=7+x,边数m=n1=6+x
    • 根据握手定理可得12+8+x=2(6+x)
    1. 接着解方程:
    • 12+8+x=12+2x
    • 移项可得2xx=12+812
    • 解得x=8
  10. ABC三个人猜测甲乙丙三个球队中的冠军。各人的猜测如下: A: 冠军不是甲,也不是乙。 B: 冠军不是甲,而是丙。 C: 冠军不是丙,而是甲。 已知其中有一个人说的完全正确,一个人说的都不对,而另外一人恰有一半说对了。据此推算,冠军应该是(A) A. 甲 B. 乙 C. 丙 D. 不确定

  11. 如第 11 题图所示各图,其中存在哈密顿回路的图是(C)

    答案:C

    • A,存在一个孤立点没有被访问,所以不行。

    • B,中间点必须访问两次,不行。

    • C,可以直接沿着正方形四条边进行访问。

    • D,必须经过中间点,所以不行。

    这是一道关于判断图中哪些图存在哈密顿回路的题目,答案是 (C)。

    解析

    1. 哈密顿回路的定义
    • 哈密顿回路是指在一个图中,从一个顶点出发,经过图中每个顶点恰好一次,最后回到起始顶点的路径。
    1. 对各选项的分析
    • 选项 (A)
    • 这是一个三角形加上一个孤立点。由于存在孤立点,无法形成经过所有顶点的回路,所以不存在哈密顿回路。
    • 选项 (B)
    • 这是一个带有交叉线的四边形。无论从哪个顶点出发,在经过所有顶点且仅经过一次的情况下,都无法回到起始顶点形成回路。例如,从左上角顶点出发,经过其他三个顶点后,无法再回到左上角顶点形成回路,所以不存在哈密顿回路。
    • 选项 (C)
    • 这是一个完整的四边形。可以很容易地找到哈密顿回路,例如按照顺时针或逆时针方向依次经过四个顶点,最后回到起始顶点,所以存在哈密顿回路。
    • 选项 (D)
    • 这是一个类似蝴蝶结形状的图。在尝试寻找哈密顿回路时会发现,无论从哪个顶点出发,都无法在经过每个顶点恰好一次的情况下回到起始顶点。例如,从上方中间顶点出发,经过其他顶点时,总会有顶点无法在满足条件的情况下被访问到,所以不存在哈密顿回路。
  12. C(x):x是国家级运动员,G(x):x是健壮的,则命题“没有一个国家级运动员不是健壮的”可符号化为¬x(C(x)¬G(x))

三、计算题(30 分)

  1. 用等值演算法求取求下列公式:((P\rarrQ)\rarr(P\orQ))的合取范式。

(P\orQ)\rarr(P\orQ)(P\orQ)\or(P\orQ)(P\andQ)\or(P\orQ)((P\andQ)\orP)\orQ((P\orP)\and(Q\orP))\orQ(Q\orP)\orQP\orQ

  1. G如下图所示,求图G的最小生成树。(图略,可根据边的权重选择合适的边构建最小生成树,此处省略具体过程)

  2. 有向图D如图所示,求D的关联矩阵M(D)。(图略,根据有向图关联矩阵的定义写出矩阵,此处省略具体矩阵内容)

    答案:-1 表示起点,1 是终点。

    横坐标表示的是edge,纵坐标表示的是vertix

  3. 化简表达式

    (((A(BC))A)(B(BA)))(CA)

    答案

    BA=BAB=BA,故B(BA)=BBA=BA

    1. 首先化简B(BA)
    • 根据集合差的定义,B(BA)=B(BA)
    • 又因为BA=BA,所以BA=BA=BA
    • B(BA)=B(BA)=(BB)(BA)=BA
    1. 然后化简(A(BC))A
    • 根据分配律(A(BC))A=(AA)((BC)A)=A((BC)A)
    • 因为(BC)A=(BC)A,所以(A(BC))A=A((BC)A)=A(因为A(AX)=A,这里X=(BC))。
    1. 接着将化简后的结果代入原式:
    • 原式变为(A(BA))(CA)
    • 根据分配律(A(BA))=(AB)(AA)=(AB)A=A(因为ABA取交还是A)。
    • 所以原式变为A(CA)
    • 又因为CA=CA,所以A(CA)=A(CA)=(AA)C=C=。 综上,化简结果为
  4. R={2,1,2,5,2,4,3,4,4,4,5,2},求r(R)s(R),并作出它们及R的关系图。

    答案

r(R)=RIA={2,1,2,5,2,4,3,4,4,4,5,2,1,1,2,2,3,3,4,4,5,5}s(R)=RR1={2,1,1,2,2,5,5,2,2,4,4,2,3,4,4,3,4,4}

  1. r(R)(自反闭包)
  • 定义:设R是集合A上的关系,r(R)=RIA,其中IA={a,a|aA}A上的恒等关系。
  • 已知R={2,1,2,5,2,4,3,4,4,4,5,2},假设A={1,2,3,4,5}(因为R中的元素涉及到这些数字)。
  • 那么IA={1,1,2,2,3,3,4,4,5,5}
  • 所以r(R)=RIA={2,1,2,5,2,4,3,4,4,4,5,2,1,1,2,2,3,3,4,4,5,5}
  1. s(R)(对称闭包)
  • 定义:设R是集合A上的关系,s(R)=RR1,其中R1={b,a|a,bR}
  • 对于R={2,1,2,5,2,4,3,4,4,4,5,2},其逆关系R1={1,2,5,2,4,2,4,3,4,4,2,5}
  • 所以s(R)=RR1={2,1,1,2,2,5,5,2,2,4,4,2,3,4,4,3,4,4}
  1. 关系图绘制
  • 关系R的关系图
  • 用五个点分别表示12345
  • 对于2,1,从点2画箭头指向点1;对于2,5,从点2画箭头指向点5;对于2,4,从点2画箭头指向点4;对于3,4,从点3画箭头指向点4;对于4,4,从点4画一个自环;对于5,2,从点5画箭头指向点2
  • 关系r(R)的关系图
  • R的关系图基础上,再给点12345分别加上自环(因为r(R)包含恒等关系)。
  • 关系s(R)的关系图
  • R的关系图基础上,对于R中的每一个有序对a,b,如果R中没有b,a,则添加从b指向a的箭头。例如,因为R中有2,1,添加从1指向2的箭头;因为R中有2,5,已有5,2,不用添加;因为R中有2,4,添加从4指向2的箭头;因为R中有3,4,添加从4指向3的箭头。

五、证明题(22 分)

  1. 构造下面推理的证明:

    前提:

    p\orq,p\rarrr,s\rarrt,s\rarrr,t

    结论:q

    答案:总结思路就是从t\rarrs\rarrr\rarrp\rarrq

    • t前提引入
    • s\rarrt前提引入
    • s取拒式(利用s\rarrt的逆否命题:t\rarrs
    • s\rarrr前提引入
    • r假言推理
    • p\rarrr前提引入
    • p取拒式
    • p\orq前提引入
    • q析取三段论
  2. A={1,2,3,4},在A×A上定义的二元关系Ru,v,x,yA×A,u,vRx,yu+y=x+v.

    证明RA×A上的等价关系。

    答案

    • 自反性:取u,vA×A

      u+v=u+v

      u,vRu,v

      故自反性得证。

    • 对称性:u,vx,yA×Au,vRx,y

      u+y=x+v

      x+v=u+y

      x,yRu,v

      故对称性得证。

    • 传递性:

      u,vx,ym,nA×Au,vRx,y,x,yRm,n

      u+y=v+x,x+n=y+m

      uv=xy,xy=mn

      uv=mn

      u+n=m+v

      u,vRm,n

      故满足传递性。

  3. 已知:A,B,C是三个集合,证明A(BC)=(AB)(AC)

    答案

    • x(A(BC))
    • x(A(BC))
    • xA\andx(BC)
    • xA\and(xB\andxC)
    • xA\andxB\andxA\andxC
    • x((AB)\and(AC))
    • 原命题得证。
  4. 无向图G=V,E,且|V|=n,|E|=m, 试证明以下两个命题是等价命题:

    1)G 中每对顶点间具有唯一的通路

    2)G 连通且 n=m+1

    证明

    1. 首先证明1)2)
    • 假设G中每对顶点间具有唯一的通路。
    • 证明G连通:因为每对顶点间都有通路,所以G是连通图。
    • 证明n=m+1
    • n进行归纳。
    • n=1时,m=0,此时n=m+1成立。
    • 假设当n=k时命题成立,即对于有k个顶点的满足条件的图Gk,有mk=k1
    • n=k+1时,在图G中任取一条边e={u,v},由于G中每对顶点间具有唯一的通路,去掉边e后,G变成两个连通分支G1G2,设|V(G1)|=n1|V(G2)|=n2,且n1+n2=k+1
    • 由归纳假设,|E(G1)|=n11|E(G2)|=n21
    • 而原来的图G的边数m=(n11)+(n21)+1=n1+n21=(k+1)1,即m=n1,也就是n=m+1
    1. 然后证明2)1)
    • 假设G连通且n=m+1
    • 反证法证明每对顶点间具有唯一的通路:假设存在一对顶点uv,它们之间有两条不同的通路P1P2
    • C=P1P2C中必存在圈。
    • C中的圈有l个顶点,l3,从G中去掉C中的一条边e,得到的图Ge仍然是连通的。
    • Gen个顶点和m1条边,且n(m1)=nm+1
    • 因为n=m+1,所以nm+1=2,这与树的性质n=m+1矛盾(因为去掉边后若还连通就不是树了,树中任意两点间有唯一通路)。
    • 所以G中每对顶点间具有唯一的通路。 综上,两个命题是等价命题。