UyHiP 趣题：几个特殊的强正则图

只有三个不同特征值的图
设图G是一个简单连通无向图、其邻接矩阵A的特征值称为G的特征值.图G的谱是指由G的所有特征值和它们对应的重数组成的集合.本文主要围绕图谱理论中的两个问题展开研究工作.第一个问题是除去完全二部图和强正则图,寻找只有三个不同的特征值的连通图.第二个问题是研究刻画第二大特征值不超过1的图.本文按照以下几个部分展开：本文的第一章介绍图论与图谱理论中的基本概念以及问题的研究背景.本文的第二章我们仅考虑非正则连通图.首先我们刻画了只有三个不同的特征值且其补图不连通的图,给出了只有三个不同特征值的图的阶,顶点度,特征值以及Perron-Frobenius特征向量的估计.我们证明了如果一个图和它的补图都恰好有三个不同的特征值,则此图只有两个不同的顶点度.其次我们重点研究了只有三个不同的特征值且恰有两个不同的顶点度的连通图,即所谓的强双正则图.主要的结果包括强双正则图的一些结构定理,构造出了一些新的强双正则图,刻画了已知的一类特殊的强双正则图以及给出了两类有无穷多个可行的强双正则图.最后,在已知的仅有有限个恰好有三个不同特征值和三个不同顶点度的图的基础上,我们又构造出了一个新的图.而且证明了一些具有特定的谱和顶点度的图是不存在的.本文的第三章我们证明了一个关于强双正则图的拟Neumaier定理,即证明了对于给定的正整数m,只有有限多个最小特征值不小于-m或者第二大特征值不超过m的非二部的强双正则图.本文的第四章我们确定出了只有三个不同特征值且第二大特征值不超过1的连通图,并且也确定出了只有三个不同的特征值且最小顶点度不大于6或者最大特征值不超过7的连通图.。

