有趣的图论

近二十年来,在数学论坛上出现了一门十分活跃的学科—图论。无论从它的文章数量、杂志种类、应用广泛程度以及每年国际性学术会议的数量上,都显示了图论的发达兴旺景象。本文试图尽量多用一些简单有趣的例子,对图论的部分内容给以简单介绍。     

具有限制的最小 k一个边不交支撑树问题

本文推广了刘振宏等具有次限制最小树算法,给出了求具有限制的最小 k 个边不交支撑树算法.该算法已在 IBM-PC 机上用 Fortran 语言实现,其时间复杂性为max{O(k~2|E|~2|V|~2),O(k~3|V|~4|E|)}.     

Parity-factor and its Covering

Amahashi gives a necessary and sufficient condition for a graph to have a {1,3, … , 2n-1} -factor. Here we give some necessary and sufficient conditions for a graph to contain a parity-factor,and also we obtain a necessary and sufficient condition for a graph to have parity-factor covering.     

关于拟阵的最小限制基问题

关于求拟阵的最小基问题,众所周知,有很简明的算法(被称为Greedy Algorithm)。本文考虑求带剖分限制的最小基问题,同样也给出了较简单的有效算法,最后举例说明,许多组合问题都可以化成拟阵的最小限制基问题而求解。     

3－连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ—４的３－连通ｋ－正则无爪图是Ｈａｍｉｌｔｏｎ的．     

2-连通 k-正则图的 Hamilton 圈的存在性

本文改进了[1,2]中的结果,证明了顶点数 n≤3k 3时,2-连通 k-正则的图在k≥6时有 Hamilton 圈.这一结果是最好可能的,因为在 n=3k 5或3k 4时,均有反例.     

最小极差 s-子图的算法

一、前言在网络优化问题中,以往研究的问题一般是给定网络 G 和限制条件 s,求满足 s 的 G的子图(如树形图,有向路,匹配等),使该子图的权达到最大(或最小)。但有些网络优化问题不要求子图的权达到最大(或最小),而要求子图中各弧的权较为“均匀”,即要求子图中最大弧权与最小弧权之差达到最小。这就提出了最小极差 s-子图的问题。     

A SOLUTION TO ONE OF KANO''''S CONJECTURES CONCERNING k-th MAXIMAL SPANNING TREES

Let (G) be the collection of all spanning trees of a connected and weighted graph G,and F_1, F_2,…,F_m the partition of (G) such that F_i is the set of i-th maximal spanning trees of G.Kano conjectured that for any A∈F_1 and every integer k,1≤k≤m,there exists T∈F_k such that|T/A| k—l.This paper gives the conjecture a very simple proof,and related results.     

2-CONNECTED k-REGULAR GRAPHS ON AT MOST 3k+3 VERTICES TO BE HAMILTONIAN (CONTINUED)

Let X~* and Y~* be generated by S(?){v_0},where G(S)is Hamiltonian connected and|X~*|=x~*,|Y~*|=Y~* and S_1~*,S_2~*,…,S_(x*)~* be the sets of vertices contained in the opensegments of C between vertices of X~*.Let S_1~*,x_1,S_2~*,x_2,…,S_(x*)~*,x_(?)~* be the segmentsand vertices of X~* in order around C.S_i~* is said to be an X~*(3)-interval if one ofx_(i-1)and x_i belongs to X_j~*—X_2~*.Let S=S_1~*,and S={a_1,c_1,c_2,…,c_1,b_1}.It is easy to see that the statement inLemma 2 can be modified as(?)({a_1,b_1},S_i~*)≤(?)