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