Sufficient Conditions for a Digraph to be Supereulerian

A (di)graph is supereulerian if it contains a spanning eulerian sub(di)graph. This property is a relaxation of hamiltonicity. Inspired by this analogy with hamiltonian cycles and by similar results in supereulerian graph theory, we analyze a number of sufficient Ore type conditions for a digraph to be supereulerian. Furthermore, we study the following conjecture due to Thomassé and the first author: if the arc‐connectivity of a digraph is not smaller than its independence number, then the digraph is supereulerian. As a support for this conjecture we prove it for digraphs that are semicomplete multipartite or quasitransitive and verify the analogous statement for undirected graphs.     

一种基于图论与熵的专家判断客观可信度的确定方法

本文给出一种群决策中确定专家判断可信度的方法，其主要思路是首先通过图论中最小生成树的方法提取专家判断矩阵的全部信息，其次，使用相对熵指标确定获得专家判断的最终结果，并同时衡量专家自身判断的统一程度，从而确定专家判断的相对客观可信度。最后，文章给出一个典型的算例以说明该方法的可行性和有效性。     

浙江中部夏熟作物田主要杂草生态相似性的数量分析

应用七级目测法对浙江中部地区27个夏熟作物田样点的杂草进行了优势等级调查，将所得数据转换成重要值，以杂草在27个样点中的重要值为运算指标，应用主成分分析法和图论聚类中的最小生成树法，对24种杂草的生态学相似性进行了比较，指出了长期使用单一的除草剂导致农田杂草种群迅速更迭的原因：杂草对除草剂的敏感性差异及不同杂草间的生态学特性的差异。     

Bases,spanning sets,and the axiom of choice

Two theorems are proved: First that the statement “there exists a field F such that for every vector space over F, every generating set contains a basis” implies the axiom of choice. This generalizes theorems of Halpern, Blass, and Keremedis. Secondly, we prove that the assertion that every vector space over ?₂ has a basis implies that every well‐ordered collection of two‐element sets has a choice function. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

On the normalized Laplacian of Möbius phenylene chain and its applications

Let denote a molecular graph of linear [n] phenylene with n hexagons and n squares, and let the Möbius phenylene chain be the graph obtained from the by identifying the opposite lateral edges in reversed way. Utilizing the decomposition theorem of the normalized Laplacian characteristic polynomial, we study the normalized Laplacian spectrum of , which consists of the eigenvalues of two symmetric matrices ℒ _R and ℒ _Q of order 3n. By investigating the relationship between the roots and coefficients of the characteristic polynomials of the two matrices above, we obtain an explicit closed-form formula of the multiplicative degree-Kirchhoff index as well as the number of spanning trees of . Furthermore, we determine the limited value for the quotient of the multiplicative degree-Kirchhoff index and the Gutman index of .     

Hierarchical Model-Based Clustering for Large Datasets

In recent years, hierarchical model-based clustering has provided promising results in a variety of applications. However, its use with large datasets has been hindered by a time and memory complexity that are at least quadratic in the number of observations. To overcome this difficulty, this article proposes to start the hierarchical agglomeration from an efficient classification of the data in many classes rather than from the usual set of singleton clusters. This initial partition is derived from a subgraph of the minimum spanning tree associated with the data. To this end, we develop graphical tools that assess the presence of clusters in the data and uncover observations difficult to classify. We use this approach to analyze two large, real datasets: a multiband MRI image of the human brain and data on global precipitation climatology. We use the real datasets to discuss ways of integrating the spatial information in the clustering analysis. We focus on two-stage methods, in which a second stage of processing using established methods is applied to the output from the algorithm presented in this article, viewed as a first stage.