| Let D =(V,X)be a strong connected digraph.A spanning subgraph H of D that is strong connected is said to be minimal if H-a is not strong connected for any arc a in H.It is readily to see that D might contain distinct minimal subgraphs,which is analogous with spanning trees in connected graph.We call a minimal subgraph DM of D minimum subgraph if it contains the minimum number of arcs among all minimal subgraphs of D.The problem of finding a minimum subgraph from a given digraph D is called MSSS-problem.It is quite useful in many cases to resolve the MSSS-problem for D,but it could be rather hard to do so,for we have to find a Hamilton cycle in D if D is itself hamiltonian.In this thesis,we develop,for two important classes of digraphs,a machinery that enables us to find a minimum subgraph from the given digraph.In the 1st chapter,we first present the background relevant to our problem and define those notions precisely.After that,we introduce the fundamental idea of dealing with the problem and state our main results.In the 2nd chapter,we develop step by step the method we employ to find a minimum subgraph from a given digraph.At the beginning,we give the the definition of deletable arc,which is one of key concepts in our algorithm.Moreover,one can see in the 2nd section that the set consisting of all deletable arcs in D can be obtained by means of the depth-first search algorithm.In the last section,we first focus on how to construct an undirected graph GA from the set A(D)composed of all deletable arcs in D,and then show how to reduce the MSSS—problem to the problem of finding a maximum independent set of GA.In the third and fourth chapters,we use the algorithm established in the second chapter to cope with the MSSS-problem for two important classes of graphs.More precisely,we show that if the undirected graph GA constructed from A(D)is a Kneser graph or an interval graph,our algorithm can find a minimum subgraph of the given digraph in polynomial time. |
PDF Full Text Request