In a graph G=(V,E),a subset F(?)V is a feedback vertex set of G if the subgraph V\F is acyclic. Let fv(G) (resp. fa(G)) denote the minimum cardinality over all feedback vertices (resp. arcs) sets of the graph G.The minimum feedback vertex set problem has been researched and used in various areas. It can be used that wavelength converters are installed into the fiber network, broadcasting storms are avoided through network transmission, also avoiding computer operating systems deadlock etc.The objective of this assignment, I analysis it's theoretical and practical value, implementing and improving the feedback number of generalized Kautz digraphs GK(d, n) and folded hypercube FQn through researching the mathematics theories and related computer complexity feedback ways.Regarding to the generalized Kautz digraphs GK(d, n), this paper divides V(GK(d, n)) into eight subsets. Bases on the subdivision, this paper provides and proves an upper bound of the feedback number of GK(d, n), that is,Located throughout this assignment, n dimensional folded hypercube FQn,I present an appreciation for construct acyclic sub graph and improve the feedback number of GK (d,n) upper bound as follows, that is,...
|