2类图完美匹配数的计算

一般图的完美匹配计数问题是NP-难问题。本文用划分、求和及嵌套递推的方法给出了2类特殊图完美匹配数目的显式表达式,所用的方法也开辟了得到一般的有完美匹配图的所有完美匹配数目的可能性。σ(n)和g(n)分别表示图3-nC6,3和2-nK3,3的完美匹配的数目。证明σ(n)=(3+3~(1/2))/6·(4+23~(1/2))n+(3-3~(1/2))/6·(4-23~(1/2))~n,g(n)=(41+5(41)~(1/2))/82·(7+)41)~(1/2)/2)~n+(41-5(41)~(1/2))/(82)·(7-(41)~(1/2)/2)~n。     

图的第二个最小特征值的界

设 G 是 n 个顶点的简单图,λ_(n-1)(G)为 G 的第二个最小特征值。G 的非孤立点形成的图记为 G_1,V(G_1)=s,(3≤s≤n)。本文主要证明了:a.若 G_1不是完全偶图,则λ_(n-1)(G)≤λ_(s-1)(K_(2,s-2)-(?)),等式成立(?)G_1(?)K_(2,s-2)-e。其中图 K_(2,s-2)-e 为完全偶图 K_(2,s-2)去掉一边 e而得到的图 b.若 G_1既不是完全偶图.又不是 K_(2,s-2)-e,则λ_(n-1)(G)<-2~(1/2)/2。     

s不超过6的无标号(n,n/2+s)-奇图的计数

一个图称为(n,m)-图,若|V(G)|=n且|E(G)|=m.一个奇图是指每个点的度都是奇数的图.给出了一种新的图同构的定义,计算并给出了不同构无标号(n,n/2+5)-奇图的结果,并对s=4,6给出了不同构无标号(n,n/2+s)-奇图的完整结果.     

图Kn-E(Kr),Kr(∪)Kn的整和数

