超树的计数理论Ⅰ

作为超图理论的一个重要课题,简单树已推广到超树.对于简单标号树,巳有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中的元     

关于匀称超树数的猜想

1982年,毛经中对(k 1) p阶和q边的匀称超树的个数T_(k 1)(p,q)提出如下猜想:其余 易见,当k(?)1时,T(p, q) (q-1)~(?) p~p(?),故(*)成立将是标号树计数的Cayley公式在超图理论中的推广。 本书证明了上述猜想并得到一般超图的计数式。 定义 如果超图H (X,ε)是连通的且不含圈,则称H为一超树,若(?)E_i∈ε,|E_i|=M,则称H是匀称M秩超树。     

一类高维种群动力系统的持续性

§1.引言 对于下述形式的Kolmogorov系统: x_i=x_if_i(x_1,x_2,…x_n),i=1,2…,n, (1.1)其中x_i=dx_i(t)/dt,x_i(t)表示种群x_i在时刻t时的种群密度,X=(x_1,x_2,…,x_n)∈R_ ~n,f_i(x)∈C~1(R_ ~n),这里R_ ~n={X|x_i≥0,i∈N},而N={1,2,…,n},R_ ~(n,0)={X|x_i>0,i∈N},在条件X(0)={x_1(0),x_2(0),…,x_n(0)}∈R_ ~(n,0)下,如果对一切i∈N:有lim sup_(t→∞)x_i(t)>0成立,称系统(1.1)弱持续生存;若liminf_(t→∞)x_i(t)>0成     

无圈超图的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 的秩.     

集的最优分划问题简介

很多高校都要对一年级新生按他们的英语程度进行分班,以利于英语教学.分班的原则通常足先将学生按英语成绩高低进行排队,然后给出几个分数段,每一段中的学生编为一个水平班.比如:85分以上的编为快班;70-84分的编为中班;70分以下的编为慢班.这样分班的合理性是显而易见的.我们不难用数学语言给它一个描述:设 E={新生集合).每个学生 e∈E 对应有一个英语成绩 w(e)≥0.现将新生分成三个了集 E_1,E_2,E_3.满足 E=E_1∪E_2∪E_3,且 E_i∩E_j=φ(i≠j),问这三个子集应如何划分能使得同一子集中学生的英语成绩尽可能接近.我们可以在每一子集 E_i 上定义     

超图的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-截口。本文给出了以给定超图为     

三次样条的Hermite-Birkboff插值

设Δ:0=x_0相似文献   

非奇异H-矩阵的新判据

1引言与记号设A=(a_(ij))∈C~(n×n),记N={1,2,…,n},∧_i(?)∧_i(A)=sum from j≠i|a_(ij)|,S_i(?)S_i(A)=sum from j≠i|a_(ij)|,(?)i,j∈N。若|a_(ij)>∧_i(A),(?)i∈N,则称A为严格对角占优矩阵。     

关于多元凸函数的Bernstein多项式逼近的阶

1.引言 用△_k是表示R~k中的单纯形:△_k={X=(x_1,x_2,…,x_k)∈R~k|x_i≥0,i=1,2,…,k;sum from i=1 to k(x_i)≤1};C(△_k)表示定义在△_k上的连续函数的全体.记||f||=||f||_(△_k):=sup|f(X)|,ω(f,t):=sup |f(X)-f(Y)|。连续函数ω(t),t∈[0,+∞)称为     

解0-1线性规划Surrogate对偶的一个方法

0—1线性观划不难化为以下形式: (P)minc~Tx s.t.Ax≤b,x∈X这里X={(x_1,…,x_n)~T|x_i=0,1,i=1,…,n},A是m×n矩阵,c~T=(c_1,…,c_n),c_i≤0,(i=1,…,n),b∈R~m.假定(P)是适定的,称x是决策变量,A、b、c是参数变量. 设非负乘子V∈R~m,问题     

关于Lovász不等式的几类超图

本文证明了下面的定理:若超图H=(X;E_1,E_2,…,E_m)中存在浓度为k长为m的圈,则有     

关于加权距离正则图和立方图

令G=(V,E)是简单的连通k-正则图;w_1相似文献   

