Досліджено властивості канонічних передфрактальних графів, породжених повною n-вершинною затравкою, колесом, зіркою, старі ребра яких не перетинаються, і у повних канонічних передфрактальних графів, старі ребра яких перетинаються. Уперше встановлено властивості повних неканонічних передфрактальних графів, старі ребра яких не перетинаються, у випадках, коли заміщення вершин відбувається довільним чином, або за певним правилом, а також властивості повних неканонічних передфрактальних графів з довільною кількістю вершин, що заміщуються, старі ребра яких перетинаються. Запропоновано поліноміальні алгоритми розпізнавання таких графів на передфрактальність. Досліджено складність розв'язання деяких NP-повних задач розпізнавання (провершинне покриття, домінуючу множину, гамільтонів цикл, розбиття на гамільтонові підграфи, розбиття на ліси) на передфрактальних графах. Розглянуто NP-складну задачу про остові дерева заданої конфігурації на довільних графах. Для цієї задачі побудовано поліноміальний алгоритм, що виділяє оптимальне діадичне дерево у заданому графі, розроблено асимптотично точний алгоритм виділення діадичного дерева у повному графі.

  Завантажити