Исследуются структурные свойства одного подкласса числовых графов, который называется арифметическим. Конкретно изучаются однородные арифметические графы, которые играют важную роль для улучшения алгоритмов на графах. Доказано, что их структура зависит от четности числа вершин и количества образующих. Путем введения специального графа разложений все разнообразные случаи сводятся к базовым, из которых можно получить остальные однородные арифметические графы с помощью обратного радиального гомоморфизма. Описана также и структура графов разложений с цикломатическим числом 1 и 2.

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

Рубрики:

Лінійне програмування

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

Уперше у загальному вигляді сформульовано задачу про математичний сейф. Розглянуто випадок, коли множина однотипових замків сейфа розташована у вигляді прямокутної матриці. Під однотиповістю замків розуміється те, що їх стани задаються числами з класу лишків за визначеним модулем. Наведено повний розв'язок для простого модуля. Всі результати проілюстровано прикладами.

Наведено постановку двох задач про математичний сейф на графах: із множиною замків з однаковою та різною кількістю станів. Доведено низку тверджень про існування розв'язків таких задач. Одержано розв'язки задач для сейфів, заданих на таких елементарних орієнтованих та неорієнтованих графах як шлях, ланцюг, контур, цикл та зірка.

Впервые поставлена задача определения хроматического числа для одного подкласса числовых графов - натуральных модульных графов. Доказано несколько утверждений, позволяющих находить хроматическое число указанных графов с числом образующих не больше трех. Для решения общей задачи предложен метод разностей, описаны его возможности и пример реализации.

Продовжено дослідження задачі пошуку ізоморфізму натуральних модульних графів. Одержано нові результати для регулярних графів степеня 4. Розроблено загальну методику для вивчення довільних регулярних NM-графів, що дає можливість впритул підійти до розв'язання проблеми ізоморфізму для даного класу числових графів.

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

Охарактеризовано новий метод, який дозволяє знайти розв'язок комбінаторної задачі, враховуючи властивості і структуру множини перестановок, на якій розглянуто задачу. Описано побудову послідовності значень лінійної цільової функції, розклад точок множини перестановок по гіперплощинах та їх залежність. Це дозволяє побудувати алгоритм знаходження точки - елемента множини перестановок, в якій досягається задане значення цільової функції.

Розглянуто натуральні арифметичні графи з трьома твірними. Доведено, що хроматичне число таких графів дорівнює трьом.

Рассмотрены задачи комбинаторной оптимизации на множестве перестановок с повторениями. На основании специфических свойств и структуры множества перестановок, а также теории графов описано построение последовательности значений линейной целевой функции, разложение точек множества перестановок по гиперплоскостям и их зависимость с учетом повторения элементов.

Рассмотрена задача о рюкзаке с исходными данными в виде нечетких множеств. Построена ее математическая модель. Предложен эвристический метод решения задачи. Найдена оценка метода. Числовыми экспериментами подтверждена его эффективность.

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

Исследуется задача о специальной нумерации вершин деревьев, которая носит название проблемы Роса. Приводится ее решение для простейших типов деревьев: цепи, звезды и гусеницы. Предлагаются подходы для решения проблемы на более сложных деревьях.

Исследована задача нахождения экстремума функции на множестве перестановок. Целевая функция представляет собой отношение двух линейных форм, каждая из которых является прямой в многомерном пространстве. Предложен метод решения задачи, основанный на частичной упорядоченности значений функции.

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

Рубрики:

Теорія графів

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

Рассмотрена одна из задач теории графов - разложение полного графа на изоморфные деревья. Доказано, что если дерево состоит из двух симметричных частей, то задача сводится к известной проблеме Роса о нумерации вершин деревьев. Приведено решение этой проблемы для деревьев порядка девять.

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

Рассмотрена классическая задача Штейнера на плоскости. Для определения оптимальной точки, минимизирующей сумму расстояний к заданным точкам многоугольника, необходимо решить специальную систему тригонометрических уравнений. Приведены решения системы для треугольника и четырехугольника.

Рассмотрено решение классической задачи Штейнера для четырех точек, произвольно расположенных на плоскости. Для невырожденного случая найдены две оси Симпсона и сравниваются их длины. Для вырожденного случая рассмотрено произвольное положение четвертой точки внутри треугольника.

Рассмотрены алгоритмы поиска значений линейкой функции на лексикографически упорядоченных перестановках, изложен вопрос применения теории графов для построения алгоритмов нахождения перестановки по определенному номеру и наоборот.