关于二分图根积和串接的优美性

定义1 设H是有m个顶点h_i(1≤i≤m)的树,令B={图G_■|1≤i≤m,G_i∩H=φ,G_■∩G_■=φ,i≠j},设 X_i∈V(G_■)为G_■的根.所谓 H 与B的根积是把H的顶点 h_j与G_■的顶点 x_■(1≤i≤m)分别叠合起来所得的图,记为H(B).若G_■(1≤i≤m)均同构于二分图G,G_■的根X_■是G中任意指定的同一个顶点 X 的同构象,则记H(B)为H(G).     

竞赛图中的完美对集

Lichiardopol在离散数学-竞赛图中经过给定的0,1,2个公共顶点的圈一文中提出以下两个公开问题;对于阶为2n+1的正则竞赛图T,(a)对任意的一个顶点w,是否存在n个有向三角形Ti生成T,且使得V(Ti)∩V(Tj)=w(1≤i相似文献   

一种场站设置问题

研究了如下一种场站设置问题:设S是欧空间Rm中由有限个点A1,A2,…,An组成的集合,d(Ai,Aj)表示点Ai和Aj之间的距离.令σ(s)=∑d(Ai,Aj),d(S)=min {d(Ai,Aj)｝,l≤i＜j≤n 1≤i≠j≤nμ(m,n)=σ(S)/d(S)(S(∈) Rm,｜...     

Hamilton有向图的一个新的充分条件

设D是n(≥2)阶强连通有向图.猜想:如果D中每一对不相邻且有公共外邻或公共内邻的顶点x,y都有d(x) d(y)≥2n-1,那么D是Hamilton有向图.文章证明了当n≥7时,若D中每一个不相邻且有公共外邻或公共内邻的顶点x,y都有d(x) d(y)≥(5n)/2-5,则D是Hamilton有向图.当3≤n≤6时,存在非Hamilton有向图D满足D中每一对不相邻且有公共外邻或公共内邻的顶点x,y都有d(x) d(y)≥(5n)/2-5.     

正则竞赛图的有向生成三角形

2008年N.Lichiardopol在离散数学-竞赛图中经过给定0,1,2个公共顶点的圈.一文中提出以下公开问题:阶为2n+1的正则竞赛图T,对于任意的x∈V(T)是否存在n个有向三角形Ti使得V(Ti)∩V(Tj)=x(1≤i≤j≤n).文章证明了对于阶数为5,7,9的正则竞赛图,该问题答案是肯定的.     

笛卡尔积图的2-距离色数

图G(V,E)的2-距离染色是指正常的顶点染色,且距离不大于2的任意两个顶点着不同的颜色.给出了笛卡尔积图的一个2-距离色数的可达界,即Δ(G) Δ(H) 1≤χ2(G×H)≤2χ(G)χ2(H),以及一些特殊笛卡尔积图的2-距离色数,说明此界可达.     

完全立方Halin图的2-距离着色

图G的2-距离着色是正常的顶点着色,并且使G中距离不大于2的任意两个顶点着不同的颜色.图G的2-距离色数是图G的所有2-距离着色中所用色数的最小者,记为χ2d(G).探讨了完全立方Halin图Hn的2-距离着色,并得χ2d(H0)=4,5≤χ2d(Hn)≤6(n≥1).     

恰有d个顶点带环的本原有向图的公共后继的界

如果存在正整数p,使有向图G中任一有序顶点对u和v都有长为p的途径,则有向图G称为本原有向图．设Pn(d)是n(n≥3)阶恰有d个顶点带环的本原有向图的集合,LG(k)是本原有向图G的k-公共后继(k-c．c．),2≤k≤n;又设L(n,d,k)=max|LG(k)|G∈Pn(d)|,由此得到了k-公共后继的界：n-[d/2]≤L(n,d,k)≤n-1,1≤d≤n．     

图C2m×Pn与C2m×Cn的邻点可区别非正常边染色

设简单图G和图H的顶点集分别为V(G)={u1,u2,…,um}和V(H)={v1,v2,…,vn}.所谓G和H的Cartesian积G×H是指这样的一个图,其顶点集和边集分别为V(G×H)={wij|i=1,2,…,m,j=1,2,…,n},E(G×H)={wijwrs|i=r,vjvs∈E(H)或j=s,uiur∈E(G)}.在这篇文章里,我们讨论了笛卡儿积图C2m×Pn和C2m×Cn的邻点可区别边非正常边染色,并给出了相应色数.     

判断k-可序哈密顿-连通图的新条件

具有n个顶点的图G(n≥3)是k-可序哈密顿-连通的(k是整数,且2≤k≤n),如果对于G中每一个具有k个不同顶点的可序集合S={v1v2,…,vk},都存在G中的哈密顿路P包含S且不改变其中元素的次序.本文证明了:对于具有n个顶点的图G,u、v是G中任意两个不相邻的顶点,且d(u)+d(v)≥n+1.如果G是「k+1/2﹁-连通的k-可序图,k是整数且2≤k≤n/12,则G是k-可序哈密顿-连通图.     

独立集中具有最小特定度和的点的上可嵌入图类(英)

结合边连通度，探讨了独立集中具有最小特定度和的点的上可嵌入图.得到了下列结果. (1)设G,是一个2-边连通简单图且满足条件:对任意一个G的3-独立集I, ∨x_i ,x_j ∈I (i,j = 1,2,3), d(x_i ,x_j)≧3 (1 ≦ i ≠ j ≦ 3) =>∑_{i = 1}³ d(x_i) ≧ v + 1(v = | V(G)|}), 则G是上可嵌入的;(2)设G是一个3-边连通简单图且满足条件:对任意一个G的6-独立集I, ∨x_i ,x_j ∈I (1≦i,j≦6), d(x_i,x_j) ≧3(1 ≦ i ≠ j ≦ 6) => ∑_{i = 1}⁶ d(x_i) ≧ v + 1(v = | V(G)|), 则G是上可嵌入的.     

一个有较大倒数和的B2(i≠j)序列

如果所有的两项和ai aj都不同,就称正整数序列a1＜a2＜…是一个B2-序列.Mian-Chwla序列是用贪婪算法得到的B2-序列,它的倒数和S*曾被猜测为所有B2-序列倒数和的最大值.根据是否允许i=j,相应有两个问题.在允许i=j时,张振祥证明了S*＜2.1596及M＞2.1597,从而推翻了这个猜测.本文研究不允许i=j(或简称i≠j)的情形.我们给出一个有较大倒数和的B2(i≠j)序列:它的前9项由贪婪算法得到,第10项是54,从第11项起继续用贪婪算法.我们新序列的前200项倒数和大于Main-Chowla(i≠j)序列的倒数和.     

关于(H,η)单调算子的非线性集值算子包含的迭代算法

引进了关于H和G的强单调性概念,在Hilbert空间中研究了新的一类关于( H,η)单调算子的非线性集值算子包含.应用与( H,η)单调算子相关的预解算子技巧提出了一个迭代算法逼近其解,并且讨论了由此算法产生的迭代序列的收敛特征.     

积分不等式(Ⅰ)

本文最初欲把Ｂｅｌｍａｎ不等式推广成：已知φ（ｘ）≤Ｃ（ｘ）＋Ｋ１（ｘ）∫ｘａＨ１（ζ）φ（ζ）ｄζ＋Ｋ２（ｘ）∫ｘａＨ２（ζ）φ（ζ）ｄζ（其中：Ｋｉ（ｘ）≥０,Ｈｉ（ｘ）≥０,ｉ＝１,２）,求适合上述不等式的φ（ｘ）的最优上界Ψ（ｘ）（ｘ≥ａ）。但后来证明这个最优上界Ψ（ｘ）是不能用初等方法求出的,只知道Ψ（ｘ）是存在的且适合积分方程：Ψ（ｘ）＝Ｃ（ｘ）＋Ｋ１（ｘ）∫ｘａＨ１（ζ）Ψ（ζ）ｄζ＋Ｋ２（ｘ）∫ｘａＨ２（ζ）Ψ（ζ）ｄζ。把此结论加以全面的推广即得到本文在高维向量空间中的多变量线性积分不等式     

广义r-部完全超图的边色数

研究了广义r-部完全超图的边色数的问题.在r-部完全超图与t-一致完全超图的着色基础上,确定一类特殊的广义r-部完全超图的边色数,对一般的广义r-部完全超图的边色数给出了上界,推广了r-部完全超图与t-一致完全超图的着色结论.      

二维两阶不定椭圆问题的有限体积元方法的两层网格算法

对二维两阶不定椭圆问题的基于P1非协调元的有限体积元方法给出了两层网格算法,并得到在H1范数意义下两层网格算法的收敛性估计:‖uh-uh‖1,h≤CH2‖f‖1,‖u-uh‖1,h≤C(h+H2)‖f‖1。     

一类具有转向点超曲面的奇摄动椭圆型方程边值问题

讨论了n维空间中如下一类具有转向点超曲面的奇摄动椭圆型方程的边值问题Lεu≡εLu ∑^ni=1fi(x1,……,xn)Эu/Эxi g(x1,……,xn)u=0,(x1,……,xn)∈Ω,u（x1,……,xn)│ЭΩ1=φ1(x1,……,xn-1),ai≤xi≤bi,u(x1,……,xn)│ЭΩ2=φ2(x1,……,xn-1),ai≤xi≤bi。其中：ε为一正参数,且L=∑ni,j=1aij(x1,……,xn)Э^2/ЭxiЭxj(aij=aji),∑ni,j=1aijξiξj≥λ∑ni=1ξ^2i,任意ξi∈R,i=1,2,……,n,λ＞0。利用多重尺度法和比较定理、就形坐标和抛物柱函数,研究了该边值问题解的渐近性态。     

关于一不定方程组的解

讨论不定方程组a2x^2-a1y^2=a2-a1,a3y^2-a2z^2=a3-a2,其中自然数a1,a2,a3满足任两数之积与1之和均为平方数.利用文献[4]的方法,给出了此不定方程组满足x2≡1（m oda1）的非平凡正整数解.     

惯量任意的符号模式

矩阵A的特征值的集合(含重数)记为σ(A),A的惯量是指三元有序数组i(A)=(i (A),i-(A),i0(A)),其中i (A),i-(A)和i0(A)分别表示具有正,负,零实部特征值的个数.n阶符号模式矩阵S=(sij)是指元素取自{1,-1,0}或者{ ,-,0}的矩阵,S的定性矩阵类是指集合Q(S)={A=(aij)∈Mn(R):对所有的i和j,sign(aij)=sij}.S的惯量是指集合i(S)={i(A):A∈Q(S)}.若对任意满足n1 n2 n3=n的非负三元数组(n1,n2,n3),都有(n1,n2,n3)∈i(S),则称符号模式S为惯量任意模式.考虑n阶符号模式Kn=(kij)n×n:当1≤j-i≤n-2或i=j=n时,kij=1;当1≤i-j≤n-2或i=j=1时,kij=-1;当|i-j|=n-1时,kij可以取任意固定值;其余情形时,kij=0.本文证明了Kn(n≥3)是惯量任意模式.     

货郎问题求解算法分析

介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。