Частный случай задачи распознавания полного неканонического предфрактального графа

Abstract

В работе исследуются свойства неканонических предфрактальных графов с замещением вершин по определенному принципу. Построены алгоритмы распознавания предфрактальных графов с одной и k замещаемыми вершинами. Решена задача ГАМИЛЬТОНОВ ЦИКЛ для неканонического предфрактального графа, порожденного полной n-вершинной затравкой, и для канонического предфрактального графа, порожденного n-вершинной звездой.

В роботі досліджуються властивості неканонічних предфрактальних графів із заміщенням вершин за деяким принципом. Побудовані алгоритми розпізнавання предфрактальних графів з однією та k вершинами, що заміщуються. Розв’язана задача ГАМІЛЬТОНІВ ЦИКЛ для неканонічного предфрактального графа, породженого повною n-вершинною затравкою, та для канонічного предфрактального графа, породженого n-вершинною зіркою.

In the paper the properties of noncanonical prefractal graphs with substitution of the vertexes according to identified principle are discussed. The algorithm of recordinition of prefractal graphs with one and k substitutable vertexes. The problem HAMILTON CYCLE is solved for noncanonical prefractal graph, gene- rated by complete n- vertexes priming and for canonical prefractal graph, generated by n-vertex star.