Фібоначчі- та супер-Фібоначчі-граціозні розмітки деяких видів графів

• Дата: 2020
• Автор: Semeniuta, Marina
• Формат: Стаття
• Мова: Russian
• Опубліковано: V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2020
• Теми: Фібоначчі-граціозна розмітка; супер-Фібоначчі-граціозна розмітка; цикл; ейлерів граф; одноточкове з’єднання графів
• Онлайн доступ: https://jais.net.ua/index.php/files/article/view/51
• Назва журналу: Problems of Control and Informatics

Рассмотрены базовые теоретические сведения по Фибоначчи-грациозным графам. Под Фибоначчи-грациозной разметкой графа G=(V,E) размера q понимают инъективную функцию f:V→{0,1,2,3,4,…,Fq} которая индуцирует биктивную функцию f*:E→{F1 ,F2,F3,…,Fq}, где F1=1, F2=1, F3=2, Fq= Fq-2+Fq-1 по правилу f*(uv)=|f(u)-f(v)| для любых смежных вершин u,v ϵ V. Граф, допускающий такую разметку, называется Фибоначчи-грациозным. В данной работе введено понятие супер-фибонач-грациозной разметки сужением множества вершинных меток, т.е. f:V→{F0,F1,F2,…,Fq}. Выделены четыре типа задач, подлежащих исследованию. В задаче первого типа поднимается следующий вопрос: существует ли граф, допускающий определенный вид разметки, и при каких условиях это имеет место? Задача второго типа — это задача построения: при заданной системе требований для графа необходимо построить (хотя бы одну) его разметку, удовлетворяющую этой системе. Следующие два типа задач относятся к задачам перечня: для заданного графа определить число разных Фибоначчи- и/или супер- Фибоначчи-грациозных разметок; построить все разные разметки заданного вида. В результате решения этих задач найдены функции, порождающие Фибоначчи- и супер-Фибоначчи-грациозные разметки для графов циклической структуры; получены необходимые и достаточные условия существования Фибоначчи-грациозной разметки дизъюнктивного объединения циклов, супер-Фибоначчи-грациозной разметки циклов, эйлеровых графов; определено число неэквивалентных разметок цикла; представлены условия существования супер-Фибоначчи-грациозной разметки одноточечного соединения произвольных связных супер-Фибоначчи-грациозных графов G1,G2,…,Gk.