A Study Of Short Circles And Related Problems On The Map

In this paper,according to the breadth-first-tree,we mainly find kinds of shortest cycles on the surface embedded graph.And this research plays an important role in the research of graph theory.In the third chapter of this paper,how to find a breadth-first-tree on graphs is mainly studied.Graphs are divided into connected graphs with the same edge weighted and with the different edge weighted.There is a breadth-first tree which can be found by the method of breadth first search on the graph.And we summarize that a breadth-first-tree can be found under at most O(n)polynomial time for connected graphs with the same edge weighted and a breadth-first-tree can be found under at most O(n2)polynomial time for connected graphs with the different edge weighted.In the fourth chapter of this paper,how to find a shortest cycle on the embedded graph is mainly studied.Embedded graphs are divided into connected graphs with the same edge weighted and with the different edge weighted.In the section 1,we get some conclusions:If the ??embedded graph has ? twosided cycles,then a shortest ?-twosided cycle can be found under at most O((n+m2)n)polynomial time for a connected graph with the same edge weighted.If the ? embedded graph has ?-separating cycle,then a shortest ?-separating cycle can be found under at most O((n+m2)n)polynomial time for a connected graph with the same edge weighted.What's more,for a special surface embedded graph--an LEW-embedded graph with the same edge weighted,if the girth of graph G is equal or greater than 5,then a shortest surface contractible cycle of G can be found at most O((n+m)n)polynomial time.In the section 2,we get some conclusions:If the ?-embedded graph has ?-twosided cycles,then a shortest?-twosided cycle can be found under at most O((n2+m2)n)polynomial time for a connected graph with the different edge weighted.If the ?-embedded graph has ?-separating cycle,then a shortest ?-separating cycle can be found under at most O((2 + m2)n)polynomial time for a connected graph with the different edge weighted.What's more,for a special surface embedded graph--an LEW-embedded graph with the different edge weighted,if the girth of graph G is equal or greater than 5,then a shortest surface contractible cycle of G can be found at most O((n2+m)n)polynomial time.