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
    2265
    Prefix
    Отказоустойчивость  это свойство ВС адаптироваться к новой ситуации и противостоять потоку отказов, выполняя при этом свою целевую функцию за счет соответствующего изменения структуры и поведения сети, даже при отказавших ее частях. В последнее время интенсивно разрабатывались алгоритмы и модели отказоустойчивых ВС
    Exact
    [1-5]
    Suffix
    (в том числе на основе методов марковских и полумарковских случайных процессов, включая и циклические системы [4-6]). Однако использование этих алгоритмв Наука и образование. МГТУ им. Н.Э. Баумана 76 и моделей обычно приводит к «переупрочненным» и весьма дорогим вариантам [5-7] построения отказоустойчивых циклически ВС.
    (check this in PDF content)

  2. Start
    2379
    Prefix
    В последнее время интенсивно разрабатывались алгоритмы и модели отказоустойчивых ВС [1-5] (в том числе на основе методов марковских и полумарковских случайных процессов, включая и циклические системы
    Exact
    [4-6]
    Suffix
    ). Однако использование этих алгоритмв Наука и образование. МГТУ им. Н.Э. Баумана 76 и моделей обычно приводит к «переупрочненным» и весьма дорогим вариантам [5-7] построения отказоустойчивых циклически ВС.
    (check this in PDF content)

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

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

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

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

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

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

  9. Start
    8119
    Prefix
    Поэтому удаление одной из вершин u или v приводит к несвязНаука и образование. МГТУ им. Н.Э. Баумана 78 ному или одновершинному графу, а это означает, что . Для любого графа 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
    9957
    Prefix
    Например, на рис. 1 множества Q1253569610, , , , , , ,pppppppp и Q27, , , , , , ,p vx wy wz w являются 1 11pp-разделяющими, а множества P156,pp и 223910, , ,Ppppp являются 1 11pp-отделяющими
    Exact
    [10-12]
    Suffix
    . Наука и образование. МГТУ им. Н.Э. Баумана 79 p2 p7 p5 p8 p3 p1p11 p9 p6 p10 p4 Рис. 1. Сеть с множествами 1Q, 2Q 1 11pp-разделяющим множеством) и 1P, 2P 1 11pp-отделяющим множеством) Для того чтобы подсчитать число реберно непересекающихся простых цепей из v в w, заметим сначала, что если какое-нибудь 1 11pp-разделяющее множество Q содержит k ребер, то число реберно непересекающ
    (check this in PDF content)

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

  12. Start
    12651
    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
    12772
    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
    13958
    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
    15085
    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
    16330
    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
    17242
    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)