在对称群中一类正则图所确定的极大子群

对称群的极大子群之确定,在多值逻辑理论和有限自动机理论中都有着重要而广泛的应用,同时也是置换群理论中的一个基本问题.本文提出了 k 次对称群中一类新的极大子群,k=h~m,m≥3,h≥7.设Γ=(Ω,E)是一个无向正则图,其中顶点集Ω={(α_1,…,α_m)|β_i∈Ω_h={10,1,…,h-1},i=1,…,m},边集 E={α,β〉|α=(α_1,…,α_m),β=(β_1,…,β_m)∈Ω,α_i≠β_i,i=1,….m}:G 是Γ的所自同构作成之群.于是,(1)G 是本原群,且G={g|g(x)=g(x_1,…,x_m)=(g_1(x_σ(1)),…,g_m(x_σ(m))),σ∈S_m(集合{1,…,m}上的对称群),g,∈S_h(Ω_h 上的对称群),i=1,…,m};(2)若 h 为奇数 h=2_n+1且 n 为偶数或 h-1>m,则 G 是 k 次对称群 S_k 中的极大子群;(3)若 k 为偶数且2(k-1)>m,则 G 是 k 次交代群 A_k 中的极大子群.     

超图的围秩与Lovasz不等式

Lovasz曾经证明[1]:若超图H=(X;E_1,E_2,…E_1)有p个支,不含长度大于2的圈,且每两边至多有两个公共点,则有     

图带宽和与其对偶超图带宽和的关系

设H=（E1,E2,…,Em）是集合X上的一个超图,一个1-1映射f:X→{1,2,…,|X|}称为H的一个标号,对H的任一标号f,BS（H,f）=∑(E∈H)max{|f(u)-f(v)|;u,v∈E}称为超图H的关于标号f的带宽和BS(H)=min{BS(H,f)|f是超图H的标号|}称为H的带宽和．论文研究图带宽和与其对偶超图的带宽和这两个参数间的关系．     

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=(V,E)是简单图.称一个函数f:E→{+1,-1}为图G的符号圈控制函数,若对G的每一导出圈C,有Σ_(e∈)E(C)f(e)≥1.G的符号圈控制数被定义为γ′_(sc)(G)=min{∑_(e∈E)f(e)|f是G的符号圈控制函数}.本文刻画了所有具有γ′_(sc)(G)=|E|-4的连通图G.     

非线性互补问题的L1模算法

非线性互补问题(记作NCP(F))定义为求x∈R~n,满足X≥0,F(x)≥0且X~гF(x)=0。其中F:R~n→R~n。本文假设F(x)是一阶连续可微的。 引人映射H:R~n→R~n,其中H的第i个分量H_i(x)=min(x_i,F_i(x))及其L_1模函数 θ(x)=sum from i=1 to n |min(x_i,F_i(x)|设全集I={1,2,…,n},定义其子集: I_f(x)={i|F_i(x)0}, I(x)={i|F_i(x)=x_i},I_f(x)={i|F_i(x)相似文献   

在对称群中一类正则图所确定的极大子群

对称群的极大子群之确定,在多值逻辑理论和有限自动机理论中都有着重要而广泛的应用,同时也是置换群理论中的一个基本问题。本文提出了k次对称群中一类新的极大子群,k=h~m,m≥3,h≥7。 设Г=(Ω,E)是一个无向正则图,其中顶点集Ω={(α_1,…,α_m)|α_i∈Ω_h={0,1,…,h-1},i=1,…,m},边集E={<α,β>|α=(α_1…,α_m),β=(β_1,…,β_m)∈Ω,a_i≠β_i,i=1,…。m};G是Г的所自同构作成之群。于是,(1)G是本原群,且 G={g|g(x)=g(x_1,…x_m)=(g_1(x_(σ(1))),…,g_m(x_(σ(m))),σ∈S_m (集合{1,…,m}上的对称群),g_i∈S_h(Ω_h上的对称群),i=1,…,m};(2)若h为奇数h=2n+1且n为偶数或h-1>m,则G是k次对称群S_k中的极大子群;(3若h为偶数且2(h-1)>m,则G是k次交代群A_k中的极大子群。