The 17 reference contexts in paper G. Mojarov P., Г. Можаров П. (2016) “Отказоустойчивые циклические сети с минимальной задержкой передачи информации // Fault Tolerant Cyclic Networks from the Minimum Information Transfer Delay” / spz:neicon:technomag:y:2016:i:4:p:76-91

  1. Start
    2311
    Prefix
    Отказоустойчивость  это свойство ВС адаптироваться к новой ситуации и противостоять потоку отказов, выполняя при этом свою целевую функцию за счет соответствующего изменения структуры и поведения сети, даже при отказавших ее частях. В последнее время интенсивно разрабатывались алгоритмы и модели отказоустойчивых ВС
    Exact
    [1-5]
    Suffix
    (в том числе на основе методов марковских и полумарковских случайных процессов, включая и циклические системы [4-6]). Однако использование этих алгоритмв и моделей обычно приводит к «переупрочненным» и весьма дорогим вариантам [5-7] построения отказоустойчивых циклически ВС.
    (check this in PDF content)

  2. Start
    2426
    Prefix
    В последнее время интенсивно разрабатывались алгоритмы и модели отказоустойчивых ВС [1-5] (в том числе на основе методов марковских и полумарковских случайных процессов, включая и циклические системы
    Exact
    [4-6]
    Suffix
    ). Однако использование этих алгоритмв и моделей обычно приводит к «переупрочненным» и весьма дорогим вариантам [5-7] построения отказоустойчивых циклически ВС. Важными практическими преимуществами циклических конфигураций ВС являются:  простота организации и управления, поскольку сообщения между процессорами сети передаются по связям в одном направлении, при этом отпадает необходимо
    (check this in PDF content)

  3. Start
    2585
    Prefix
    В последнее время интенсивно разрабатывались алгоритмы и модели отказоустойчивых ВС [1-5] (в том числе на основе методов марковских и полумарковских случайных процессов, включая и циклические системы [4-6]). Однако использование этих алгоритмв и моделей обычно приводит к «переупрочненным» и весьма дорогим вариантам
    Exact
    [5-7]
    Suffix
    построения отказоустойчивых циклически ВС. Важными практическими преимуществами циклических конфигураций ВС являются:  простота организации и управления, поскольку сообщения между процессорами сети передаются по связям в одном направлении, при этом отпадает необходимость в принятии решения о направлении пересылки сообщения;  относительная простота введения дополнительных связей м
    (check this in PDF content)

  4. Start
    3280
    Prefix
    пересылки сообщения;  относительная простота введения дополнительных связей между процессорами для повышения отказоустойчивости, причем эти связи уменьшают время передачи сообщений и разгружают каналы связи, повышая пропускную способность ВС. В течение последнего десятилетия интенсивно разрабатывались более тонкие методы расчёта отказоустойчивости ВС сетей с произвольной структурой
    Exact
    [8-10]
    Suffix
    . Большинство моделей [6, 10,11] неявно предполагали, что все компоненты ВС (в том числе циклических)  свободны от ошибок. Однако в реальной ситуации ошибки возникают и отказы (процессоров, модулей памяти и линий связи и т.д.) приводят к ухудшению рабочих характеристик ВС.
    (check this in PDF content)

  5. Start
    3307
    Prefix
    относительная простота введения дополнительных связей между процессорами для повышения отказоустойчивости, причем эти связи уменьшают время передачи сообщений и разгружают каналы связи, повышая пропускную способность ВС. В течение последнего десятилетия интенсивно разрабатывались более тонкие методы расчёта отказоустойчивости ВС сетей с произвольной структурой [8-10]. Большинство моделей
    Exact
    [6, 10,11]
    Suffix
    неявно предполагали, что все компоненты ВС (в том числе циклических)  свободны от ошибок. Однако в реальной ситуации ошибки возникают и отказы (процессоров, модулей памяти и линий связи и т.д.) приводят к ухудшению рабочих характеристик ВС.
    (check this in PDF content)

  6. Start
    4518
    Prefix
    Чтобы получить допустимую конфигурацию многопроцессорная ВС должна иметь не менее двух процессоров, двух блоков памяти (эти минимальные требования могут возрасти в зависимости от специфики решаемой задачи). Однако до настоящего времени не существует единой научной методологии по синтезу отказоустойчивых циклических ВС, структура которых может быть представлена циркулянтым графом
    Exact
    [6-9]
    Suffix
    . Ниже будут предложены и исследованы аналитические методы решения сложной научно-технической оптимизационной задачи по определению минимального количества линий связи среди всех циклических ВС и приведены примеры синтеза отказоустойчивой циркулянтной сети.
    (check this in PDF content)

  7. Start
    5950
    Prefix
    Ясно, что менее отказоустойчивой следует считать ту ВС, исправность которой нарушается при повреждении меньшего количества узлов и связей. Отказоустойчивость сети ВС можно измерять на основе вводимых ниже определений
    Exact
    [7-9]
    Suffix
    . Числом вершинной связности (или просто числом связности) Gграфа G называется наименьшее число вершин, удаление которых приводит к несвязному или одновершинному графу. Так, например, если через nK обозначить полный n-вершинный граф, а через nС обозначить n-вершинный цикл, то 10K, 1nKn , 2nC.
    (check this in PDF content)

  8. Start
    6791
    Prefix
    Вершина v графа G называется точкой сочленения (или разделяющей вершиной), если граф Gv имеет больше компонент, чем граф G. В частности, если граф G связен и v – точка сочленения, то Gv не связен
    Exact
    [7,8]
    Suffix
    . Аналогично ребро графа называется мостом, если его удаление увеличивает число компонент. Число вершинной связности и число реберной связности ее графа отражают чувствительность сети к разрушению узлов и каналов связи соответственно, а мостам и точкам сочленения отвечают наиболее уязвимые места сети.
    (check this in PDF content)

  9. Start
    8164
    Prefix
    Если же он связен, то ребро uv является мостом. Поэтому удаление одной из вершин u или v приводит к несвязному или одновершинному графу, а это означает, что . Для любого графа G верны неравенства
    Exact
    [7,10,11]
    Suffix
        GGG. Для любых натуральных чисел p, q, r, таких, что pqr, существует граф G, у которого Gp, Gq, Gr. Для графа G верно равенство   GG. Граф G называется k-связным, если Gk, и реберно-k-связным − если Gk.
    (check this in PDF content)

  10. Start
    10002
    Prefix
    Например, на рис. 1 множества Q1253569610, , , , , , ,pppppppp и Q27, , , , , , ,p vx wy wz w являются 1 11pp-разделяющими, а множества P156,pp и 223910, , ,Ppppp являются 1 11pp-отделяющими
    Exact
    [10-12]
    Suffix
    . p1p11 p2 p4 p3 p5 p6 p10 p9 p8 p7 Рис. 1. Сеть с множествами 1Q, 2Q 1 11pp-разделяющим множеством) и 1P, 2P 1 11pp-отделяющим множеством) Для того чтобы подсчитать число реберно непересекающихся простых цепей из v в w, заметим сначала, что если какое-нибудь 1 11pp-разделяющее множество Q содержит k ребер, то число реберно непересекающихся простых цепей не превосходит k, поскольку
    (check this in PDF content)

  11. Start
    11371
    Prefix
    Соединимость по ребрам  определяется наименьшим количеством ребер, удаление которых ведет к утрате связности графа. Можно показать, что 2qp     , где   минимальная степень вершины (число исходящих из нее ребер)
    Exact
    [9-11]
    Suffix
    . Исследуются некоторые свойства неориентированных симметричных графов специального вида так называемых циркулянтов. Пусть G  граф с матрицей смежности А и Px  многочлен от х такой, что все элементы матрицы Р(А)  неотрицательные целые числа.
    (check this in PDF content)

  12. Start
    12696
    Prefix
    n P xnaa xa x      является циркулянтом (циркулянтом называется матрица, у которой каждая строка получается из строки, стоящей над ней, в результате циклического сдвига на одну позицию вправо) с первой строкой 011, , ...,na aa. 3 2 1 n n -1 Cn Рис. 2. Контур nC В частности, n1 CnnnCC   где nC  простой цикл и nC  контур на n вершинах. Из теории матриц известно
    Exact
    [12]
    Suffix
    , что собственными значениями матрицы A являются 2ji n jje      1, 2, ..., ;1jn i . Используя теорему Захса [11], получаем     n1IA. Следовательно, собственными значениями простого цикла nC являются n122cos jjjj n       1, 2, ...,jn.
    (check this in PDF content)

  13. Start
    12819
    Prefix
    Контур nC В частности, n1 CnnnCC   где nC  простой цикл и nC  контур на n вершинах. Из теории матриц известно [12], что собственными значениями матрицы A являются 2ji n jje      1, 2, ..., ;1jn i . Используя теорему Захса
    Exact
    [11]
    Suffix
    , получаем     n1IA. Следовательно, собственными значениями простого цикла nC являются n122cos jjjj n       1, 2, ...,jn. У графа nPC собственными значениями будут величины jjP  , 1, ...,jn (известный результат в теории циркулянтов).
    (check this in PDF content)

  14. Start
    13994
    Prefix
    A имеет собственные векторы 1, ...,nvv, которые принадлежат соответственно характеристическим числам , ...,  n . Всякий полином от матрицы P, 1 0 n i i i cP   A называется циркулянтом
    Exact
    [8,11]
    Suffix
    . Матрица nAM, имеющая вид 12 121 112 231 n nn nnn n aaa aaaa aaaa aaaa           A, называется циркулянтной матрицей или циркулянтом. Любая ее строка получается из предыдущей путем циклического сдвига на одну позицию вправо, так что элементы любой строки представляют циклическую перестановку элементов первой строки.
    (check this in PDF content)

  15. Start
    15128
    Prefix
    Кроме того, циркулянты коммутируют относительно умножения. Можно рассматривать также и обобщения циркулянтных матриц, например такие матрицы, где строки циклически сдвигаются не на одну, а на несколько позиций (влево или вправо)
    Exact
    [11,13]
    Suffix
    . Некоторые основные неравенства циркулянтых графов Исследуем некоторые неравенства циркулянтных графов. Пусть граф ,C n r на n вершинах 1, 2, ...,n, ребрами которого являются пары ,1ii, ,i i r для 1,in, где индексы взяты по модулю n, является циркулянтом.
    (check this in PDF content)

  16. Start
    16371
    Prefix
    Тогда неравенство 1 IO ijij ij Eij E xsxsn sk r      определяет фасету многогранника двудольного подграфа. Пусть 1n kr, где ,2kr − четные числа. Тогда , ij2 ij C n r xn k r    
    Exact
    [9,14,15]
    Suffix
    . Заметим, что в случае 2r циркулянт ,2Cn задача: «содержит ли граф G циркулянт ,2Cn для некоторого n?» является NP-полной. Следовательно, задача отделения для класса неравенств:   ,2 3 1 2 ij ij C n xn  , n нечетное является NP-трудной.
    (check this in PDF content)

  17. Start
    17288
    Prefix
    Если p либо n четное, то для того, чтобы граф был решением поставленной задачи, необходимо и достаточно, чтобы он был регулярным и имел степень n   . Вообще говоря, для любого регулярного графа G . Если выполняется равенство, то граф G называется -оптимальным. Пусть вершины графа занумерованы 0, 1, ...,, 1p
    Exact
    [9,11,15]
    Suffix
    . Структура циркулянтного графа, или циркулянта, 12, , ...,pkG C n nn или, короче, piCn, такова, что при 10...1 2knnp     каждая вершина i соединена с вершинами 1in, 2in, ..., modki np.
    (check this in PDF content)