română | русский | english

Автор: Nadejda Sur Степень: доктор физико-математических наук Специальность:  01.01.09 - Математическая кибернетика и операционные исследования Год: 2009 Научный руководитель: Sergiu Cataranciuc доктор хабилитат, профессор, Государственный Университет Молдовы Институт: Ученый совет:

Статус Диссертация была зашищена 23 декабря 2008 Утверждена Национальным Советом 26 февраля 2009 Автореферат – 0.26 Mb / на румынском Диссертация CZU 519.17 0.85 Mb / на румынском 111 страниц

Ключевые слова

Аннотация

Основной целью диссертации является изучение d-выпуклости на дискретных структу- рах и именно на графах, как на неориентированных графах, так и на ориентированных. Решается задача, появившаяся в 60-70 годы прошлого столетия, о характеризации множе- ства d-выпукло простых неориентированных графов. Эти графы описываются рекурсивным методом. Вводится алгебраические операции на множестве d-выпукло простых графов, кото- рые позволяют не только расширять некоторые известные классы этих графов, но и выявлять некоторых первоначальных графов, из которых с помощью вводимых операций, формируются новые классы d-выпукло простых графов. Таким образом, определяется структура d-выпукло простых неориентированных графов, которая немало важная с точки зрения обоснования тео- рии выпуклости на дискретных структурах и в приложениях. Показывается, что метрические задачи в d-выпукло простых графов вида L(G, G0), приводятся к тем же задачам в графе G. Устанавливается размерность вложения в Евклидовых пространствах d-выпукло простых планарных графов и описывается алгоритм вложения этих графов в пространстве.

Аналогично случая d-выпукло простых графов, d-выпукло квази-простые неориентирован- ные графы описываются рекурсивным методом. Определяются все операции, которые были введены для d-выпукло простых графов. С их помощью изучаются специальные классы, d- выпукло квази-простых графов и находится граф генератор для некоторых классов. Уста- навливается размерность вложения в Евклидовых пространствах d-выпукло квази-простых планарных графов и описывается алгоритм вложения этих графов в данном пространстве. Используя понятие расстояния, определенная обычным способом на ориентированных гра- фов, определяется понятия d-выпуклого множества в ориентированных графов. Определяются d-выпукло простые ориентированные графы, как графы с наименьшем количеством выпуклых множеств. d-Выпукло простые ориентированные графы описываются рекурсивным методом.

На множестве ориентированных d-выпукло простых графов определяются все операции, ран- нее определяемые на неориентированных d-выпукло простых графов, к которым добавились операция транспонирования и операция L. Доказывается, что эти операции являются алгебраи- ческими на множестве d-выпукло простых ориентированных графов. Это нужно не только для выявления структуры данных графов и описания способа их строения, но и для доказательства того, что для любого неориентированного d-выпукло простого графа существует ориентирован- ный d-выпукло простой граф, который является ориентации первого. Таким образом, можно утверждать что множество ориентированных d-выпукло простых графов содержит множество знакомых неориентированных d-выпукло простых графов. 1

Официальные оппоненты

• Dumitru Lozovanu
  доктор хабилитат, профессор, Государственный Университет Молдовы
• Dumitru Zambiţchi
  доктор, доцент

 Диссертации