Семенюта М. Ф. Фибоначчи- и супер-Фибоначчи-грациозные разметки некоторых видов графов / М. Ф. Семенюта // Проблемы упр. и информатики. - 2021. - № 1. - С. 105-121. - Библиогр.: 15 назв. - рус.Рассмотрены базовые теоретические сведения относительно Фибоначчи-грациозных графов. Под Фибоначчи-грациозной разметкой графа G = (V, E) размера q понимают инъективную функцию f:V <$E symbol О> {0, 1, 2, 3, 4, ..., Fq}, индуцирующую биективную функцию f<^>*: E <$E symbol О> {F1, F2, F3, ..., Fq}, где F1 = 1, F2 = 1, F3 = 2, ..., Fq = Fq-2 + Fq-1, по правилу <$E f sup * (u nu )~=~|f(u)~-~f( nu )|> для любых смежных вершин <$E u,~nu~symbol <174>~V>. Граф, допускающий такую разметку, называется Фибоначчи-грациозным. Введено понятие супер-Фибоначчи-грациозной разметки сужением множества вершинных меток, т.е. f:V <$E symbol О> { F0, F1, F2, F3, ..., Fq}. Выделено 4 типа задач, подлежащих исследованию. В задаче первого типа поднимается следующий вопрос: существует ли граф, допускающий определенный вид разметки, и при каких условиях это имеет место? Задача второго типа - это задача построения: необходимо, при заданной системе требований, для графа построить (хотя бы одну) его разметку, которая удовлетворяла бы этой системе. Следующие 2 типа задач относятся к задачам перечисления: для заданного графа определить число различных Фибоначчи- и/или супер-Фибоначчи-грациозных разметок; построить все различные разметки заданного вида. В результате решения этих задач найдены функции, порождающие Фибоначчи- и супер-Фибоначчи-грациозные разметки для графов циклической структуры; получены необходимые и достаточные условия существования Фибоначчи-грациозной разметки дизъюнктивного объединения циклов, супер-Фибоначчи-грациозной разметки циклов, эйлеровых графов; определено число неэквивалентных разметок цикла Cn; приведены условия существования супер-Фибоначчи-грациозной разметки одноточечного соединения k произвольных связных супер-Фибоначчи-грациозных графов G1, G2, ..., Gk. Індекс рубрикатора НБУВ: В126.3
Рубрики:
Шифр НБУВ: Ж26990 Пошук видання у каталогах НБУВ Додаткова інформація про автора(ів) публікації: (cписок формується автоматично, до списку можуть бути включені персоналії з подібними іменами або однофамільці) Якщо, ви не знайшли інформацію про автора(ів) публікації, маєте бажання виправити або відобразити більш докладну інформацію про науковців України запрошуємо заповнити "Анкету науковця"
|