оки2 (С.А. Ложкин - Лекции по основам кибернетики (2014)), страница 2

Цикл, в котором все вершины, кроме начальной и конечной, различны,называется простым циклом.Будем говорить, что вершина u достижима из вершины v в графе G, где u, v ∈ V (G), если u = v или в G существует (v − u)-цепь. Заметим, что отношение достижимостивершин графа G является рефлексивным и транзитивным,а если G — неориентированный граф, то и симметричным.Следовательно, множество вершин графа G распадается наклассы эквивалентности по отношению их достижимости вb который получается из графа G заменой каждойграфе G,bдуги на соответствующее неориентированное ребро (G = G,§1. Основные понятия из теории графов, сетей, схем.9если G — неориентированный граф).

При этом подграф графа G, натянутый на каждый такой класс вершин, называется связной компонентой графа G, а множество всех егосвязных компонент обозначается через c (G). Граф G называется связным, если |c (G)| = 1.Напомним, что|E (G)| − |V (G)| + |c (G)| > 0(1.2)и что левая часть (1.2) называется цикломатическим числом графа G. Напомним также, что это число равно максимальному числу линейно независимых относительно операции симметрической разности1 остовных подграфов графаG, состоящих из одного простого цикла и изолированныхвершин.Множество S, которое состоит из ребер графа G = (V, E)и обладает тем свойством, что вершина u, u ∈ V , достижима из вершины v, v ∈ V , в графе G, но не достижима изнее в графе (V, E \ S), называется (u|v)-сечением графа G.Легко видеть, что любая (u − v)-цепь графа G имеет хотябы одно общее ребро с любым (u|v)-сечением этого графа.Сечение, которое не имеет собственных подмножеств, являющихся сечением, называется тупиковым.Неориентированный (ориентированный) граф, не имеющий циклов (соответственно ориентированных циклов), называется ациклическим.

Заметим, что в ориентированномациклическом графе G всегда есть как стоки, так и истоки. При этом для каждой его вершины v можно определить1Под симметрической разностью графов G1 и G2 понимается графG, для которогоV (G) = V (G1 ) ∪ V (G2 ) ,E (G) = (E (G1 ) ∪ E (G2 )) \ (E (G1 ) ∩ E (G2 )) .10Глава 2.

Основные классы управляющих системее глубину (соответственно исходящую глубину), как максимальную длину (u − v)- (соответственно (v − u)-) путей графа G, где u — один из истоков (соответственно стоков) G.Легко видеть, что отношение достижимости является отношением частичного порядка на множестве вершин ориентированного ациклического графа и обратно.Неориентированный связный ациклический граф называется деревом. Для дерева G, как известно, имеет месторавенство|E (G)| = |V (G)| − 1.(1.3)Дерево с выделенной вершиной (корнем) называется корневым деревом, а все отличные от корня вершины степени 1 этого дерева считаются его листьями.

Ориентированный граф, который получается из корневого дерева заменой каждого его неориентированного ребра на соответствующую дугу, «направленную» к корню, называется ориентированным деревом.Дерево (ориентированное дерево) D, являющееся остовным подграфом графа G, называется его остовным поддеревом, а дерево D0 , получающееся из D в результате присоединения «конечной» вершины любого не вошедшего в Dребра графа G к той же вершине D, которая была его конечной вершиной в G, и объявления начальной вершины этогоребра листом — остовным наддеревом графа G. Очевидно,что при этом граф G может быть получен из дерева D0 врезультате присоединения некоторых вершин степени 1 (листьев) к другим его вершинам.

Заметим, что любой неориентированный связный граф, а также любой ориентированный ациклический граф с 1 стоком всегда имеют остовныеподдеревья и наддеревья соответствующего типа.Граф, вершинам и (или) ребрам которого сопоставлены определенные символы (пометки), считается помеченным графом. Примером такого графа является, в частно-§1.

Основные понятия из теории графов, сетей, схем.11сти, корневое дерево. Другим примером помеченного графа является ациклический граф с монотонной нумерациейвершин, когда для любой дуги номер вершины, из которойона исходит, больше номера вершины, в которую эта дугавходит. Ориентированный граф G называется упорядоченным, если для любой его вершины v, v ∈ V (G), все ребра, входящие в v, упорядочены и пронумерованы числами1, 2, .

. . , d+G (v).Будем считать, что ребра и вершины остовного поддерева, а также ребра связанного с ним остовного наддеревапомеченного графа имеют те же самые пометки, которыеони имели в исходном графе. Это означает, в частности, чтоостовное наддерево ориентированного ациклического упорядоченного графа является упорядоченным.Графы G0 = (V 0 , E 0 ) и G00 = (V 00 , E 00 ) называются изоморфными, если существуют такие взаимнооднозначные отображения ϕ : V 0 → V 00 и ψ : E 0 → E 00 , при которых вершиныи неориентированные ребра (дуги) G0 переходят в вершины и неориентированные ребра (соответственно дуги) G00 ссохранением отношения инцидентности (соответственно исхода, захода) вершин и ребер, а также всех пометок. Для(конечного) множества графов G через |G| будем обозначатьчисло попарно неизоморфных графов в G.

