启发法及其设计——综合报告(四)

4.5候选者的选择——启发法的一个特征启发法的特征就是不对所有被接纳的候选者都作进一步的考察.根据对被接纳的候选者的评估,他们之中只有一些被选中,而其他的则被舍弃.这种舍弃过程使被接纳的候选者所成之集(邻域3)缩减成为选中的候选者之集(邻域4).在启发法中,除了一个被接纳的候选者外全都不要的作法是常见的.这个选中者是具有最好评估的候选者(属性N).尽管这种过程最常用,但也会被滥用.     

图的双控制的一些新结果

图G=(V,E)的每个顶点控制它的闭邻域的每个顶点.S是一个顶点子集合,如果G的每一个顶点至少被S中的两个顶点控制,则称S是G的一个双控制集.把双控制集的最小基数称为双控制数,记为dd(G).本文探讨了双控制数和其它控制参数的一些新关系,推广了[1]的一些结果.并且给出了双控制数的Nordhaus-Gaddum类型的结果.     

R^(1)上莫朗测度关于几何平均误差的最优Voronoi分划北大核心CSCD

设E是R^(1)上由有界闭区间J,(nk)_(k)=1∝和C_(k)=(ck,j)j=1nk1)k≥1确定的莫朗集.μ是E上由正概率向量序列(P_(k))k≥1所确定的一个莫朗测度.μ关于几何平均误差的所有n-最优集组成的集簇记为Cn(μ).设αn∈Cn(μ)及αn对应的任一Voronoi分划{Pa(αn)}a∈αn.证明了■对于每个aαn,Pa(αn)包含一个以a为中心,半径为d2|Pa(αn)∩E|的闭区间,其中d2是一个常数,|B|是集合B?R^(1)的直径.记en(μ)是μ上的n-级几何平均误差及ên(μ):=logen(μ),证明了ên(μ)-ên+1(μ)■n-1.     

一类极小本原对称图的指数集

运用有向图方法完全确定出顶点带环的n阶极小本原对称有向图的本原指数集,所得的结论是:1)顶点全部自带环的n阶极小本原对称有向图所成的子图类之本原指数集E1={2,3,…,n-1};2)顶点不全带环的n阶极小本原对称有向图所成的子图类之本原指数集E2={2,3,…,2n-2}\S,其中S是{n,n+1,…,2n-2}中的所有奇数之集;3)顶点带环的n阶极小本原对称有向图所成的特殊图类之本原指数集En=E1∪E2={2,3,…,2n-2}\S.     

两类特殊图的L(2,1)-标号

正1引言本文所指定的图均为无向简单图,文中未说明的符号和术语同文献[1].设G=(V,E)是一个图,其顶点集V=V(G)和边集E=E(G).对任意u∈V(G),则N_G(u)为u点在G中的邻域,N_G[u]=N_G(u)∪{u}为u点在G中的闭邻域,d_G(u)=|N_G(v)|为u点在G中的度,而δ=δ(G)和△=△(G)分别为图G的最小度和最大度.在不致混淆情况下,可将N_G(v),N_G[v],△(G),δ(G)分别简单记为N(v),N[v],△,δ.图G中两个顶     

核函数 递归算法論Ⅱ

<正> 这里所討論的函数仍是有穷字母表 (?)={o_1,…,ok}中的函数.我們仍以☉表示空字(見[1]). 本文定义了一个看来是极狹小的函数集(§1),并証明其中的函数都可以表成一种范式(§2).此外,还利用这函数集构造了一种正規算法的通用算法与一种图林机器的通用計算机(§3).     

关于满足强分离开集条件的自相似集的Hausdorff测度

设E是Rn中由相似压缩S1,S2,…,Sm所确定的满足开集条件的自相似集,其Hausdorff维数为s,其s-维Hausdorff测度记为Hs(E).利用部分估计原理得到了本文的主要结果:若E满足强分离开集条件,则在E中存在一个压缩拷贝串序列{Ui}和紧集U(|U|>0),使得Hs(U)等于|U|s,并且{Ui}按Hausdorff度量收敛到U,进而证明了由U可以构造一个数列,使得该数列正好收敛到Hs(E);另外,引入了自相似集的相似压缩不动点,得到了等式Hs(E∩U)=|U|s 成立的一个必要条件.     

