Bobylova E. The Methods and Algorithms of Recognition of the Graphs on the Prifractile and their Application

The dissertation is devoted to the studing of the prifractal graphs. The properties of the canonical prifractal graphs, the old edges of which aren't crossed, and are generated by the full n-vertex zatravka, wheel, star, are studied. The full canonical prifractal graphs, the old edges of which are crossed, are investigated. For the first time the full noncanonical prifractal graphs were investigated. Also the properties of the full noncanonical prifractal graphs, the old edges which are crossed, and the amount of the vertexes, which are replaced, is arbitrary, were examined. On the base of the characters of the enumerated graphs the methods and polynomial algorithms of their recognition were constructed. For the first time complexity of the some NP-full problems (the task of vertex cover, the task of the dominating set, the problem of the partition on the forests, the task of the Hamilton cycle) was explored on this rgaphs.The statistically exact and asymptotically effective algorithms of the isolation of the framing dyadic tree which has a limited degree were constructed.