For a graph G and an positive integer k,letσ_k(G)denote the minimum degree sum of k independent vertices of G.It has been proved that if a connected claw-free graph G satisfiesσ_(k+1)(G)≥|G|-k,then G has a spanning...For a graph G and an positive integer k,letσ_k(G)denote the minimum degree sum of k independent vertices of G.It has been proved that if a connected claw-free graph G satisfiesσ_(k+1)(G)≥|G|-k,then G has a spanning k-ended tree.We also know that the lower bound|G|-k is sharp.In this paper,we give a simple proof of this theorem by using another t-ended system.展开更多
As far as the minimal spanning tree problem for the digraph with asymmetric weightsis concerned, an explicit integer programming model is proposed, which could be solved successfullyusing the integer programming packa...As far as the minimal spanning tree problem for the digraph with asymmetric weightsis concerned, an explicit integer programming model is proposed, which could be solved successfullyusing the integer programming packages such as LINDO, and furthermore this model is extendedinto the stochastic version, that is, the minimal spanning tree problem for the digraph with theweights is not constant but random variables. Several algorithms are also developed to solve themodels. Finally, a numerical demonstration is given.展开更多
Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a f...Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.展开更多
With the purpose of making calculation more efficient in practical hydraulic simulations, an improved algorithm was proposed and was applied in the practical water distribution field. This methodology was developed by...With the purpose of making calculation more efficient in practical hydraulic simulations, an improved algorithm was proposed and was applied in the practical water distribution field. This methodology was developed by expanding the traditional loop-equation theory through utilization of the advantages of the graph theory in efficiency. The utilization of the spanning tree technique from graph theory makes the proposed algorithm efficient in calculation and simple to use for computer coding. The algorithms for topological generation and practical implementations are presented in detail in this paper. Through the application to a practical urban system, the consumption of the CPU time and computation memory were decreased while the accuracy was greatly enhanced compared with the present existing methods.展开更多
Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatoria...Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.展开更多
As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality ...As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.展开更多
As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a nume...As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.展开更多
The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that ther...The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.展开更多
There are many methods to calculate seismic fractal at present. However, there are still more or less questions to every method. In this paper, we introduce a new way to calculate seismic fractal-the minimal spanning ...There are many methods to calculate seismic fractal at present. However, there are still more or less questions to every method. In this paper, we introduce a new way to calculate seismic fractal-the minimal spanning tree. We make an important improvement for this method. By studying some seismic events of four regions including Wushi, Wusu, Tangshan and Haicheng, we obtain that before the strong earthquake occurrence, the multi-fractal spectrum of the space-time distribution of earthquakes changes from centralized to loose. The result shows that the complexity of fractal structure and the inhomogeneity of the space-time distribution of earthquakes are both increasing. By studying the numerical simulation of point sets, we draw the conclusion that the physical essence of multi-fractal spectrums before and after a strong earthquake occurrence is a changing process from homogeneous to inhomogeneous, from simple to complex.展开更多
Since the outbreak and spread of corona virus disease 2019(COVID-19),the prevalence of mental disorders,such as depression,has continued to increase.To explore the abnormal changes of brain functional connections in p...Since the outbreak and spread of corona virus disease 2019(COVID-19),the prevalence of mental disorders,such as depression,has continued to increase.To explore the abnormal changes of brain functional connections in patients with depression,this paper proposes a depression analysis method based on brain function network(BFN).To avoid the volume conductor effect,BFN was constructed based on phase lag index(PLI).Then the indicators closely related to depression were selected from weighted BFN based on small-worldness(SW)characteristics and binarization BFN based on the minimum spanning tree(MST).Differences analysis between groups and correlation analysis between these indicators and diagnostic indicators were performed in turn.The resting state electroencephalogram(EEG)data of 24 patients with depression and 29 healthy controls(HC)was used to verify our proposed method.The results showed that compared with HC,the information processing of BFN in patients with depression decreased,and BFN showed a trend of randomization.展开更多
Classical mathematical morphology operations use a fixed size and shape structuring element to process the whole image.Due to the diversity of image content and the complexity of target structure,for processed image,i...Classical mathematical morphology operations use a fixed size and shape structuring element to process the whole image.Due to the diversity of image content and the complexity of target structure,for processed image,its shape may be changed and part of the information may be lost.Therefore,we propose a method for constructing salience adaptive morphological structuring elements based on minimum spanning tree(MST).First,the gradient image of the input image is calculated,the edge image is obtained by non-maximum suppression(NMS)of the gradient image,and then chamfer distance transformation is performed on the edge image to obtain a salience map(SM).Second,the radius of structuring element is determined by calculating the maximum and minimum values of SM and then the minimum spanning tree is calculated on the SM.Finally,the radius is used to construct a structuring element whose shape and size adaptively change with the local features of the input image.In addition,the basic morphological operators such as erosion,dilation,opening and closing are redefined using the adaptive structuring elements and then compared with the classical morphological operators.The simulation results show that the proposed method can make full use of the local features of the image and has better processing results in image structure preservation and image filtering.展开更多
This paper provides a method of producing a minimum cost spanning tree(MCST)using set operations.It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and...This paper provides a method of producing a minimum cost spanning tree(MCST)using set operations.It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm.This algorithm uses the FDG(formula to divide elements into groups)to sort(the FDG sorts a sequence of n elements in expected tir O(n))and uses the method of path compression to find and to unite.Therefore.n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).展开更多
Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology...Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology of hepatitis C virus(HCV)infection.On the other hand,Kemeny’s constant(Ω)is a beneficial quantifier characterizing the universal average activities of a Markov chain.This network invariant infers the expressions of the expected number of time-steps required to trace a randomly selected terminus state since a fixed beginning state si.Levene and Loizou determined that the Kemeny’s constant can also be obtained through eigenvalues.Motivated by Levene and Loizou,we deduced the Kemeny’s constant and the number of spanning trees of hexagonal ring network by their normalized Laplacian eigenvalues and the coefficients of the characteristic polynomial.Based on the achieved results,entirely results are obtained for the M鯾ius hexagonal ring network.展开更多
Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding co...Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.展开更多
A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G conta...A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G contains a spanning 3-ended tree, where σk（G） = min{∑es deg（v） ： S is an independent set of G with ｜S｜ = k}.展开更多
Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-t...Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.展开更多
For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of ...For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of T.The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized.In application to design of communication networks,the loads of all branches leading from the switch center should be as balanced as possible.In this paper,we prove that the problem is strongly NP-hard even for bipartite graphs.Moreover,the problem is shown to be polynomially solvable for split graphs,and exact formulae for special graph familis,say Kn_(1),n_(2),...,n_(k)and P_(m)×P_(n),are presented.展开更多
In Corley′s algorithm for all efficient spanning trees, final solutions include many spanning trees, which are not all efficient. In this paper, a new algorithm is presented, which corrects and modifies Corley′s alg...In Corley′s algorithm for all efficient spanning trees, final solutions include many spanning trees, which are not all efficient. In this paper, a new algorithm is presented, which corrects and modifies Corley′s algorithm. A necessary condition is developed for the subtree of an efficient spanning tree. According to the condition the new algorithm is established and its efficiency is proved.展开更多
Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algo...Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algorithm for electric distribution network reconfiguration is proposed.Above all,all spanning trees of simplified graph of distribution network are found.Tie branches are obtained with spanning tree subtracted from simplified graph.There is one and only one switch open on each tie branch.Decimal identity number of open switch on each tie branch is taken as the optimization variable.Therefore,the length of chromosome is very short.Each spanning tree corresponds to one subpopulation.Gene operations of each subpopulation are implemented with parallel computing method.Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation.Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation,which result in very low searching efficiency,are completely overcome.High calculation speed and superior capability of the proposed method are validated by two test cases.展开更多
Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a ...Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.展开更多
文摘For a graph G and an positive integer k,letσ_k(G)denote the minimum degree sum of k independent vertices of G.It has been proved that if a connected claw-free graph G satisfiesσ_(k+1)(G)≥|G|-k,then G has a spanning k-ended tree.We also know that the lower bound|G|-k is sharp.In this paper,we give a simple proof of this theorem by using another t-ended system.
文摘As far as the minimal spanning tree problem for the digraph with asymmetric weightsis concerned, an explicit integer programming model is proposed, which could be solved successfullyusing the integer programming packages such as LINDO, and furthermore this model is extendedinto the stochastic version, that is, the minimal spanning tree problem for the digraph with theweights is not constant but random variables. Several algorithms are also developed to solve themodels. Finally, a numerical demonstration is given.
文摘Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.
文摘With the purpose of making calculation more efficient in practical hydraulic simulations, an improved algorithm was proposed and was applied in the practical water distribution field. This methodology was developed by expanding the traditional loop-equation theory through utilization of the advantages of the graph theory in efficiency. The utilization of the spanning tree technique from graph theory makes the proposed algorithm efficient in calculation and simple to use for computer coding. The algorithms for topological generation and practical implementations are presented in detail in this paper. Through the application to a practical urban system, the consumption of the CPU time and computation memory were decreased while the accuracy was greatly enhanced compared with the present existing methods.
基金This work is supported by the National Natural Science Foundation of China under Grant 61772179the Hunan Provincial Natural Science Foundation of China under Grant 2019JJ40005+3 种基金the Science and Technology Plan Project of Hunan Province under Grant 2016TP1020the Double First-Class University Project of Hunan Province under Grant Xiangjiaotong[2018]469the Open Fund Project of Hunan Provincial Key Laboratory of Intelligent Information Processing and Application for Hengyang Normal University under Grant IIPA19K02the Science Foundation of Hengyang Normal University under Grant 19QD13.
文摘Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.
基金the National Natural Science Foundation of China (No. 79870030).
文摘As far as the weighted digraph is considered, an optimal directed spanning tree algorithm called table based algorithm (TBA) is proposed in the paper based on the table instead of the weighted digraph. The optimality is proved, and a numerical example is demonstrated.
文摘As far as the weight digraph is considered, based on the table instead of the weightdigraph, an optimal spanning tree method called the Table Operations Method (TOM) is proposed.And the optimality is proved and a numerical example is demonstrated.
文摘The first problem considered in this article reads： is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs？ It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n3/2, where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n3/2.
文摘There are many methods to calculate seismic fractal at present. However, there are still more or less questions to every method. In this paper, we introduce a new way to calculate seismic fractal-the minimal spanning tree. We make an important improvement for this method. By studying some seismic events of four regions including Wushi, Wusu, Tangshan and Haicheng, we obtain that before the strong earthquake occurrence, the multi-fractal spectrum of the space-time distribution of earthquakes changes from centralized to loose. The result shows that the complexity of fractal structure and the inhomogeneity of the space-time distribution of earthquakes are both increasing. By studying the numerical simulation of point sets, we draw the conclusion that the physical essence of multi-fractal spectrums before and after a strong earthquake occurrence is a changing process from homogeneous to inhomogeneous, from simple to complex.
基金supported by the National Natural Science Foundation of China(Nos.61962034,61862058)Longyuan Youth Innovation and Entrepreneurship Talent(Individual)Project and Tianyou Youth Talent Lift Program of Lanzhou Jiaotong Univesity。
文摘Since the outbreak and spread of corona virus disease 2019(COVID-19),the prevalence of mental disorders,such as depression,has continued to increase.To explore the abnormal changes of brain functional connections in patients with depression,this paper proposes a depression analysis method based on brain function network(BFN).To avoid the volume conductor effect,BFN was constructed based on phase lag index(PLI).Then the indicators closely related to depression were selected from weighted BFN based on small-worldness(SW)characteristics and binarization BFN based on the minimum spanning tree(MST).Differences analysis between groups and correlation analysis between these indicators and diagnostic indicators were performed in turn.The resting state electroencephalogram(EEG)data of 24 patients with depression and 29 healthy controls(HC)was used to verify our proposed method.The results showed that compared with HC,the information processing of BFN in patients with depression decreased,and BFN showed a trend of randomization.
基金National Natural Science Foundation of China(No.61761027)。
文摘Classical mathematical morphology operations use a fixed size and shape structuring element to process the whole image.Due to the diversity of image content and the complexity of target structure,for processed image,its shape may be changed and part of the information may be lost.Therefore,we propose a method for constructing salience adaptive morphological structuring elements based on minimum spanning tree(MST).First,the gradient image of the input image is calculated,the edge image is obtained by non-maximum suppression(NMS)of the gradient image,and then chamfer distance transformation is performed on the edge image to obtain a salience map(SM).Second,the radius of structuring element is determined by calculating the maximum and minimum values of SM and then the minimum spanning tree is calculated on the SM.Finally,the radius is used to construct a structuring element whose shape and size adaptively change with the local features of the input image.In addition,the basic morphological operators such as erosion,dilation,opening and closing are redefined using the adaptive structuring elements and then compared with the classical morphological operators.The simulation results show that the proposed method can make full use of the local features of the image and has better processing results in image structure preservation and image filtering.
文摘This paper provides a method of producing a minimum cost spanning tree(MCST)using set operations.It studies the data structure for implementation of set operations and the algorithm to be applied to this structure and proves the correctness and the complexity of the algorithm.This algorithm uses the FDG(formula to divide elements into groups)to sort(the FDG sorts a sequence of n elements in expected tir O(n))and uses the method of path compression to find and to unite.Therefore.n produces an MCST of an undirected network having n vertices and e edges in expected time O(eG(n)).
文摘Spanning tree(τ)has an enormous application in computer science and chemistry to determine the geometric and dynamics analysis of compact polymers.In the field of medicines,it is helpful to recognize the epidemiology of hepatitis C virus(HCV)infection.On the other hand,Kemeny’s constant(Ω)is a beneficial quantifier characterizing the universal average activities of a Markov chain.This network invariant infers the expressions of the expected number of time-steps required to trace a randomly selected terminus state since a fixed beginning state si.Levene and Loizou determined that the Kemeny’s constant can also be obtained through eigenvalues.Motivated by Levene and Loizou,we deduced the Kemeny’s constant and the number of spanning trees of hexagonal ring network by their normalized Laplacian eigenvalues and the coefficients of the characteristic polynomial.Based on the achieved results,entirely results are obtained for the M鯾ius hexagonal ring network.
文摘Let P n be a set of n points in the unit square S,l(P n) denoe the length of the minimum spanning tree of P n, andC n= max P nSl(P n), n=2,3,… In this paper,the exact value of C n for n=2,3,4 and the corresponding configurations are given. Additionally,the conjectures of the configuration for n=5,6,7,8,9 are proposed.
基金Supported by the National Natural Science Foundation of China,Tian Yuan Special Foundation(Grant No.11426125)by Educational Commission of Liaoning Province(Grant No.L2014239)
文摘A spanning tree with no more than 3 leaves is called a spanning 3-ended tree. In this paper, we prove that if G is a k-connected （k≥ 2） almost claw-free graph of order n and σk＋3（G） ≥ n ＋ k ＋ 2, then G contains a spanning 3-ended tree, where σk（G） = min{∑es deg（v） ： S is an independent set of G with ｜S｜ = k}.
基金supported by National Key R&D Program of China(Grant No.2021YFA1000403)National Natural Science Foundation of China(Grant No.11991022)+1 种基金the Strategic Priority Research Program of Chinese Academy of Sciences(Grant No.XDA27000000)the Fundamental Research Funds for the Central Universities。
文摘Spanning tree problems with specialized constraints can be difficult to solve in real-world scenarios,often requiring intricate algorithmic design and exponential time.Recently,there has been growing interest in end-to-end deep neural networks for solving routing problems.However,such methods typically produce sequences of vertices,which make it difficult to apply them to general combinatorial optimization problems where the solution set consists of edges,as in various spanning tree problems.In this paper,we propose NeuroPrim,a novel framework for solving various spanning tree problems by defining a Markov decision process for general combinatorial optimization problems on graphs.Our approach reduces the action and state space using Prim's algorithm and trains the resulting model using REINFORCE.We apply our framework to three difficult problems on the Euclidean space:the degree-constrained minimum spanning tree problem,the minimum routing cost spanning tree problem and the Steiner tree problem in graphs.Experimental results on literature instances demonstrate that our model outperforms strong heuristics and achieves small optimality gaps of up to 250 vertices.Additionally,we find that our model has strong generalization ability with no significant degradation observed on problem instances as large as 1,000.Our results suggest that our framework can be effective for solving a wide range of combinatorial optimization problems beyond spanning tree problems.
基金Key Research Project of Henan Higher Education Institutions(No.20A110003).
文摘For a spanning tree T of graph G,the centroid of T is a vertex v for which the largest component of T-v has as few vertices as possible.The number of vertices of this component is called the centroid branch weight of T.The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized.In application to design of communication networks,the loads of all branches leading from the switch center should be as balanced as possible.In this paper,we prove that the problem is strongly NP-hard even for bipartite graphs.Moreover,the problem is shown to be polynomially solvable for split graphs,and exact formulae for special graph familis,say Kn_(1),n_(2),...,n_(k)and P_(m)×P_(n),are presented.
文摘In Corley′s algorithm for all efficient spanning trees, final solutions include many spanning trees, which are not all efficient. In this paper, a new algorithm is presented, which corrects and modifies Corley′s algorithm. A necessary condition is developed for the subtree of an efficient spanning tree. According to the condition the new algorithm is established and its efficiency is proved.
文摘Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algorithm for electric distribution network reconfiguration is proposed.Above all,all spanning trees of simplified graph of distribution network are found.Tie branches are obtained with spanning tree subtracted from simplified graph.There is one and only one switch open on each tie branch.Decimal identity number of open switch on each tie branch is taken as the optimization variable.Therefore,the length of chromosome is very short.Each spanning tree corresponds to one subpopulation.Gene operations of each subpopulation are implemented with parallel computing method.Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation.Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation,which result in very low searching efficiency,are completely overcome.High calculation speed and superior capability of the proposed method are validated by two test cases.
基金Supported by the National Natural Science Foundation of China (No.10771091)Project of Knowledge and Science Innovation Program of Northwest Normal University (Grant No.NWNU-KJCXGC-3-47)
文摘Some structures of spanning trees with many or less leaves in a connected graph are determined.We show（1） a connected graph G has a spanning tree T with minimum leaves such that T contains a longest path,and（2） a connected graph G on n vertices contains a spanning tree T with the maximum leaves such that Δ（G） =Δ（T） and the number of leaves of T is not greater than n D（G）＋1,where D（G） is the diameter of G.
