Індекс рубрикатора НБУВ: В126.35

Рубрики:

Топологічні та метричні задачі теорії графів

Шифр НБУВ: РА348896 Пошук видання у каталогах НБУВ 

  Скачати повний текст

Рассмотрена отрасль теории графов, занимающаяся разложениями графов на подграфы заданного вида. Изучены экстремальные (имеющие наибольший и наименьший размер) разложения и покрытия.

Запропоновано метод незалежних підмножин, що дозволяє побудувати вершинні розбиття графів з контрольованими індексами підмножин розбиття.

Роботу присвячено вивченню метричних базисів і метричної розмірності уніциклічних графів та опису зв'язків між метричною розмірністю уніциклічних графів та відповідних їм дерев. Повністю охарактеризовано уніциклічні графи, що мають метричну розмірність 2 і описано їх структуру. Зокрема показано, що в довільного такого графа не існує поза циклом вершини ступеня більшого, ніж 3, а максимальний ступінь вершин в циклі не перевищує 4 і лише в непарному уніциклічному графі. Для повної характеризації уніциклічних графів, що мають метричну розмірність 2, введено поняття базисного та мінорного графів, графів типу "павучок'' та "напівпавучок", а також конструкції обплетення і повного обплетення зазначених графів. Описано зв'язок між метричними розмірностями дерева і побудованого з нього уніциклічного графа та знайдено метричну розмірність кістякових дерев уніциклічних графів, метричний базис яких містить два елементи.