关于图的路色数的一些结果

本文研究图的路色数，首无得到图的路色数的一些基本性质，其次给出了G满足X（G；P2）小于等于2的一个充分必要条件，该条件可以有效地应用于极大平面图和2－连通极大外平面图，最后证明了图的K－路色数问题NP-完全性（K≥3）。     

(m,n)构形的带宽

确定一个图(或对称矩阵)的带宽,是在计算机科学及其它领域中有着重要意义的组合问题。但求一般图的带宽(甚至简单到求树的带宽)是属于NP难度的。至于求特殊图的带宽,近年来有一些成果。1976年,Dewdney在第七届美国东南组合论、图论及计算会议上提出三个未解决的问题。其一是求环面上格子图C_m×C_n的带宽,已为李乔、陶懋颀和     

支撑树端点数介值定理的一个简单证明

G.Chartrand在第四届国际图论会议(1980)上提出这样一个问题:若一连通图G分別有含m和n个端点的支撑树,m相似文献   

求欧拉图所有初级圈覆盖的一个算法

本文利用深探法设计了一个求欧拉图一切无公共边的初级图覆盖(简称覆盖)的算法它由两个子算法组成:算法(Ⅰ):求欧拉图中过一边 e 的所有初级级图.算法 (Ⅱ):求欧拉图的一切无公共边的初级图覆盖.文中定理和算法对有向欧拉图也完全适用。     

圈幂补图的带宽与拓扑带宽

圈幂补图的带宽与拓扑带宽原晋江，林诒勋（郑州大学数学系）在电网络的设计中，常需将一个图的顶点安装在一直线的整点上，使得最长边的长度尽可能小；有时为进一步缩短最长边，允许在图中添加剖分点．由此引出图的带宽和拓扑带宽问题［‘ｊ．设Ｇ（Ｖ，Ｅ）是一简单图．...     

批数确定的分批排序问题最优解的结构性质

研究了目标函数为总完工时间、工件恰分N批的单机分批排序问题最优解的结构性质,其中N为1与工件数之间的任意整数.分批方式为继列分批和平行分批.     

对概率模型的认识

对概率论基础历来有多元的认识,历史上不同观点的争论(如客观与主观)持续不断.如今Kolmogorov公理模型在数学中被广泛接受.但是它只是说:"概率"是一个正则化测度,恰如长度、体积、质量一样,并且与随机现象无关.事实上,概率和任意正则化的物理测度都满足这个公理系统.所以它不是概率概念的精确定义.本文尝试给出另一个模型,它可缩小Kolmogorov模型与直观背景之间的间隙,统一历史上的各种定义,并给一些争论问题以合理的解释.     

关于偶匹配可扩图中删去两个点(英文)

设G是含有完美匹配的简单图.称G是偶匹配可扩的,如果G中导出子图是偶图的匹配M都可以扩充为G的完美匹配.研究了在偶匹配可扩图中删去两个顶点后该图的性质.这些性质对于偶匹配可扩图的进一步研究会有帮助.     

电力网调度时间表问题的动态规划算法

为保持电力系统的平稳供电,安排每一电厂(站)所有机组的检修时间是极为重要.作为系统工程的应用,本文给出这一时间表问题的数学模型及动态规划算法.