超树的计数理论Ⅰ

作为超图理论的一个重要课题,简单树已推广到超树.对于简单标号树,巳有Cayley公式等一系列漂亮的结果[1].然而,对相应的超树计数理论迄今尚未见展开.我们试图建立相应超树计数理论,把简单标号树一系列公式推广到超树,本文是我们工作的第一部份. 一、基本定义设X={x_1,x_2…x_p}是有限集,ε={E_i|i=1,2,…q}是X的子集的一个簇,若E_i≠φ,1≤i≤q,且E_i=X,则称H=(X,ε)为一个超图.|X|=p称为超图的阶,X中的元     

关于r-超树的因子定理

树的概念分别由Ljamin 及 Bolloba’s等人在超图中做了不同的推广,他们研究了超树的顶点数与边数的关系及复盖数等。本文中的γ-超树是 Ljamin超树的特例.文中给出了一个γ-超树有1-因子的充分必要条件,推广了Chungphaisam关于树的因子定理. 本文中未加说明的记号和述语皆见[4].超图H=(X,E)的秩γ(H)=max|Ei|.超图H=(X,E)的圈是一个顶点和边的交错序列{x_1,E_1,x_2,E_2,…,x_q,E_q,x_(q 1)}使x_i∈X,E_i∈E,x_i,x_(i 1)∈E_i, i=1,…,q,其中x_(q 1)=x_1;i≠j时E_i≠E_j,x_i≠x_j,且q>1. 由此定义易见一个超图不合圈,则任意的E_i,E_j∈E,E_i≠E_j必有|E_i∩E_j|≤1.     

超树的计数

本文对带有p阶和q边的(k+1)秩超树,证明如下猜想;其余,并且得到(p,q)无环超树的计数式:T(p,q)=p~(q-1)S_2(p-1,∈)其中S_2(m,n)是第二类stirling数     

关于有向图与超图的计数

1980年,M.Hegde和M.R.Sridharan沿用R.C.Read的计数方法,得到了标号偶有向图和偶超图的计数公式。我们推广了[1]的结果,得到了恰有2k个奇度点的p阶有向图和(p,q)有向图,恰有k个奇度点的p阶超图和(p,q)超图的计数式。本文所讨论的图均指标号图。     

超图的r-截口