2002年4月离散数学试题答案第一篇：2002年4月离散数学试题答案 专注于收集各类历年试卷和答案更多试卷答案下载免费试听网校课程2002年4月离散数学试题答案课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)1.B2.D3.A4.A5.D6.D7.D8.C9.D10.B11.A12.A13.C14.B15.C二、填空题 16.0 17.10 18.单位元19.x∩yx∪y 20.入射满射21.［x］R=［y］R22.A(x)B(y)23.(M(x)→D(x))M(x)→D(x)24.可满足式永假式(或矛盾式)25.陈述句真值三、计算题⎧1⎪⎪126.M=⎨⎪1⎪0⎩⎧2⎪2⎪2M=⎨⎪2⎪1⎩442ij***10⎫⎪0⎪⎬1⎪1⎪⎭0⎫⎪1⎪⎬ 1⎪1⎪⎭∑∑Mi=1j=1=18, ∑Mij=6i=12G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，∀x∈P(A),xn=∅当n是奇数时，∀x∈P(A),x=x⊕于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n=∅⊕(｛a｝-1)n｛b｝n｛a｝n=∅⊕∅当n是奇数时，=∅n(｛a｝-1｛b｝｛a｝)n⊕｛a｝-n｛b｝n｛a｝n-1-1nnn=｛a｝｛b｝｛a｝⊕(｛a｝)｛b｝｛a｝-1-=｛a｝｛b｝｛a｝⊕｛a｝｛b｝｛a｝=∅28.(1)偏序关系R 的哈斯图为 专注于收集各类历年试卷和答案(2)B的最大元：无，最小元：无；极大元：2，5，极小元：1，3下界：4，下确界4；上界：无，上确界：无29.原式⇔(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命题为真的赋值是P=1,Q=0和P=1,Q=1 30.令e1=(v1,v3)，e2=(v4,v6)e3=(v2,v5)，e4=(v3,v6)e5=(v2,v3)，e6=(v1,v2)e7=(v1,v4)，e8=(v4,v3)e9=(v3,v5)，e10=(v5,v6)令ai为ei上的权，则a1取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=15 31.原式⇔┐(∀x1F(x1,y)→∃y1G(x,y1))∨∃x2H(x2)(换名)⇔┐∃x1∃y1(F(x1,y)→G(x,y1))∨∃x2H(x2)⇔∀x1∀y1┐(F(x1,y1)→G(x,y1))∨∃x2H(x2)⇔∀x1∀y1∃x2(┐(F(x1,y1)→G(x,y1))∨H(x2)四、证明题32.设T中有x片树叶，y个分支点。

假设你有n 枚外观完全相同的硬币，它们的重量分别为1g, 2g, 3g, …, ng 。

有意思的是，这一次，你已经知道了各枚硬币的重量，而且你也已经把重量值标在了这些硬币上。

但是，由于我不知道各枚硬币的重量，因此我希望你能向我证明，你所标的重量值是正确的（我知道这些硬币的重量是从 1 克到n 克，我只是不知道哪个硬币对应哪个重量）。

你唯一能用的工具就是一架天平。

每一次，你可以任意选择一枚或多枚硬币，放在天平的左侧，再从剩下的硬币中任意选择一枚或多枚硬币，放在天平的右侧（注意，你只能在天平上放硬币，不能放别的东西）。

一个有意思的问题是，为了向我证明你所标的重量值都是对的，你最少需要使用多少次天平？显然，为了证明n 枚硬币的重量标签的正确性，我们最多需要称n – 1 次。

先把硬币1 放在左边，把硬币 2 放在右边，让对方看到硬币 1 确实比硬币 2 要轻。

接下来，向对方验证硬币 2 确实比硬币 3 更轻，硬币 3 确实比硬币 4 更轻，等等。

称完n – 1 次后，我们就相当于给出了n 枚硬币的轻重顺序，因而它们只有可能分别是 1 克、 2 克、 3 克……。

我们还能做得更好吗？不妨让我们看看n 比较小的情况。

例如，当n = 4 的时候，利用上述方法可以 3 次完成验证，那么只用 2 次可以完成验证吗？仔细一想，你会发现真的可以！其中一种方法就是，先把硬币 1 和硬币 2 放在左边，把硬币 4 放在右边。

由于两枚硬币的重量之和小于第三枚硬币，这只可能是1 + 2 < 4 ，因此对方会相信，左边两枚硬币分别是 1 和 2 ，右边那枚硬币是4 ，没放上去的那枚硬币是 3 。

对方唯一不知道的就是，在左边两枚硬币中，究竟谁是 1 ，谁是 2 。

于是，我们只需要再称一下硬币 1 和硬币 2 ，问题就解决了。

不妨把证明n 枚硬币重量标签的正确性最少需要的称重次数记作B(n) 。

我们的问题就是：判断B(n) 是以什么级别增长的。

Hall定理正则⼆部图完美匹配相异代表系设S1,S2,⋯,S m是⼀族集合，它们的⼀个相异代表系为⼀个m维向量 (x1,x2,⋯,x m)满⾜：代表性：x i∈S i互异性：∀i≠j,x i≠x j相异代表系也简称为SDR对于⼀族指标J⊆[m]，我们定义它们的并 union(J) 为：union(J)=⋃j∈J S jHall定理有限集族S1,S2,⋯,S m存在SDR当且仅当HC成⽴，其中HC：∀J⊆[m],|union(J)|≥|J|（严谨性未知）笔者⼝胡的反证法：如果⼀个集合满⾜HC但是不存在SDR，那么⼀定存在⼀个S i，其中的元素⽆法选择，并且对于j≠i，S j中选择的元素⽆法更换，因为如果可以更换，那么我们相应的更换S k,k≠j,k≠i中的元素，直到更换⾄S i，即存在SDR，此时我们不选择S i，余下的集族不满⾜HC，⽭盾（正规证明）使⽤数学归纳法：定义⼀个指标族J临界，若 {S j:j∈J} 存在SDR，并且 |union(J)|=|J|空集与全集如果是临界指标族，那么称为平凡的临界指标族⾸先我们讨论S1,S2,⋯,S m不存在⾮平凡临界指标族显然当m=1 时成⽴，现在我们假设在⼩于m时均成⽴显然由HC得S m⾮空，我们选择⼀个元素x m∈S m，将S i(1≤i<m) ⾥的x m剔除，将此剔除后的集合的并函数设为 union′(J)注意到不存在⾮平凡临界指标族，所以之后对于J⊆[m−1]，有：|union′(J)|=|union(J)|+1≥|J|+1−1≥|J|满⾜了HC，之后构造SDR显然，证毕现在我们来讨论存在⾮平凡临界指标族的情况由上例的思想，我们显然可以将这⼀个⾮平凡临界指标族捆绑起来，然后从剩余的⾥⾯剔除掉这个指标族的并，然后由于J是临界的，我们直接展开即得1.设 (A1,A2,⋯,A m) 为 {1,2,⋯,n} 的⼀个⼦集组，且关联矩阵M=(m ij),m ij=1i∈A j 0i∉A j可逆，证明 (A1,A2,⋯,A m) 有SDR证：可逆⇒⾮降秩矩阵，证毕2. 01矩阵的最⼩覆盖数m等于最⼤匹配数M{证：匹配显然要找⼀对⾏与列都不同的 1，这⼀对 1 显然要⾄少 1 条线来覆盖，即m≥M然后我们设S i为⼀条横线上存在的 1 的位置，在满⾜最⼩覆盖的情况下，显然这东西满⾜HC，因此存在⼀个SDR，可推出M≥m，即m=M正则⼆部图完美匹配⼆部图G=X△Y具有覆盖了X的匹配当且仅当HC2成⽴，HC2：∀J⊆X,|N(J)|≥|J|其中对于⼀个图G=(V,E)，N(v)={u∈V:u∼v}，u∼v当且仅当有边连接它们不难发现这就是HC换了个⽪，证明也很显然定理：正则的⼆部图⼀定存在完美匹配设此⼆部图为G=X△Y，并且∀y∈Y,∃x∈X,x∼y设 deg(v)=k，其中 deg(v) 表⽰顶点v的度事实上如果G中存在孤⽴点，那么此图不存在边也就是说E=∅现在我们来证明 |X|=|Y|，不难发现∑x∈X deg(x)=∑y∈Y deg(y)，由此图正则即可得∀J∈X，F={e:e∈E,e f∈J,e t∈Y}，其中e f与e t分别是⼀条边的起点与终点则显然有 |F|=k|J|，|F|≤k|N(J)||N(J)|≥|J|，证毕Processing math: 100%。

离散数学题集1.下列语句不是命题的是( C )。

合代数A.黄金是非金属。

11.设S是自然数集，则下列运算中不满足交换律的是( B )。

B.要是他不上场，我们就不会输。

A.a*b=|a-b| B.a*b=ab C.他跑100米只用了10秒钟，你说他是不是运动健将呢? C.a*b=max{a,b} D.他跑100米只用了10秒钟，他是一个真正的运动健将。

D.a*b=min{a,b} 2.关于命题变元P和Q的大项M01表示( D )。

12.设图G′=<V′，E′>是图的生成子图，则必须( a )。

A.?P?QB.?P?Q A.V′=V B.V′?C.P??QD.P??Q V但E′=EC.E′=ED.E′?，,,3.公式(x)(y)(P(x,z)?Q(y))S(x,y)中的(x)的辖域是( B )。

E且V′?V，13.设有向图G有5个结点，4条边，且有一条有向路经过每A.(y)(P(x,z)?Q(y))B.P(x,z)?Q(y)C.P(x,z)D.S(x,z) 个结点一次，则图G满足的最大连通性是( )。

4.下列等价式不成立的是( D )。

A.不连通 B.弱连,通，,A.?(x)A(x)(x)?A(x),C.单侧连通 D.强连通，,B.?(x)A(x)(x)?A(x),14.一个连通图G具有以下何种条件时，能一笔画出:即从某,,,C.(x)(A(x)?B(x))(x)A(x)?(x)B(x),结点出发，经过图中每边仅一次回到该结点。

( A )。

,,,D.(x)(A(x)?B(x))(x)A(x)?(x)B(x)A.G没有奇数度结点B.G有1个奇数，,5.公式(x)(y)(P(x,y)?Q(z))?R(x)中的x( )。

A.只是约束变元度结点B.只是自由变元C.G有2个奇数度结点D.G没有或有2C.既是约束变元又是自由变元个奇数度结点D.既非约束变元又非自由变元二、填空题(每小题2分，共30分) 6.设A={a,{a}}，则下列各式正确的是( )。