Вивчено проблему Штейнера на площині, коли ваги ребер дерева Штейнера мають довільні значення. Доведено ряд тверджень про оптимальну побудову дерева для заданих трьох і чотирьох точок.

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

Описано достатні умови неповоротності для випадкових блукань з обмеженими стрибками у випадкових середовищах на дереві Келі.

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

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

Рубрики:

Дискретне програмування

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

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

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

Рубрики:

Майже періодичні функції

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

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

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

Рубрики:

Дискретне програмування

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

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

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

Рубрики:

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

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

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

Рубрики:

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

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

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

Рубрики:

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

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

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

Рубрики:

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

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

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

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

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

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

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

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

Наведено класифікацію зображень зорієнтованих графів (зі співвідношеннями) спеціального вигляду - гельфандових графів, які узагальнюють графи, що виникають під час вивчення модулів Харіш - Чандри над дійсними напівпростими алгебрами Лі. Викладено повний та інваріантний розв'язок задачі, поставленої І.М.Гельфандом на Міжнародному математичному конгресі в Ніцці.

Приведена классификация изображений сориентированных графов (с соотношениями) специального вида - гельфандовых графов, обобщающих графы, которые возникают при изучении модулей Хариш - Чандры над действительными полупростыми алгебрами Ли. Представлено полное и инвариантное решение задачи, поставленной И.М.Гельфандом на международном математическом конгрессе в Ницце.

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

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

Рубрики:

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

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

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

Запропоновано модель на графах процесів багатокритеріальної оптимізації в задачах дрібно-лінійного програмування великої розмірності.