部分双曲集附近的拟跟踪性

引入部分双曲集的概念,证明了紧黎曼流形上的微分同胚在其部分双曲集的小邻域内具有如下形式的拟跟踪性:设f为紧黎曼流形M上的一个微分同胚,Λ为f的部分双曲集.则存在Λ的邻域O(Λ),使得对于任意ε0,存在δ0,使得f在O(Λ)中的任意δ-伪轨{x_k}k∈Z,存在点列{y_k}k∈Z,和中心向量列{u_k∈E_(xk)~c}k∈Z满足d(x_k,y_k)ε,其中y_k=exp_(x_k)(exp_(x_k)~(-1)(f(y_(k-1)))+u_k).作为一个应用,给出任意微分同胚在C~0扰动下,如果在双曲集邻域内存在不变集,则其是拓扑拟稳定的.     

部分双曲集附近的拟跟踪性北大核心CSCD

引入部分双曲集的概念,证明了紧黎曼流形上的微分同胚在其部分双曲集的小邻域内具有如下形式的拟跟踪性:设f为紧黎曼流形M上的一个微分同胚,Λ为f的部分双曲集.则存在Λ的邻域O(Λ),使得对于任意ε>0,存在δ>0,使得f在O(Λ)中的任意δ-伪轨{x_k}k∈Z,存在点列{y_k}k∈Z,和中心向量列{u_k∈E_(xk)~c}k∈Z满足d(x_k,y_k)<ε,其中y_k=exp_(x_k)(exp_(x_k)^(-1)(f(y_(k-1)))+u_k).作为一个应用,给出任意微分同胚在C^0扰动下,如果在双曲集邻域内存在不变集,则其是拓扑拟稳定的.     

一种求解运动曲面上对流扩散方程的三维水平集方法

给出了一种求解运动曲面上对流扩散方程的三维水平集算法. 水平集函数被用来表示曲面.曲面上的微分方程及其解通过水平集方法被延拓到包含曲面的一个小邻域中. 一种半隐式的Crank-Nicholson 格式被用来做时间推进, 中心差分和三阶加权实质无振荡(WENO) 格式被分别用来离散方程中的扩散项和对流项. 分析证明了它在标准的Courant-Friedrichs-Lewy (CFL) 条件下的稳定性. 数值算例显示了它能取得二阶精度.     

Browder定理和Weyl定理

本文通过定义两个新的谱集,给出了Browder定理和Weyl定理对算子T以及f(T)成立的充要条件,其中f∈H(σ(T)),H(σ(T))表示在谱集σ(T)的开邻域上解析的函数的全体。     

决策分析概述

§引言在人类的社会实践中,人们会遇到各种各样的决策问题.对于某一具体问题,一般总有若干个行动(actions)(或方案,措施等)可供选择.全体可供选择的行动所成之集称为行动集,记作D.采取某一行动之后,其可能出现的结果(outcomes)事先不能确切预知,是不确定的(uncertain).这种不以人的意志而改变的结果称为自然状态,简称状态.全体状态所成之集称为状态集,记作I.被选用的行动与可能出现的状态两者对应于一个后果     

一个产生Jaulent-Miodek方程的无反射位势的五次Hamilton系统

在Jaulent-Miodek方程的无反射位势与平方特征函数的关系(u,v)~T=f(ψ)所确定的约束下,孤子方程的Lax对被非线性化成一个五次系统和一个非线性演化方程,而前者的解簇是由后者所确定的S-流的不变集。此外,f把五次系统的解映到某个驻定的Jaulent-Miodek方程的解。     

一类p叶解析函数的邻域与部分和

本文研究了单位圆内解析的p叶函数类S*n+p-1(η;A,B).利用邻域概念,得到了函数f(z)的邻域与函数类S*n+p-1(η;A,B)的一些包含关系以及函数,f(z)的部分和性质.     

准上半连续性不必蕴含上半连续性的例子

