RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Модел. и анализ информ. систем:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Модел. и анализ информ. систем, 2018, том 25, номер 4, страницы 388–401 (Mi mais636)  

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

Остовное дерево в делимом кратном графе

А. В. Смирнов

Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, г. Ярославль, 150003 Россия

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

Ключевые слова: кратный граф, кратное дерево, делимый граф, остовное дерево, полное остовное дерево, минимальное остовное дерево.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 17-07-00823_а
Работа выполнена при поддержке Российского фонда фундаментальных исследований (проект № 17-07-00823 А).


DOI: https://doi.org/10.18255/1818-1015-2018-4-388-401

Полный текст: PDF файл (765 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.17
Поступила в редакцию: 29.07.2018

Образец цитирования: А. В. Смирнов, “Остовное дерево в делимом кратном графе”, Модел. и анализ информ. систем, 25:4 (2018), 388–401

Цитирование в формате AMSBIB
\RBibitem{Smi18}
\by А.~В.~Смирнов
\paper Остовное дерево в делимом кратном графе
\jour Модел. и анализ информ. систем
\yr 2018
\vol 25
\issue 4
\pages 388--401
\mathnet{http://mi.mathnet.ru/mais636}
\crossref{https://doi.org/10.18255/1818-1015-2018-4-388-401}
\elib{http://elibrary.ru/item.asp?id=35452926}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/mais636
  • http://mi.mathnet.ru/rus/mais/v25/i4/p388

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:12
    Полный текст:3
    Литература:2

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019