在图的支撑树最优化中,有两个重要的优化指标:伸展度和层叠度.由此提出两个组合最优化问题:最小伸展支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,这些边的最大伸展距离为最小;最小层叠支撑树问题,求一个图的支撑树,使得当所有边嵌入到此支撑树时,每条树边上的最大重叠边数为最小.这两个问题确定出两个图论参数:树展和树层.本文主要论述树展和树层的基本结构性质,包括圈与余圈的对偶性、极值性、上下界、最优性刻画和最优值计算等.
科研之友
微信
新浪微博
Facebook
分享链接
