Статья: НЕКОТОРЫЕ ПОЛИНОМИАЛЬНЫЕ ПОДКЛАССЫ ЗАДАЧИ ОБ ЭЙЛЕРОВОМ МАРШРУТЕ В КРАТНОМ ГРАФЕ

Скачать

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k>1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или (k+1) вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Рассматривается задача об эйлеровом маршруте (цикле или цепи) в кратном графе, которая обобщает классическую задачу для обычного графа. Задача о кратном эйлеровом маршруте является NP-трудной. Обоснована полиномиальность двух подклассов задачи о кратном эйлеровом маршруте, разработаны полиномиальные алгоритмы. В первом подклассе задано ограничение на множества достижимости по обычным ребрам, которые представляют собой подмножества вершин, соединенных только обычными ребрами. Во втором подклассе задано ограничение на степень квазивершин в графе с квазивершинами. Структура этого обычного графа отражает структуру кратного графа, а каждая квазивершина определяется k индексами множеств достижимости по обычным ребрам, которые инцидентны какому-то мультиребру.

Информация о документе

Формат документа: PDF
Кол-во страниц: 1 страница
Загрузил(а): Смирнов Александр
Лицензия: —
Доступ: Всем

Информация о статье

ISSN: 1818-1015
EISSN: 2313-5417
Журнал: МОДЕЛИРОВАНИЕ И АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ
Год публикации: 2024
Автор(ы): Смирнов А. В.
Ключевые фразы: КРАТНЫЙ ГРАФ, ДЕЛИМЫЙ ГРАФ, ПОКРЫВАЮЩИЕ ЦЕПИ, ПУТИ, НЕ ПЕРЕСЕКАЮЩИЕСЯ ПО РЕБРАМ, ЭЙЛЕРОВА ЦЕПЬ, ЭЙЛЕРОВ ЦИКЛ, ГРАФ С КВАЗИВЕРШИНАМИ, МНОЖЕСТВО ДОСТИЖИМОСТИ ПО ОБЫЧНЫМ РЕБРАМ, ПОЛИНОМИАЛЬНЫЙ ПОДКЛАСС
УДК: 519.161. Общие вопросы о комбинаторных алгоритмах. Полиномиальные и NP- полные проблемы
519.17. Теория графов

Статистика просмотров

Статистика просмотров статьи за 2025 год.

Ранее вы смотрели (10)

01. Статья: Развитие инструментария стратегирования для целей устойчивого развития компании

02. Статья: НАПРАВЛЕНИЯ И ЭФФЕКТИВНОСТЬ ИННОВАЦИОННОЙ ДЕЯТЕЛЬНОСТИ РИТЕЙЛЕРОВ

03. Статья: ПРАЗДНИК «ЗАЕМ СВОБОДЫ» НА ЮГЕ РОССИИ В 1917 г.

04. Статья: Становление и перспективы развития методов портретной экспертизы по трехмерным изображениям

05. Статья: Исковая давность по трудовым спорам во взглядах ученых: дискуссионные предложения по совершенствованию законодательства о труде

06. Статья: ФОРМИРОВАНИЕ ПОЛИЦЕЙСКО-ПРАВОВОЙ ТЕОРИИ: АНАЛИЗ И ОЦЕНКА ПОЛИЦЕИСТА В. В. ИВАНОВСКОГО

07. Статья: Анализ трендов развития цифровой валюты и рекомендации по минимизации рисков

08. Статья: РОЛЬ ЖЕНЩИНЫ В КУЛЬТУРНОЙ И ОБРАЗОВАТЕЛЬНОЙ ПОЛИТИКЕ СОВЕТСКОГО ГОСУДАРСТВА

09. Статья: Подходы к оценке результативности территориального девелопмента с позиции ESG-принципов

10. Статья: ИЗ БЕЗЖАЛОСТНЫХ ВОИНОВ В БЕСПЕЧНЫЕ ЛЕНИВЦЫ: ЭВОЛЮЦИЯ ОБРАЗА КРЫМСКИХ ТАТАР ВО ФРАНЦУЗСКИХ ТРАВЕЛОГАХ XVII-XIX ВВ.

Все права на тексты и товарные знаки принадлежат их законным владельцам. Подробнее...

Сайт https://scinetwork.ru (далее – Сайт) представляет собой платформу, на которой пользователи самостоятельно добавляют и публикуют метаинформацию о материалах разных видов (названия, обложки, аннотации, данные об авторах и т.п.). Администрация Сайта не занимается самостоятельным сбором или первоначальной публикацией этих сведений.

Модерация контента

На Сайте действует постмодерация. Это означает, что материалы, добавляемые пользователями, становятся общедоступными сразу после публикации и проверяются Администрацией Сайта постфактум в разумные сроки.

Использование информации

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

Отказ от гарантий

Администрация Сайта не гарантирует точность, полноту и достоверность метаинформации, размещенной пользователями, поскольку не осуществляет ее предварительную проверку.

Ответственность

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