Известно, что|D (q)| 6 4q ,(1.4)где D (q) — множество упорядоченных ориентированных корневых деревьев с не более, чем q ребрами.Введем теперь общие определения и обозначения, связанные с сетями и «абстрактными» схемами, с реализациейими функций, а также с некоторыми структурными представлениями схем.Набор вида G = (G; V 0 ; V 00 ), где G — граф, а V 0 и V 00 —выборки из множества V (G) длины p и q соответственно,12Глава 2. Основные классы управляющих системпричем выборка V 0 является выборкой без повторений, называется (p, q)-сетью. При этом выборка V 0 (выборка V 00 )считается входной (соответственно выходной) выборкой, а ееi-я вершина называется i-м входным (соответственно выходным) полюсом или, иначе, i-м входом (соответственно выходом) сети G. Вершины, не участвующие во входной и выходной выборках сети, считаются ее внутренними вершинами.Для того чтобы выделить входную и выходную выборки сети G = (G; V 0 , V 00 ), будем записывать ее в виде G =G(V 0 ; V 00 ) или G = G(V 0 ; V 00 ).

Сеть, в которой входная ивыходная выборки совпадают (не совпадают), называетсясетью с неразделенными (соответственно с разделенными)полюсами. При этом в случае неразделенных полюсов сетьG = (G; V ; V ) = G(V ; V ) будем записывать в виде G =(G; V ) = G(V ). Как правило, входы и выходы (полюса) сетиимеют специальные пометки, которые отличают эти вершины от других вершин сети и указываются вместо них в соответствующих выборках. Таким образом, сети можно считатьспециальным частным случаем помеченных графов.Примером сети является корневое дерево, входами которого считаются его листья, а выходом — корень. При этомпорядок листьев во входной выборке ориентированного упорядоченного корневого дерева D задается «естественной»нумерацией τ , отображающей множество вершин дерева Dв N так, что τ (v 0 ) < τ (v 00 ) тогда и только тогда, когда либоv 00 достижима из v 0 , либо k 0 < k 00 , где k 0 и k 00 — номера дуг,по которым цепи, соединяющие вершины v 0 и v 00 соответственно с корнем D, входят в свою первую общую вершину.0 = v0 , .

. . , v0Для произвольныхвыборокVи V 00 =p10000= v1 , . . . , vq из множества V (G) графа G определим матрицу достижимости выборки V 0 из выборки V 00 как матри-§1. Основные понятия из теории графов, сетей, схем.13цу M, M ∈ B p,q , для которой(1, если vj00 достижима из vi0 ,M hi, ji =0, в остальных случаях.Заметим, что в случае V 0 = V 00 матрица M является рефлексивной и транзитивной1 , а если, кроме того, G — неориентированный граф, то и симметричной матрицей. Заметим также, что транзитивность рефлексивной матрицы M ,M ∈ B m,m , имеет место тогда и только тогда, когда2M 2 = M.(1.5)c = M 2 , получимДействительно, полагая Mc hi, ji =Mm_M hi, ti · M ht, ji(1.6)t=1c = M неравенства транзитиви, следовательно, в случае Mностиc hi, ji = M hi, ji > M hi, ti · M ht, jiMбудут выполнены при любых i, j, t из отрезка [1, m].

С другойстороны, из транзитивности рефлексивной матрицы M , всилу (1.6), следует, что _c hi, ji = M hi, ji ∨ MM hi, ji · M ht, ji = M hi, ji .16t6mt6=i,j1Матрица M, M ∈ B m,m , считается рефлексивной (транзитивной)тогда и только тогда, когда она задает рефлексивное (соответственнотранзитивное) отношение на множестве [1, m], то естьM hi, ii = 1(соответственно M hi, ti · M ht, ji > M hi, ji)для любого i (соответственно любых i, j и t) из отрезка [1, m].2Считаем, что при умножении матриц из 0 и 1 вместо операциисложения используется операция дизъюнкции.14Глава 2.

Основные классы управляющих системМатрица достижимости выходной выборки сети из ее входной выборки называется матрицей достижимости этой сети.Под «абстрактной» схемой понимается сеть, часть пометок которой составляют входные переменные и в каждойвершине которой реализуется функция (столбец из функций) от этих переменных. При этом считается, что самасхема реализует систему (матрицу), состоящую из функций (соответственно столбцов функций), реализованных наее выходах. В качестве выходных пометок схемы используются, как правило, специальные выходные переменные,а схема Σ с входными переменными (входами) x1 , . .

. , xnи выходными переменными z1 , . . . , zm записывается в видеΣ = Σ(x1 , . . . , xn ; z1 , . . . , zm ).Номер ν(α) набора α = (α1 , . . . , αn ) из B n считается номером ЭК (ЭД) ранга n от БП X (n) вида xα1 1 · · ·xαnn (соответственно xα1 1∨. . .∨xαnn ), множество всех таких ФАЛ обозначается Qn (соответственно Jn ), а система из всех указанныхФАЛ, упорядоченных по их номерам, называется конъюнктивным (соответственно дизъюнктивным) дешифратором−→порядка n от БП x1 , . .

. , xn и обозначается через Qn (соответ−→ственно Jn ). Функция вида_µn (x1 , . . . , xn , y0 , . . . , y2n −1 ) =xα1 1 · · · xαnn yν(α)α=(α1 ,...,αn )называется мультиплексорной функцией, или, иначе, мультиплексором порядка n, а переменные x = (x1 , . . . , xn ) (y =(y0 , . . . , y2n −1 )) считаются адресными (соответственно информационными) БП мультиплексора µn .Мультиплексорную ФАЛ порядка (n − q) , 0 6 q < n, отадресных БП x00 = (xq+1 , .