Structure of local primitive digraphs.pdf Орграф Г называется i х j-примитивным (локально примитивным), если существует такое натуральное 7, что в Г имеются пути из i в j длины t при любом t ^ 7, наименьшее такое 7 называется ix j-экспонентом (локальным экспонентом) орграфа Г. Отсюда i х j-примитивность орграфа Г полностью определяется свойствами непустого множества путей из i в j. В [1] показано, что оценка локального экспонента сильно зависит от строения локально примитивного орграфа. С целью оптимизации существующих [1] и получения новых оценок локального экспонента для различных классов орграфов целесообразно описать строение локального примитивного орграфа в общем виде. Обозначим Г(^ j) компоненту сильной связности орграфа Г, содержащую множество всех путей из i в j. Для вершин i, j орграфа Г ксс U орграфа Г называется i, j-связывающей (кратко i, j-ксс), если в Г(^ j) есть путь, проходящий через некоторую вершину ксс U. Утверждение 1 [2]. Если орграф Г является i х j-примитивным, то Г содержит i, j-ксс. При описании i х j-примитивного орграфа различаются 2 случая. Случай 1: вершины i, j принадлежат общей ксс (в частности, i = j). Утверждение 2 [1]. Если вершины i,j принадлежат ксс U, то орграф Г является i х j-примитивным тогда и только тогда, когда ксс U примитивная. Случай 2: вершина i недостижима из вершины j. Без ущерба для общности положим, что обе вершины i, j не принадлежат i, j-ксс. Простой путь (i, i1, . . . , il, j) в орграфе Г назовём ациклическим, если вершины i1, . . . , il ациклические. В общем случае Г(^ j) состоит из всех i, j-ксс и ациклических простых путей, соединяющих i, j -ксс и вершины i, j. Разобьём множество вершин на k + 1 блоков (ярусов), k < n. К 0-му ярусу относится вершина i, к k-му ярусу - вершина j. К 1-му ярусу отнесём все i, j-ксс, достижимые из вершины i c помощью ациклического простого пути. Вершина 0-го яруса i соединяется с вершиной j с помощью простых ациклических путей, если таковые есть в Г. Каждая i, j-ксс U 1-го яруса имеет множество предшественников P (U), содержащее вершину i. Пусть описаны 1-й, ... , (t - 1)-й ярусы и множества предшественников для каждой i, j-ксс этих ярусов, t < k. К t-му ярусу отнесём все i, j-ксс, не входящие в 1-й, ... , (t - 1)-й ярусы и достижимые из i, j-ксс (t - 1)-го яруса c помощью ациклического простого пути. Множество предшественников P(U) для i, j-ксс U t-го яруса состоит из всех вершин, из которых достижима U. Ксс U t-го яруса соединена с вершиной j и с вершинами i, j-ксс 1-го, ..., t-го ярусов, не входящих в P(U), с помощью простых ациклических путей, если таковые есть в Г. Построение завершено после описания 1-го, ..., (k - 1)-го ярусов и множеств предшественников для каждой i,j-ксс этих ярусов. Пример. На рис. 1 изображён граф Г(1,14), содержащий четыре 1,14-ксс U1, U2, U3, U4 с множествами вершин {2, 3}, {4, 5,6}, {8, 9}, {12,13} соответственно. Рис. 1. Орграф Г(1,14) К 0-му ярусу относится вершина 1, к 1-му - ксс U1 и U2, ко 2-му - ксс U3 и U4, к 3-му - вершина 14. Множества предшественников: P(U1) = {1}, P(U2) = {1, 2, 3, 12,13}, P(Ua) = P(U2) U {4, 5,6, 7}, P(U4) = {1, 2, 3}. С помощью этой модели опишем перемешивающий орграф генератора с перемежающимся шагом [3, гл. 18], построенный на базе двоичных регистров правого сдвига: управляющего длины m и двух генерирующих длин п и r, m, п, r > 1. В зависимости от управляющего знака сдвигается либо первый, либо второй генерирующий регистр. Перемешивающий орграф r(h) преобразования h множества Vm+n+r состояний генератора является i х (m + п)- и i х (m + n + r)-примитивным [4] для любого i Е {1,..., m}; r(h) содержит i, (m + п)-ксс U1 и U2 (с множествами вершин {1,..., m} и {m + 1,... ,m + п} соответственно) и i, (m + п + г)-ксс U3 с множеством вершин {m + п + 1,..., m + п + r}. Для любого i Е {1,..., m} в орграфе r(i, m + п) имеется два яруса: к 0-му ярусу относится ксс U1, к 1-му - ксс U2; в орграфе T(i,m + п + r) также имеется два яруса: к 0-му ярусу относится ксс U1, к 1-му - ксс U3.

Скачать электронную версию публикации