设H=(X;E_1,E_2,…,E_m)是一个超图,H的r-截口,记作H_((r)),定义为(X;ε_((r)),其中ε_((r))={F;FX,|≤| F |≤r,且存在E_i使FE_i}.对任一超图H,H_((r))唯一存在,但并非任一秩不超过r的超图是某个超图的r-截口。本文给出了以给定超图为     

3-一致超图的反馈数研究（英文）

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τ_c(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τ_c(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τ_c(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τ_c′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τ_c'(H)≤2m-n+p.     

3-一致超图的反馈数研究

超图H=(V,E)顶点集为V,边集为E.S■V是H的顶点子集,如果H/S不含有圈,则称S是H的点反馈数,记τc(H)是H的最小点反馈数.本文证明了:(i)如果H是线性3-一致超图,边数为m,则τc(H)≤m/3;(ii)如果H是3-一致超图,边数为m,则τc(H)≤m/2并且等式成立当且仅当H任何一个连通分支是孤立顶点或者长度为2的圈.A■V是H的边子集,如果H\A不含有圈,则称A是H的边反馈数,记τc′(H)是H的最小边反馈数.本文证明了如果H是含有p个连通分支的3-一致超图,则τc’(H)≤2m-n+p.     

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m＜n)使对每个l∈{3,4,…,n} -{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图,用(?)k表示具有n k条边和恰有1/2(k 1)(k 2)个圈的简单H图的集合,用(?)_k~*表示具有n k条边恰有2~k k个圈的简单外可平面H图的集合,本文确定了(?)_k和(?)_k~*中所有几乎唯一泛圈图,并证明这些图都是简单MCD图,本文还构造了50个含有同胚于K_4的子图的几乎唯一泛圈图,并提出了若干问题和猜想。     

球超图最大边数的一个下界

设V={v_1,v_2,…,v_n}是一个有限集,E={e_1,e_2,…e_m}是V的非空子集的一个族,满足则称H=(V,E(是一个超图[1],V的元素称为H的顶点,E的元素称为H的边。n称为H的阶。若E中的元素两两不相同,则H称为是简单的。若V是k维欧氏空间ε_k中的点集,且有m个k维闭球B_1,B_2,…。B_m,使B_i中恰含e_1中的点,即     

关于多项式的一条猜想

设C是常数,p(z)与q(z)为多项式,若p(a)=C也使q(a)=C,则记为p9或qp.[1]提出如下猜想: 设p,q为次数大于1的多项式,若p=0q=0 且 p′=1q′=1,则p=q,其中p′为p的导数。     

余半单Hopf代数的Frobenius性质

设k是特征为0的代数闭域,H为其上的余半单Hopf代数,本文证明了当H有型:l:1 m:p 1:q(其中p~2相似文献   

正则的哈密顿路图

本文仅考虑无向简单图。所谓图G的哈密顿路图是指这样的图,它与G有相同的节点集,其中任意两个节点有边相连当且仅当它们在G中有哈密顿路相连。用H(G)表示图G的哈密顿路图。递归地,由H~k(G)=H(H~(k-1)(G))(k≥2)可以定义k-哈密顿路图。用ε(G)表示图G的边数。如果G(?)H~k(G),则称图G为k-自哈密顿路图,简称为k-SHP图(k-Self Hamil-tonian Path Graph(k≥1)。若k=1,则称G为SHP图。     

四维时空中两个不同主曲率类时共形齐性超曲面的分类

如果对任意两点p,q∈M_1~3,都存在R_1~4中的一个共形变换σ,使得σ(x(p))=x(q),并且σ(x(M_1~3)=x(M_1~3),则称x(M_1~3)为共形齐性超曲面.在本文中我们主要研究类时共形齐性超曲面x:M_1~3→R_1~4,并假设其形状算子可对角化且有两个不同主曲率.首先通过定义共形不变度量g_c,典则提升Y,共形切标架{E_i}和典则法标架ζ,我们给出了这类超曲面的一个完备共形不变量系统{E_1,E_2,E_3}.接下来通过可积条件,我们构造出了一系列非杜邦超曲面的例子以及对应的共形变换子群,并完成了对这类超曲面的分类.     

树环中的流量疏导问题研究

H为定义在树环G上的一个超图,将H的每条超边映射为G中不同的映射树,称为超边在G中的嵌入问题.超图在树环中的嵌入问题即为寻找H在G中的最优映射使得G中任一边被H所有超边的映射经过的最大次数最小.应用超图嵌入圈(MCHEC)问题的算法可得超图嵌入树环问题的一个2-近似算法.     

5-一致超图的全横贯

设H=(V,E)是以V为顶点集, E为(超)边集的超图. 如果H的每条边均含有k个顶点, 则称H是k-一致超图. 超图H的点子集T称为它的一个横贯, 如果T 与H 的每条边均相交. 超图H的全横贯是指它的一个横贯T, 并且T还满足如下性质: T中每个顶点均至少有一个邻点在T中. H 的全横贯数定义为H 的最小全横贯所含顶点的数目, 记作\tau_{t}(H). 对于整数k\geq 2, 令b_{k}=\sup_{H\in{\mathscr{H}}_{k}}\frac{\tau_{t}(H)}{n_{H}+m_{H}}, 其中n_H=|V|, m_H=|E|, {\mathscr{H}}_{k} 表示无孤立点和孤立边以及多重边的k-一致超图类. 最近, Bujt\'as和Henning等证明了如下结果: b_{2}=\frac{2}{5}, b_{3}=\frac{1}{3}, b_{4}=\frac{2}{7}; 当k\geq 5 时, 有b_{k}\leq \frac{2}{7}以及b_{6}\leq \frac{1}{4}; 当k\geq 7 时, b_{k}\leq \frac{2}{9}. 证明了对5-一致超图, b_{5}\leq \frac{4}{15}, 从而改进了当k=5 时b_k的上界.     

图与超图中的彩色匹配综述

超图H=(V,E)是一个二元组(V,E),其中超边集E中的元素是点集V的非空子集.因此图是一种特殊的超图,超图也可以看作是一般图的推广.特别地,如果超边集E中的元素均是点集V的k元子集,则称该超图为k-一致的.通常情况下,为叙述简便,我们也会将超边简称为边.图(超图)中的匹配是指图(超图)中互不相交的边的集合.对于图(超图)中的彩色匹配,有两种定义方式:一为染色图(超图)中互不相交且颜色不同的边的集合;二为顶点集均为[n]的多个染色图(超图)所构成的集族中互不相交且颜色均不同的边的集合,且每条边均来自集族中不同的图(超图).现主要介绍了图与超图中关于彩色匹配的相关结果.     

关于杨重骏之猜想

在文[1]中,杨重骏提出了下述两个猜想 猜想1 设p,q为两个非线性的多项式,若p=O q=0,p(z)=1 q’(z)=1, 则p≡q. 猜想2 设f,g为二超越整函数,且 f=0 g=0与 f=1 g=1.若f g,则必有fg≡1,且f≡e~x(z),共中x(z)为一非常数的整函数. 我们认为,猜想1和猜想2都不成立. 我们先来证明猜想1不成立.     

关于一个素数和一个素数的k次方和问题

设k≥2,Hk表示一个正整数n的集合,使对任意的正整数q,同余方程a+b2三n(modq)在模q的既约剩余系中有解a,b.Dk(N)表示n≤N,n∈Hk,但不能表成p1+p22=n的数的个数,其中p1,p2表示素数.则在GRH下,Dk(N)<<N1-1/k(h(k)+1)+ε,这里k=2,3;h(2)=2,h(3)=8.     

无圈超图的1—因子定理

本文证明了一个无圈超图 H=(X,E)有1-因子当且仅当(?)S(?)X,sum from i=1 to r-1(r-i)q_i≤|S|,其中 q_i 表示 H 的子超图 H-S 的顶点数模 r 等于 i 的连通分支数,r 是超图 H 的秩.     

充分条件和必要条件的判断

对于充分条件和必要条件 ,要能够正确地理解和判断 .1　概念1.1　若 p q ,则称p是 q的充分条件 ,q是p的必要条件 .1.2　若 p q ,则 p是q的充要条件 .1.3　若p q且 q 　q ,则称p是 q的充分不必要条件 .1.4　若 p 　q且 q p ,则称 p是q的必要不充分条件 .1.5　若p 　q且q 　 p,则称p是 q的既不充分也不必要条件 .2　概念的理解2 .1　从命题的角度理解设原命题为“若 p则q” ,则1)若原命题为真 ,则 p是q的充分条件 .2 )若逆命题为真 ,则 p是 q的必要条件 .3)若原命题和逆命题都为真 ,则p是 q的充要条件 .4 )若原命题为真而逆命题为假 ,…