轮图和多轮图的生成树的计数

本文应用计算生成树个数的有向图方法、分块矩阵的行列式计算法以及常系数线性递归方程的解法 ,计算得到轮图和多轮图的生成树个数的表达式 (显式或递推式 )     

棱柱和多边形上可定向的小覆盖

计算了棱柱和多边形上可定向小覆盖的等变同胚类的个数.     

有向图中几类支撑树数目的计算公式

将W.T.Tultte提出的计算有向图中以某点为根的支撑出树数目的公式推广到了更一般的情况,并给出了有向图中具有不同特点的支撑树数目的计算公式。     

递归树的若干枚举特征

递归树由Meir和Moon定义作非平面增长树的一种，且所有节点出度都是允许的．本文首先在n个节点的递归树集合和n-1个元素的排列之间建立一个新的──对应，这个对应能同时给出树叶子和排列中的路段之间的对应和树叶子数和排列中的路段数之间的密切关系．同时还研究递归树的各种枚举特征，诸如节点的分类枚举（内节点和叶子节点、偶节点和奇节点，具不同出度的节点）和通路长度枚举（接各种节点分类）．     

一道组合竞赛题的延伸

1978年波兰数学奥林匹克有一道组合题: 对于n元集合N的任何两个子集A和B,求得A(n)B的元素个数,求证所有的个数之和为n.4n-1.     

最小支撑树博弈:重新审视Bird配置

最小支撑树博弈是合作博弈中的经典模型,自1973年被Claus和Kleitman提出后持续得到学术界关注.最小支撑树博弈不仅跟图论和组合优化中的最小支撑树问题一脉相承,还在水网、电网和公路铁路网建设中的成本分摊问题中有重要应用. Bird配置因其简洁性和直观性持续受到大量关注,是最小支撑树博弈最著名的求解方案.本文基于Edmonds对最小支撑树问题的线性规划表示,利用对偶定理给出Bird配置一种新的等价公式.本文还研究了最小支撑树博弈的一种推广,即点加权的最小支撑树博弈,并证明了Bird配置的一个变形依然在这个推广博弈的核中.     

一道组合竞赛题的推广

1978年波兰数学奥林匹克有一道组合题: 对于n元集合M的任何两个子集A和B,求得A∩B的元素个数,求证所有求得的个数之和为n*4n-1.下面给出原证明.     

图的支撑树伸展与层叠最优化

在图的支撑树最优化中,有两个重要的优化指标:伸展度和层叠度.由此提出两个组合最优化问题:最小伸展支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,这些边的最大伸展距离为最小;最小层叠支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,每条树边上的最大重叠边数为最小.这两个问题确定出两个图论参数:树展和树层.本文主要论述树展和树层的基本结构性质,包括圈与余圈的对偶性、极值性、上下界、最优性刻画和最优值计算等.     

简单多面体与球

1本单元重、难点分析本单元的重点是:多面体和凸多面体的概念,棱柱、棱锥的概念和性质,直棱柱和正棱锥的直观图的画法,正多面体,欧拉公式,球的概念和性质,球的体积和表面积.棱柱中重点研究的是三棱柱和平行六面体,其中的长方体(正方体)是建立空间概念培养空间想象能力的理想模型.棱锥中重点研究的是正棱锥和三棱锥,它们是许多空间几何问题的载体.棱柱和棱锥的性质是进行计算和证明的理论依据,必须掌握.欧拉公式描述了简单多面体的顶点数、面数和棱数之间的关系,是进行相关推理和计算的重要工具.球是一个特殊的几何体,它只有一个面(即球面),…     

计量逻辑学中的雪崩逻辑公式

将密码学中满足严格雪崩准则的布尔函数的概念引入到计量逻辑学之中,提出了雪崩逻辑公式的概念,并研究了雪崩逻辑公式的真度及其性质。证明了至少含有三个原子公式的雪崩逻辑公式的真度之集为H1={k/2n-12n-3≤k≤3×2n-3;n=3,4,…},在此基础上,通过引入函数ξ建立了n(n≥3)元雪崩布尔函数个数的表达式,给出了雪崩逻辑公式的构造方法。最后,研究了反射变换下k阶雪崩逻辑公式的性质。     

Bijective counting of Kreweras walks and loopless triangulations

