Гиперсеть
Cтраница 4
Можно предположить, что для ( Д X) - гиперсетей задачи поиска / с-соединимости и Л - квазисоединимости также полиномиально вычислимы. S решаются за полиномиальное время. [46]
ИГ) - гиперсеть простая, a ( R V) - гиперсеть обыкновенная; обратное неверно) или абстрактная гиперсеть может принадлежать различным классам. Некоторые классы могут иметь пустое пересечение. Из сказанного следует, что система классов абстрактных гиперсетей имеет нетривиальную структуру, установить зависимость между классами в некоторых случаях сложно. [47]
Рассматриваются задачи синтеза в классе ( X - - R) - гиперсетей с заданной частичной квазисвязностью и ограничением па ранг связывающих квазимаршрутов. Во всех этих задачах считается заданной первичная сеть PS ( X, V) синтезируемой гиперсети. [48]
 |
Преобразование вершин гиперсети в клики инциденции. [49] |
Гиперсеть называется связной, если и только если между любой парой вершин гиперсети S существует соединяющий их маршрут. Отсюда следует, что графы PS и WS связны. Гиперсеть называется односторонне квазисвязной, если и только если любая пара вершин из S соединима хотя бы одним квазимаршрутом. Гиперсеть называется слабо связной, если и только если любая пара вершин S соединима слабым маршрутом. [50]
В этом разделе решены некоторые задачи, связанные с поиском маршрутов в гиперсетях. [51]
Вработе рассматривается классификация гиперсетей, приведены определения маршрутов, отделимости и соединимости вершин в гиперсетях и алгоритмы их вычисления в том случае, когда указанные задачи не ЖР-полные. Исследуются методы синтеза некоторых классов гиперсетей с заданной связностью. В процессе синтеза их структур важно учитывать не только оптимизацию, но и структурную надежность систем. Этим объясняется актуальность исследования характеристик связности гиперсетей. [52]
Отношения слабой отдаленности и слабого расстояния играют большую роль при решении прикладных задач на гиперсетях. Так же как и в предыдущих случаях, справедлива следующая теорема. [53]
 |
Классификация задач вычисления k - соединимости в гиперсетях. [54] |
В работе [9] показано, что задачи вычисления А-соедини-мости и А; - F-соединимости пары вершин в произвольной гиперсети S ( X, V, R) являются ТУР-полными. [55]
Когда маршрут есть цепь в PS, то гиперсеть называется обыкновенной, в случае простой цепи имеем простую гиперсеть. Основное внимание в данной работе уделено простым гиперсетям. [56]
Заметим, что вычисление кратчайших квазимаршрутов с помощью специально построенных графов и ультраграфов не накладывает ограничений на класс гиперсетей. [57]
ИГ) - гиперсеть простая, a ( R V) - гиперсеть обыкновенная; обратное неверно) или абстрактная гиперсеть может принадлежать различным классам. Некоторые классы могут иметь пустое пересечение. Из сказанного следует, что система классов абстрактных гиперсетей имеет нетривиальную структуру, установить зависимость между классами в некоторых случаях сложно. [58]
Легко показать, что для некоторых тривиальных классов гиперсетей ( например, для ( F - R) - гиперсетей) все задачи вычисления А-отделимости решаются за полиномиальное время. [59]
Страницы: 1 2 3 4