关于图运算的测地数

作者：叶永升; 莫艳红; 吕长虹图运算测地线定向图有向图最短路图g集合基数点集

摘要：对于图 G(或有向图 D)内的任意两点 u和 v, u- v测地线是指在 u和 v之间(或从 u到 v)的最短路. I(u;v)表示位于 u- v测地线上所有点的集合,对于 S V(G)(或 V(D)), I(S)表示所有 I(u,v)的并,这里 u,v∈ S.G(或 D)的测地数 g(G)(或 g(D))是使 I(S)=V(G)(或 I(S)=V(D))的点集 S的最小基数. G的下测地数 g- (G)=min{g(D):D是 G的定向图 }, G的上测地数 g+ (G)=max{g(D):D是 G的定向图 }.对于两个图 G和 H, u∈ V(G)和 v∈ V(H),在 u和 v之间加一条边,然后再收缩这条边 uv所得的图,记为 Gu o Hv. 本文主要研究图 Gu o Hv的测地数和上 (下 )测地数 .

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社