独立集上最小最大比值和最小极差比值问题的算法

定义在集Ｅ的子集Ｘ上的两个实函数的比值的极大、极小值分别记为Ｍ（Ｘ）和ｍ（Ｘ），极差△（Ｘ）＝Ｍ（Ｘ）－ｍ（Ｘ）。本文给出在秩为ｒ的独立系统（Ｅ，Ｉ）（ＩＰ（Ｅ））中求ｍａｘ｛ｍ（Ｘ）｜Ｘ∈Ｉ｜，｜Ｘ｜＝ｒ｝和ｍｉｎ｛△（Ｘ）｜Ｘ∈Ｉ｜，｜Ｘ｜＝ｒ｝的有效算法及其证明。     

图的同构因子分解──概况与问题

系统介绍了图的同构因子分解的已有成果和尚待解决的许多问题．     

图的匹配设计的组合和矩阵方法

完全图Ｋｎ 中若存在一族ｋ－匹配,使得Ｋｎ 中任一对独立边恰属于λ个ｋ－匹配,则称Ｋｎ 存在ＭＡＴＣＨ（ｎ,ｋ,λ）－设计; 同样定义完全二部图Ｋｎ, ｎ的匹配设计。综述研究这两种匹配设计所采用的组合设计和图论方法及作者新近提出的矩阵方法,简述这一课题的研究成果及未解决的问题。     

n阶极大外平面图的构造法

图的同构的判定是图论研究中的重要课题之一,非同构的极大外平面图的计数问题尚未解决.提出一种判定图同构的方法,其原理是赋予每个无标号极大外平面图一个n×(n-3)阶0-1矩阵,证明了矩阵与极大外平面图一一对应,矩阵相同的图彼此同构.构造所有可能的n阶极大外平面图,并用上述方法除去其中同构者,所有n阶无标号极大外平面图被不重不漏地构造出来,同时得到其总个数,解决了有关极大外平面图同构与计数问题.     

超立方图和超立方有向图的同构因子分解

图Ｇ＝（Ｖ，Ｅ）的一个同构因子分解是边集Ｅ的一个划分：｛Ｅ１，Ｅ２，…，Ｅｔ｝，使得生成子图（Ｖ， Ｅ１），…，（Ｖ，Ｅｔ）都彼此同构。若 Ｈ≌（Ｖ，Ｅ１），记为 Ｈ［Ｇ或 ｔ］Ｇ．若对每个ｔ≥２．当　　　时．均有：ｔＧ，则称Ｇ为有理图．文章证明了超立方图（ｈｙｐｅｒｃｕｂｅ）和超立方有向图都是有理图．     

Spectral Radius of Hamiltonian Planar Graphs and Outerplanar Graphs

All graphs considered here are finiteundirected,without loops and multiple edges.LetG be a graph with n verticesand m edges,d G( v) bethe degree of the vertex v in G,and Cn and Pn bethe cycle and path with n vertices. Thecomplement of a subgraph Y of G is the graphobtained from G by deleting all the edges in Y andis denoted by YG.The spectral radius r( G) of G isthe largest eigenvalue of its adjacent matrix.Aplanar graph G is called a maximal planar graph iffor every pairof nonadjacent…