经典组合优化问题的概率极限定理(英文)

本文对经典组合优化问题解的主要概率极限定理作一综述 ,并重点讨论零担售货员问题 ,极小生成树 ,匹配和最长单调增子列长度 .涉及的概率极限定理包括强大数律 ,收敛速度 ,依分布收敛和大偏差原理 .没有提供详细证明 。

基于圈或路的多重星相关图的生成树数目

利用图的标定技巧、矩阵和行列式运算、补生成树矩阵定理等理论,研究了当图G是基于圈或路的多重星图时,补图类Kn-G的生成树数目的计数问题,得到了一些特殊情况下基于圈或路的多重星相关图的生成树数目的计数公式.

基于路的多重完全图相关图的生成树数目

利用图G的标号技巧、矩阵和行列式运算、补生成树矩阵定理等,研究了当G是基于路的多重完全图时的补图类Kn-G的生成树数目的计数问题,并求出了补图类Kn-G的一些特殊情况的生成树数目的计数公式.

有关对称无权图生成树数目的拆分定理

设G是一个对称平面图.Ciucu等证明了一个有关G的生成树数目的拆分定理,也就是G的生成树数目可用两个小图的生成树数目乘积来表示.在此基础上,提出了一种图变换,给出了图在这种变换下生成树数目的变化关系式,再结合矩阵-树定理给出了该拆分定理的一个简短证明.同时,受Zhang等证明的赋权图生成树权和的拆分定理启发,还给出了一个关于对称无权图生成树数目的等价拆分公式.

切比雪夫多项式与循环图中生成树的个数

生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量．利用切比雪夫多项式的性质推出了循环图中计算生成树个数的在线性时间内即可实现的方法,并讨论了渐进特性．

矩阵-树定理的一个简单证明

本文不用行列式计算中的Binet－Chachy定理，给出矩阵-树定理的一个简单证明．

基于路的多重完全图相关图生成树计数

利用图G的标定技巧、矩阵和行列式运算、补生成树矩阵定理、不等式运算等理论,研究了当m=2,3,4,5,且a1,a2,…,am为任意数时,基于路的多重完全图相关图一般情况的生成树数目,并得到了相关公式。

图G(p,q)的生成子图的构造与计数

在工程实际中,经常要设计最短线路或管线,这往往要用到生成树的知识。本文给出了生成子图的定义,证明了生成子图的计数定理和构造定理,提出了任意G(p,q)的生成树的构造方法和技术方法。介绍了八面体平面的生成树的计数和构造。

图类K_n-C_4~s(a1,a2,a3,a4)的生成树数目最大化条件

利用图G的标定技巧、补生成树矩阵定理、线性代数的矩阵、行列式运算和不等式运算等理论,研究了补图类——当m比较小且为任意数时,基于圈的多重星相关图的一般情况(即a1,a2,…,am为任意数时)的生成树的数目最大时满足的条件并得到了相关结论。

利用对偶图求平面图的生成树数目

图的生成树数目是图的一个重要参数,求连通图生成树数目的方法有很多.本文利用平面图的对偶图的Kirchhoff矩阵来求一些平面图的生成树数目,求这类平面图的生成树数目比直接利用收缩边和去边得到递推公式的方法要简单,该方法对于平面图可以进一步推广.

几类平面图生成树数目的一种求法

求连通图生成树数目的方法有很多。本文利用平面图的对偶图的Kirchhoff矩阵求出梯形图,扇形图和轮图的生成树数目,这类平面图利用收缩边和去边的方法已经求出,但用本文的方法更简单直接且便于推广到一般平面图。

一类柱面上的格子图的生成树数

计算一个图的生成树数问题在数学、物理和化学等很多领域都被广泛的研究.该文考虑具有柱面条件的一类网格图的生成树数,给出了生成树数的显式表达式.

连通图中含某些指定边的生成树的计数

应用线性代数的方法 ,推广了Kirchhoff矩阵—树定理、得到了连通图中含某些指定边的所有生成树的计数公式 ;