K-桥图的本原指标

K-桥图是由连接A,B两点的K条内部不交路所组成的图.计算得到本原K-桥图的本原指标等于m-1或n-1,其中m是最大奇圈的圈长,而n是A,B间最长奇路(偶路)与最短偶路(奇路)的长度之和.

k-桥图匹配最大根的极值

设G是有n个点的图,μ(G,x)表示图G的匹配多项式,M_(1)(G)表示多项式μ(G,x)的最大根,称为匹配最大根。把k条路P_(a_(1)+2),P_(a_(2)+2),…,P_(a_(k)+2)的左右2个端点分别黏结成2个点后得到的图称为k-桥图,记为θ_(k)(a_(1),a_(2),…,a_(k))。有n个点且每一条路上的点数几乎相等的k-桥图记为θ_(k)^(*)(n)。证明了:在n个点的k-桥图中匹配最大根取得最小的图是θ_(k)^(*)(n),最大的图是θ_(k)(k-20,1,1…,1,n-k);在n个点的任意k-桥图中匹配最大根取得最小的图是2-桥图(圈)C_(n),最大的图是(n-1)-桥图θ_(n-1)(0,1,1…,1)。