Z表示所有整数的集合.一个有限子集S(∪)Z上的整和图是指图(S,E)中uv∈E当且仅当u+v∈S.图G是整和图,如果它同构于某个子集S(∪)Z上的整和图.图G的整和数是指使(G∪mK1)成为一个整和图时加入的孤立顶点的最少个数m.1994年Harary在[3]中提出了4个未决的问题,本文完整地回答了其中的第一个问题,即确定了图(Kn-E(Kr))的整和数.具体结论如下:ζ(Kn-E(Kr))={0(r=n,n-1)n-1(n-2≥r≥[2n/3]-1)3n-2r-4([2n/3]-1＞r≥n/2)2n-4([2n/3]-1＞n/2≥r≥2)其中n≥5,r≥2,[x]表示不小于x的最小整数.     

三角函数的基础圆法

对三角函数通常有直角三角形、坐标、单位圆和向量四种解释方法,不同的场合可以采用不同的解释方法。下而再介绍一种新的方法——基础圆法。〔角的概念〕如图1、2所示,数轴X’X在平面内绕原点O旋转,从正半轴OX的位置到终止位置OT所形成的几何图形称为角,记作∠XOT或α。依逆时针方向旋转转形成的角称为正角〔图1〕;依顺时针方向旋转所形成的角称为负角〔图2〕。〔平面基础圆系〕如图3所示,在平面直角也标系XOY中,分别以S(0,1/2)、S’(0,-1/2、c(1/2,0)、c,(-1/2,0)和O(0,0)为圆心,以单位长为直径和半径的圆分别称为正弦圆、负正弦圆、余弦圆、负余弦圆单位圆。这五个圆统称为基础圆。点A(0,1)和点B(1,0)分别你为正点和余点。这样的一套图形称为平而基础圆系。     

关于4连通图的容错直径和宽直径

容错直径和宽直径是度量网络可靠性和有效性的重要参数.对任意k连通图,它的容错直径Dk,不超过宽直径dk.本文证明:当G是4连通图时,若D3=2,d4≤{D4 1,8D4-17};若D3≥3,d4≤max{3D2(3D4-1/2D2-13/2) 1,2D2D3(D4-2) D2-D22 1,3D2(D3-1)(D4-2)-3/2D2-3/2D22 1}并且证明对n(n≥3)连通图,当Dn=2时,2≤dn≤3.     

最大度不小于7的图的星边色数的一个上界

定义了星边染色和星边色数X's(C),证明了若图G的最大度△≥7,则X's(G)≤[16(△-1)3/2].此结果包含了若图G是最大度△≥12的线图,则Xs(G)≤[16(△-1)3/2].     

小m条件下的联结数与分数(k,m)-消去图(英文)

设k,m为整数,其中k≥2,m≥0且k≥{2m-1,若k是奇数,2m-2,若k是偶数.本文证明:若图G满足n4k+1-4(k+1-2m)～(1/2),bind(G)((2k-1)(n-1))/(K(n-2)-2m+2),则G是分数(k,m)-消去图.当k是偶数时,若图G满足n4k+1-4(k+2-2m)～(1/2),bind(G)((2k-1)(n-1))/(K(n-2)-2m+3),则G是分数(k,m)-消去图.同时,本文所给结果在一定意思上是最好的.     

二维可定向流形的几个定理(英文)

给出了二维可定向流形的几个定理。 (K6-E(K3) )不能三胞腔嵌入二维可定向流形 ;若围长为g的 (p ,q) -连通图能G 2 Sk,则g >3 ,q 3(p +2k - 2 ) ,q 2 (p+2h - 2 ) ;n点k -正则图G能三胞腔嵌入Sh,则h=1+n(k - 6 ) / 12。     

图的L(d,1,1)-标号

给出了图L(d,1,1)-标号的一般性质. 对一般图G, 给出了构造L(d,1,1)-标号的一个算法, 证明了λ_d,1,1(G)≤Δ³-Δ²+dΔ. 对最大度Δ的树T, 证明了d+Δ-1≤λ_d,1,1(T)≤d+2Δ-2, 并且式中的上界与下界都是可达的. 此外, 对于两类特殊的树图： 拟正则树T_Δ及正则毛毛虫Cat_n, 给出了确切的L(d,1,1)-标号数, 其中d≥2.     

关于丢番图方程11x(x+1)(x+2)(x+3)=13y(y+1)(y+2)(y+3)

运用递推序列的性质及二次剩余的知识,证明了丢番图方程11x(x+1)(x+2)(x+3)=13y·(y+1)(y+2)(y+3)仅有4组非平凡整数解(x,y)=(23,22),(-26,22),(23,-25),(-26,-25).同时,给出了丢番图方程x²-143(y²+3y+1)²=-22的全部整数解.     

Fan定理的简捷证明

本文研究的图是简单图Ｇ ,限于本文的使用 ,记Ｆａｎ =ｍｉｎ{ｍａｘ{ｄ(ｘ) ,ｄ( ｙ) }|ｄ(ｘ ,ｙ) =2 }.Ｆａｎ定理[1 ] 　 2连通ｎ阶图Ｇ ,Ｆａｎ≥ｎ/2 ,则Ｇ是哈密尔顿图 (Ｈ图 ) .证明　假设Ｇ不是Ｈ图 .记Ｇ的一最长圈为Ｃｍ:Ｘ1 Ｘ2 …ＸｍＸ1 ,因Ｇ是 2连通的 ,记Ｘｉ,Ｘｊ 为和Ｇ -Ｃｍ 的一分支Ｇ1 中 ｙ1 ,ｙ2 相邻的两点 ,且满足 {Ｘｉ+1 ,Ｘｉ+2 ,… ,Ｘｊ- 1 }中没有点和Ｇ1 中点相邻 .情况 1　ｄ( ｙ1 ) <ｎ/2 ,且ｄ( ｙ2 ) <ｎ/2 .此时由Ｆａｎ≥ｎ/2 ,知ｄ(Ｘｉ+1 )≥ｎ/2 ,ｄ(Ｘｊ- 1 )≥ｎ/2 ,因Ｃｍ 为最长圈 ,所以 ( …     

图的2-距离着色

简单图G(V,E)的2-距离着色是正常的顶点着色且距离不大于2的任意两个顶点着不同的颜色,给出了网格的2-距离色散,并通过运用线图构造了一类特殊图,从而证明了最大度为△的图G的二距离色数的界为16/5△2+8/3△+16/5≤x2d(G)≤min{△2+1,n}     

用圈刻画Clifford半群Cayley图可扩性

Γ=Cay(S,C)的11/2-可扩性和2-可扩性比1-可扩性性质更强,需要的条件也更复杂.对Γ是圈的Clifford半群Cay(S,C)图的11/2-可扩性和2-可扩性进行了刻画.     

上可嵌入图与次上可嵌入图的线性荫度

通过度再分配的方法研究上可嵌入图与次上可嵌入图的线性荫度,证明了最大度△不小于(4-3ε)~(1/3)且欧拉示性数ε≤0的上可嵌入图其线性荫度为「△/2」.对于次上可嵌入图,如果最大度△≥(4-3ε)~(1/3)且ε≤0,则其线性荫度为「△/2」.改进了文献[1]中最大度的的界.作为应用证明了双环面上的三角剖分图的线性荫度.     

范-条件与具有给定端点的最长路

令G是n阶2-连通图且d(u,v)=2 max{d(u),d(v)}≥n/2.设{x,y}不是G的2-割集.记最长的(x,y)-路的长度为p(x,y).本文证明了如下结论:(1)p(x,y)≥n-2;(2)若p(x,y)=n-2且P是最长的(x,y)-路中使得d(xp)最小的一条,那么d(xp)=2,3或者n/2,其中xp表示唯一一个不属于P的点.本文还刻画了3-连通且使得d(xp)=3的图.     

镇静钢钢锭模设计的图算方法

本文研究的是镇静钢钢锭模设计的图算方法。 在设计时先给出下列的技术条件:钢锭体积V(不包含帽部),高宽比α,宽厚比β,大、小面的锥度i_1和i_2,大面上尾部转角半径R_2,小面尾部转角半径R_1,直部横截面的园角半径r。所要求出的是,钢锭的高度H,大头断面的长、宽a_1、a_2、小头断面(直部与尾部相连处)的长、宽b_1,b_2。 文中求H的方程 h~3-ph-q=0,其中 h=H-δ, δ=1/3(i_1/η i_2/η)R_1 (*) i=(4-π/2-i_1)R_2~2/ξ (4-π/2-i_2)R_1~2/η (4-π)i~2/ξη, q=V/ξη,ξ=2β/α(1 β),η=2/α(1 β)。此外,我们也推出了计算钢锭尾部体积的公式 V_尾=b_1b_2h-2[f(h/R_1)R_1~2b f(h/R_2)R_2~2b_2],其中 f(k)=k-1/2k(1-k~2)~1/2-1/2sin~(-1)k, h是尾部高度。 最后,我们作出了解方程(＊)和计算尾部体积的计算图,利用这些图可以很方便并且很快地来完成钢锭模的设计工作。     

较大亏格曲面嵌入图的线性荫度

通过度再分配的方法研究嵌入到曲面上图的线性荫度.给定较大亏格曲面∑上嵌入图G,如果最大度Δ(G)≥((45-45ε)^(1/2)+10)且不含4-圈,则其线性荫度为[Δ/2],其中若∑是亏格为h(h>1)的可定向曲面时ε=2-2h,若∑是亏格为k(k>2)的不可定向曲面时ε=2-k.改进了吴建良的结果,作为应用证明了边数较少图的线形荫度.     

线图中2-因子分支数一些结果的改进

设G为一简单图,该文重点研究了图及其补图的线图中2-因子的分支数,改进了Nebesk■的一个结果,得出如下结论:阶数n≥5的简单图G,G和L(G)分别是G的补图和线图,存在一个图G′∈{G,■},线图L(G′)包含k个分支的2-因子,其中k=1,…,└(n-3)/4」.讨论了图及其补图的线图中2-因子分支的最大个数的界的问题,并给出了线图中存在一定分支数的2-因子的Chvtáal-Erds型条件,即对于阶为n的图G,如果k(G)≥a(G)-1,则L(G)中存在所有k个分支的2-因子,其中1≤k≤└n~(1/2)/3」.     

Met+H2O复合体系手性转变反应中间体电子激发表征

基于M06-2X理论方法, 在加有弥散函数的aug-cc-pVTZ基组水平上, 用含时密度泛函理论(TDDFT)方法进行电子激发计算, 给出隐式溶剂氯仿下Met(甲硫氨酸)+H₂O复合体系手性转变中第一基元反应中间体INT₁-S-Met-CHCl₃+H₂O分子体系的空穴-电子、自然跃迁轨道(NTO)和电荷密度差(CDD)分布等值面图, 并分析中间体激发态的性质及其电子结构. 结果表明： H原子迁移形成中间体, 引起Met分子体系结构发生显著变化; 基于NTO、空穴-电子和CDD等值面与空穴-电子数据分析对INT₁-S-Met-CHCl₃+H₂O分子体系激发态激发类型互认具有一致性.