A RESULT ON WOODALL''''S CONJECTURE

The binding number of a simple graph G=(V,E),denoted by Bind(G),isdefined as Bind(G)-min{|г(X)|/|X|φ≠x V(G),г(X)≠V(G)}where г(X)={u|(u,v)∈E(G),v∈X}。 In [1] Woodall had shown that G contains a triangle if Bind (G)≥[1+5~(1/2)]/2≈     

线性目标函数下的 greedy-结构

有限集合E的一个子集类■2~E,如果对任意的 Y∈■及 X■Y,总有 X∈■,我们则称(E,■)为一独立系统.1971年 J.Edmonds 指出,独立系统(E,■)对任意线性目标函数其greedy基恒为最优基的充分必要条件是■满足交换公理,即对任意的 X,Y∈■,及|Y|>|X|,则存在 y∈Y\X,使 X∪{y}∈■.这时(E,■)是一拟阵.