We consider lattice walks in the plane starting at the origin, remaining in the first quadrant i,j?0 and made of West, South and North-East steps. In 1965, Germain Kreweras discovered a remarkably simple formula giving the number of these walks (with prescribed length and endpoint). Kreweras' proof was very involved and several alternative derivations have been proposed since then. But the elegant simplicity of the counting formula remained unexplained. We give the first purely combinatorial explanation of this formula. Our approach is based on a bijection between Kreweras walks and triangulations with a distinguished spanning tree. We obtain simultaneously a bijective way of counting loopless triangulations.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

Greedy heuristics for the diameter-constrained minimum spanning tree problem

The diameter-constrained minimum spanning tree problem is an NP-hard combinatorial optimization problem that seeks a minimum cost spanning tree with a limit D imposed upon the length of any path in the tree. We begin by presenting four constructive greedy heuristics and, secondly, we present some second-order heuristics, performing some improvements on feasible solutions, hopefully leading to better objective function values. We present a heuristic with an edge exchange mechanism, another that transforms a feasible spanning tree solution into a feasible diameter-constrained spanning tree solution, and finally another with a repetitive mechanism. Computational results show that repetitive heuristics can improve considerably over the results of the greedy constructive heuristics, but using a huge amount of computation time. To obtain computational results, we use instances of the problem corresponding to complete graphs with a number of nodes between 20 and 60 and with the value of D varying between 4 and 9.     

How to Resum Feynman Graphs

In this paper, we reformulate the combinatorial core of constructive quantum field theory. We define universal rational combinatorial weights for pairs made of a graph and any of its spanning trees. These weights are simply the percentage of Hepp’s sectors of the graph in which the tree is leading, in the sense of Kruskal’s greedy algorithm. Our main new mathematical result is an integral representation of these weights in terms of the positive matrix appearing in the symmetric “BKAR” Taylor forest formula. Then, we explain how the new constructive technique called Loop Vertex Expansion reshuffles according to these weights the divergent series of the intermediate field representation into a convergent series which is the Borel sum of the ordinary perturbative Feynman’s series.     

Spanning trees on hypercubic lattices and nonorientable surfaces

We consider the problem of enumerating spanning trees on lattices. Closed-form expressions are obtained for the spanning tree generating function for a hypercubic lattice in d dimensions under free, periodic, and a combination of free and periodic boundary conditions. Results are also obtained for a simple quartic net embedded on two nonorientable surfaces, a Möbius strip and the Klein bottle. Our results are based on the use of a formula expressing the spanning tree generating function in terms of the eigenvalues of an associated tree matrix. An elementary derivation of this formula is given.     

The sand-pile model and Tutte polynomials

A new explicit bijection between spanning trees and recurrent configurations of the sand-pile model is given. This mapping is such that the difference between the number of grains on a configuration and the external activity of the associate tree is the number of edges of the graph. It gives a bijective proof of a result of Merino López expressing the generating function of recurrent configurations as an evaluation of the Tutte polynomial.     

Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree

The Degree Constrained Minimum Spanning Tree (DCMST) on a graph is the problem of generating a minimum spanning tree with constraints on the number of arcs that can be incident to vertices of the graph. In this paper we develop three heuristics for the DCMST, including simulated annealing, a genetic algorithm and a method based on problem space search. We propose alternative tree representations to facilitate the neighbourhood searches for the genetic algorithm. The tree representation that we use for the genetic algorithm can be generalised to other tree optimisation problems as well. We compare the computational performance of all of these approaches against the performance of an exact solution approach in the literature. In addition, we also develop a new exact solution approach based on the combinatorial structure of the problem. We test all of these approaches using standard problems taken from the literature and some new test problems that we generate.     

An Iterative Exact Solution for the Dual Power Management Problem in Wireless Sensor Network

We study the dual power management problem in wireless sensor networks. Given a wireless sensor network with two possible power levels (heigh and low) for each sensor, the problem consists in minimizing the number of sensors assigned heigh power while ensuring the connectivity of the network. We formulate the problem by a binary integer programming model to minimize the total power consumption. Since the problem is NP-complete, we provide an iterative approximation based on iterative methods in combinatorial optimization. We solve the separation subproblem as a minimum spanning tree.