<正> 1.命 X,Y 是拓扑空间,多值映象 T:X→2~Y 称为上半连续的(upper semi-continuous),如果对任何 x_0∈X 和任何开集 G(?)T(x_0),存在 x_0 在 X 中的邻域 U(x_0)使得 x∈U(x_0)蕴含 T(x)(?)G.F.E.Browder 证明了下述卓越的不动点原理([1]定理3).定理1 命 K 是局部凸隔离实拓扑向量空间 E 的非空紧致凸集,T:K→2~E 上半连续,使得对每个 x∈K,T(x)(?)E 是非空闭凸集,命δ(K)={x∈K|(?)y∈E,使 x+λy(?)K,(?)λ>0}表示 K 的代数边界.假设对每个 x∈δ(K),存在 y∈K,z∈T(x)和λ>0使得z-x=λ(y-x),那么存在 x_0∈K 使 x_0∈T(x_0).     

Fuzzifying双拓扑空间中的半开集

引入了fuzzifying双拓扑空间中的(τi,τj)半开集(半开集),(τi,τj)半邻域系统(半邻域系统)以及(τi,τj)半闭包和(τi,τj)半内部(半闭包,半内部),最后给出了全连续映射。     

具有有限个負二次式的条件正定广义函数

<正> §1.引言 設K是具有有界支集的无限次可微分函数φ(x)的全体所成的基本函数空間.在K中按照通常的方法引进拓扑,当K中的序列{φ_n(x)}以及它們的各阶导函数所成的序列都分別地勻斂于0,而且它們的支集的和集有界时,我們定义φ_n收斂于0,記为φ_n0.設K′是K上的連續线性泛函全体所成的广义函数空間,当φ(x)∈K时,置φ(x)=φ(-x).在空間K上定义卷积“*”如下:     

deg≥2的圆周自映射

<正> 记 R=(-∞,+∞),I=[0,1]和 S~1{e~(2πxi)|x∈I}.S~1是复平面上中心在原点的单位圆周.S~1上全体连续自映射的集合记为 C~0(S~1,S~1).设 f∈C~0(S~1,S~1),f 的周期集合,不动点集,周期点集,非游荡集和拓扑熵分别记为 p(f),F(f),P(f),Ω(f)和ent(f).此外,用 deg(f)记 f 的拓扑度或层数(一种定义见§2).关于圆周自映射所产生的动力系统性质已有很多人进行了讨论.据作者所知,所有这种讨论还仅限于在某种条件下寻求拓扑熵下限的最好估计以及 Sharkovskii 和 Li Yorke     

有向完美图

Gallai 和 Milgram 曾经证明,有向图 G 的所有结点可用恰好 α(G) 条互不相交的路来复盖,此处 α(G) 为图 G 的内固数.然而这个结果的好多证明都未指出存在着一最优 内固集 S 以及结点集的一个路剖分 μ_1,μ_2,…μ_k,以致对于所有 i,均有|S∩μ_i|=1.Gallai 和 Roy 曾经独立地证明,在一有向图 G 中,令 k 为一条路所能包含的最多的结点的个数,则 k 至少等于图 G 的色数γ(G).同样,我们不知道是否存在一最优色谱(S_1,S_2,…,S_k)以及一条路μ,以致对于所有的 i,均有|S_i∩μ|=1.在本文中引进了下述概念:1.有向图 G 称为α-有向完美,若对于每一最优内固集 S,均存在结点集合的一个路剖分μ_1,μ_2,…,以致对于所有的 i,均有|S∩μ_i|=1(且此性质对 G 的任一子图亦成立).2.一有向图 G 称为 γ-完美,若对于每一最优色谱 (S_1,S_1,…S_k),均存在一条路 μ,以致对于所有 i,均有|μ∩S_i|=1(且此性质对 G 的每一子图亦均成立).3.一长度为2k+1的奇圈系由2k+1条弧 u_1,u_2,…,u_(2k+1) 所给出,并从而确定了一个有2k+1个结点的序列 x_1,x_2,…,x_(2k+1).一条弦,可以是 G 的一条弧,它联结在以上叙列中不相继的两个结点,或者是 G 的一条弧,它平行上述2k+1条弧中的一条弧.一个奇圈称为反有向的,若i)其长度>3,ii)最长     

NP图灵完全集的一些性质

本文主要结果是:(1)P=NP 当且仅当一切 NP 图灵完全的无穷集组成一个非递归可表现的类;(2)NP=co-NP 当且仅当一切 NP 图灵完全集恰好组成一个多项式时间图灵等价类;(3)NP=co-NP 当且仅当 NP=P~(SAT).