Гиперсеть

Cтраница 2

Задачи синтеза гиперсетей имеют различную сложность решения. Покажем на примерах, как незначительное изменение в постановке задачи влияет на сложность ее решения. Пусть заданы первичная сеть PS ( X, V), для которой со ( PS) 2, и вторичная сеть WS ( F, R) - простой цикл, и пусть Х Y. [16]

В определении абстрактной гиперсети рассматриваются два понятия: слабая инцидентность и инцидентность. [17]

Подразбиение вершины на инцидентную и слабо инцидентную. [18]

Используя преобразование гиперсети S, изложенное в доказательстве теоремы 9, легко показать, что задача поиска внут - ренне А-везависимых ( s, t) - квазимаршрутов полиномиально вычислима. [19]

ИГ) - гиперсеть простая, a ( R V) - гиперсеть обыкновенная; обратное неверно) или абстрактная гиперсеть может принадлежать различным классам. Некоторые классы могут иметь пустое пересечение. Из сказанного следует, что система классов абстрактных гиперсетей имеет нетривиальную структуру, установить зависимость между классами в некоторых случаях сложно. [20]

Таким образом, синтезируемая гиперсеть должна обладать заданными значениями одной или нескольких характеристик связности. [21]

Вработе рассматривается классификация гиперсетей, приведены определения маршрутов, отделимости и соединимости вершин в гиперсетях и алгоритмы их вычисления в том случае, когда указанные задачи не ЖР-полные. Исследуются методы синтеза некоторых классов гиперсетей с заданной связностью. В процессе синтеза их структур важно учитывать не только оптимизацию, но и структурную надежность систем. Этим объясняется актуальность исследования характеристик связности гиперсетей. [22]

В процессе синтеза гиперсети с заданной связностью часто возникает необходимость в оптимизации значения некоторой целевой функции, в частности, она может отсутствовать. [23]

Следовательно, во вновь полученной гиперсети S вершины, не являются минимальным сечением - противоречие. Тем самым теорема доказана. [24]

Фундаментальным понятием в теории гиперсетей является отношение слабой инциденции. Два элемента из различных множеств слабо инцидентны, если найдется элемент из третьего множества, инцидентный им обоим. [25]

Перечислим некоторые важные направления гиперсетей. [26]

Удаляя различные элементы из гиперсетей, можно получать всевозможные частичные гиперсети с теми или иными свойствами. Например, возможны следующие задачи: найти минимальную ( по числу вершин, ветвей или ребер) частичную гиперсеть, связывающую заданное множество вершин или ветвей; найти компоненты связности, блоки и части гиперсетей с заданной связностью. [27]

Пример двухполюсной гиперсети. [28]

Однако для некоторых классов гиперсетей задачи вычисления - отделимости пары вершин решаются за полиномиальное время. [29]

Кроме того, в гиперсетях возможно определение этих понятий, когда одно множество сопоставляется двум другим. В этом направлении возникают принципиально новые задачи. [30]

Страницы: 1 2 3 4