CAJ | 학술논문

边赋非负权无向简单图的一簇顶点两两不相交的子树称为它的一个d-子树划分(d为非负实数),如果这些子树的顶点集的并等于此图的顶点集.且每棵子树的直径不超过d.图的d-子树划分问题就是求它的一个含子树数最少的d-子树划分及其所含的子树数.d-子树划分问题在有线通信网络、道路交通网络、城市供水网络、电力传输网络等网络的运行管理、维护与测试中具有很强的应用背景.文中证明了对任意正实数d,边赋非负权二分平面图的d-子树划分问题是NP-完全问题;提出了求解边赋非负权树d-子树划分问题的一个线性时间算法,详细地讨论了算法的实现策略.所提出的算法具有简明易实现、耗费时间少等特点.
변부비부권무향간단도적일족정점량량불상교적자수칭위타적일개d-자수화분(d위비부실수),여과저사자수적정점집적병등우차도적정점집.차매과자수적직경불초과d.도적d-자수화분문제취시구타적일개함자수수최소적d-자수화분급기소함적자수수.d-자수화분문제재유선통신망락、도로교통망락、성시공수망락、전력전수망락등망락적운행관리、유호여측시중구유흔강적응용배경.문중증명료대임의정실수d,변부비부권이분평면도적d-자수화분문제시NP-완전문제;제출료구해변부비부권수d-자수화분문제적일개선성시간산법,상세지토론료산법적실현책략.소제출적산법구유간명역실현、모비시간소등특점.
A d-subtree partition of undirected simple graph with nonnegative edge-weights is a collection of pairwise vertex-disjoint subtrees such that the union of vertex sets of these subtrees is equal to the vertex set of the graph and each subtree has diameter of no more than d, where d is a nonnegative real. The d-subtree partition problem of a graph is to find a d-subtree partition that has the smallest cardinality among all d-subtree partitions of the graph and the cardinality. The d-subtree partition problem has found some applications in operation management, maintenance and test of network such as wire communication network, road traffic network, urban water supply network and power transmission network. In this paper, it is proved that the d-subtree partition problem is NP-complete for bipartite planar graphs with nonnegative edge-weights for any positive real d. A linear time algorithm is presented to solve the d-subtree partition problem for trees with nonnegative edge-weights. Realization strategies for the algorithm are discussed in detail. The algorithm presented can be realized easily and requires less time.