EISSN 2500-1779
Языки: ru · en

Статья: Анализ оценок максимально внутренне устойчивых множеств при работе с обыкновенным взвешенным графом (2024)

Читать онлайн

Исследованы методы эффективного поиска максимально внутренне устойчивых множеств в обычных графах. Рассмотрены точные методы поиска максимально внутренне устойчивого множества: метод Магу, различные методы поиска нижних оценок. Данные алгоритмы направлены либо на анализ структуры графов и выявление в них особых подструктур, обладающих свойством внутренней устойчивости, либо на прогнозирование чисел
внутренней устойчивости и результатов, связанных с ними. Проведён вычислительный эксперимент с использованием программного средства на языке программирования C# на различных объёмах исходных данных. Результаты эксперимента демонстрируют эффективность и сравнимость оценок при различных условиях, сделаны выводы об их эффективности.

Ключевые фразы: метод Магу, нижняя оценка, верхняя оценка, максимально внутренне устойчивое множество, хроматическое число, обыкновенный граф, обратный граф, вершина (узел), ребро (связь)
Автор (ы): Кобак Валерий Григорьевич, Глазков Дмитрий Владимирович
Журнал: МОЛОДОЙ ИССЛЕДОВАТЕЛЬ ДОНА

Идентификаторы и классификаторы

УДК
519.87. Математические модели исследования операций
Для цитирования:
КОБАК В. Г., ГЛАЗКОВ Д. В. АНАЛИЗ ОЦЕНОК МАКСИМАЛЬНО ВНУТРЕННЕ УСТОЙЧИВЫХ МНОЖЕСТВ ПРИ РАБОТЕ С ОБЫКНОВЕННЫМ ВЗВЕШЕННЫМ ГРАФОМ // МОЛОДОЙ ИССЛЕДОВАТЕЛЬ ДОНА. 2024. Т. 9. № 3 (48)
Текстовый фрагмент статьи