|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Algorithms
Алгоритмы для задач об эйлеровом цикле и эйлеровой цепи в кратном графе
А. В. Смирнов Ярославский государственный университет им. П.Г. Демидова, ул. Советская, 14, Ярославль, 150003, Россия
Аннотация:
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют $2$ или $(k+1)$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер мультиребра.
Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Ставится задача об эйлеровом маршруте (цикле или цепи) в кратном графе, которая обобщает классическую задачу для обычного графа. Сформулированы необходимые условия существования эйлерова маршрута в кратном графе, показано, что эти условия не являются достаточными. Кроме того, показано, что для произвольного кратного графа необходимые условия существования эйлерова цикла и эйлеровой цепи не являются взаимоисключающими, поэтому можно построить кратный граф, в котором одновременно существуют два вида эйлеровых маршрутов. Кратному графу сопоставляется обычный граф с квазивершинами, в упрощенном виде представляющий структуру исходного графа. В частности, каждому эйлерову маршруту в кратном графе соответствует эйлеров маршрут в графе с квазивершинами. Формулируется алгоритм построения такого графа. Также рассмотрена вспомогательная задача о покрывающих цепях с заданными концами в обычном графе, получены два алгоритма ее решения. Разработан алгоритм поиска эйлерова маршрута в кратном графе экспоненциальной трудоемкости. Для частного случая кратного графа предложен полиномиальный алгоритм, показано, что в этом частном случае необходимые условия существования эйлерова маршрута являются достаточными.
Ключевые слова:
кратный граф, кратный путь, делимый граф, множество достижимости, покрывающие цепи, эйлерова цепь, эйлеров цикл, граф с квазивершинами.
Поступила в редакцию: 13.08.2023 Исправленный вариант: 26.08.2023 Принята в печать: 30.08.2023
Образец цитирования:
А. В. Смирнов, “Алгоритмы для задач об эйлеровом цикле и эйлеровой цепи в кратном графе”, Модел. и анализ информ. систем, 30:3 (2023), 264–282
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais804 https://www.mathnet.ru/rus/mais/v30/i3/p264
|
Статистика просмотров: |
Страница аннотации: | 33 | PDF полного текста: | 3 | Список литературы: | 8 |
|