基于图谱理论的纹理图像分析

图谱理论作为目前模式识别研究的热门方法之一,广泛应用于聚类与分割,但对其进行图像分析,尤其是复杂的纹理图像分析未见报道。将图谱理论引入到图像分析领域,并结合窗口纹理分析方法构造新的纹理分析算法。首先对图像灰度级进行窗口划分得到不同灰度级下的子图像,然后以各子图像作为图的顶点,子图像间的相似度作为图的边,将原图像解析为一幅带权无向图。利用图谱理论的相关思想对该无向图进行分析,可以从中获得纹理粗糙度等特征,从而完成对原始图像的分析。通过对Brodatz图像库的检索实验证明,该方法优于传统纹理分析算法。     

特殊图类的符号控制数

图G的符号控制数γS(G)有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其上下界有重要意义.本文研究了1)一般图G的符号控制数,给出了一个新的下界;2)确定了Cn图的符号控制数的精确值.     

Gargano,Lewinter and Malerba问题的解

§1　IntroductionLet G be a graph with vertex-set V(G) ={ v1 ,v2 ,...,vn} .A labeling of G is a bijectionL:V(G)→{ 1,2 ,...,n} ,where L (vi) is the label of a vertex vi.A labeled graph is anordered pair (G,L) consisting of a graph G and its labeling L.Definition1.An increasing nonconsecutive path in a labeled graph(G,L) is a path(u1 ,u2 ,...,uk) in G such thatL(ui) + 1相似文献   

不含悬挂点的A3-图

对于图方程 A( H) =n的讨论 ,重点是研究 A2 -图及 A3-图 H及其母图的性质 ,这就需要研究不同类型的 A3-图 .本文给出了不含悬挂点的 A3-图     

对带有中止规则的调整型抽样方案的复合OC函数的研究

利用多元转移概率流图及转移概率母函数,对带有中止检查规则的调整型抽样方案进行了讨论,分别在(1)当检查始于正常检查时,(2)当检查始于加严检查时和(3)当检查始于放宽检查时,得到了三个复合OC函数.     

A new algorithm for the intersection of a line with the independent set polytope of a matroid

We present a new algorithm for the problem of determining the intersection of a half-line with the independent set polytope of a matroid. We show it can also be used to compute the strength of a graph and the corresponding partition using successive contractions. The algorithm is based on the maximization of successive linear forms on the boundary of the polytope. We prove it is a polynomial algorithm in probability with average number of iterations in O(n⁵). Finally, numerical tests reveal that it should only require O(n²) iterations in practice.     

Decomposition of bipartite graphs into closed trails

Let Lct(G) denote the set of all lengths of closed trails that exist in an even graph G. A sequence (t ₁,..., t _p ) of elements of Lct(G) adding up to |E(G)| is G-realisable provided there is a sequence (T ₁,..., t _p ) of pairwise edge-disjoint closed trails in G such that T _i is of length T _i for i = 1,..., p. The graph G is arbitrarily decomposable into closed trails if all possible sequences are G-realisable. In the paper it is proved that if a ⩾ 1 is an odd integer and M _a,a is a perfect matching in K _a,a , then the graph K _a,a -M _a,a is arbitrarily decomposable into closed trails.      

Codiameters of 3-domination critical graphs with toughness more than one

A graph G is 3-domination-critical (3-critical, for short), if its domination number γ is 3 and the addition of any edge decreases γ by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with α≤δ, Discrete Mathematics 271 (2003) 1-12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with α=δ+2, European Journal of Combinatorics 23 (2002) 777-784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with α=δ+1≥5, Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph G is Hamilton-connected if and only if τ(G)>1, where τ(G) is the toughness of G.     

Edge-choosability of planar graphs without adjacent triangles or without 7-cycles

A graph G is edge-L-colorable, if for a given edge assignment L={L(e):e∈E(G)}, there exists a proper edge-coloring ? of G such that ?(e)∈L(e) for all e∈E(G). If G is edge-L-colorable for every edge assignment L with |L(e)|≥k for e∈E(G), then G is said to be edge-k-choosable. In this paper, we prove that if G is a planar graph with maximum degree Δ(G)≠5 and without adjacent 3-cycles, or with maximum degree Δ(G)≠5,6 and without 7-cycles, then G is edge-(Δ(G)+1)-choosable.     

The clique operator on matching and chessboard graphs

Given positive integers m,n, we consider the graphs G_n and G_m,n whose simplicial complexes of complete subgraphs are the well-known matching complex M_n and chessboard complex M_m,n. Those are the matching and chessboard graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph G_m,n in terms of m and n, and show that G_m,n is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph G_n.