Lectionc2 (1132951), страница 2
Текст из файла (страница 2)
При этом G0 считается подграфом графа G, натянутым на множество вершинV 0 , если E 0 включает в себя все входящие в E пары вершин из V 0 . Подграф, содержащий все вершины исходного§1. Основные понятия из теории графов, сетей, схем.9графа, называется его остовным подграфом. Легко видеть,что подграф всегда можно получить из исходного графа врезультате (многократного) применения операций удаленияребра или удаления вершины. При этом удаление вершины,как обычно, подразумевает удаление всех инцидентных ейребер.При определении понятий, связанных с «движениями»по графу, ограничимся случаем ориентированных графов,считая, как обычно, что неориентированное ребро эквивалентно двум противоположным дугам, связанным с той жепарой вершин. Последовательность C, состоящая из реберe1 , e2 , .
. . , en , где ei = (vi , vi+1 ) ∈ E (G) при всех i, i ∈ [1, n],называется (v1 − vn+1 )-путем графа G. При этом вершина v1 (vn+1 ) считается начальной (соответственно конечной)вершиной этого пути, вершины v2 , . . . , vn — его внутренними вершинами, а число n — его длиной. Если все ребра пути различны (как элементы соответствующего сочетания),то он называется цепью, а если, кроме того, различны всеего вершины, то — простой цепью. Если начальная и конечная вершины пути (цепи) C совпадают, то C считаетсязамкнутым путем (соответственно циклом). Цикл, в котором все вершины, кроме начальной и конечной, различны,называется простым циклом.Будем говорить, что вершина u достижима из вершины v в графе G, где u, v ∈ V (G), если u = v или в G существует (v − u)-цепь. Заметим, что отношение достижимостивершин графа G является рефлексивным и транзитивным,а если G — неориентированный граф, то и симметричным.Следовательно, множество вершин графа G распадается наклассы эквивалентности по отношению их достижимости вb который получается из графа G заменой каждойграфе G,bдуги на соответствующее неориентированное ребро (G = G,если G — неориентированный граф).
При этом подграф графа G, натянутый на каждый такой класс вершин, называ-10Глава 2. Основные классы управляющих системется связной компонентой графа 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 можно определитьее глубину (соответственно исходящую глубину), как максимальную длину (u − v)- (соответственно (v − u)-) путей графа G, где u — один из истоков (соответственно стоков) G.1Под симметрической разностью графов G1 и G2 понимается графG, для которогоV (G) = V (G1 ) ∪ V (G2 ) ,E (G) = (E (G1 ) ∪ E (G2 )) \ (E (G1 ) ∩ E (G2 )) .§1.
Основные понятия из теории графов, сетей, схем.11Легко видеть, что отношение достижимости является отношением частичного порядка на множестве вершин ориентированного ациклического графа и обратно.Неориентированный связный ациклический граф называется деревом. Для дерева G, как известно, имеет месторавенство|E (G)| = |V (G)| − 1.(1.3)Дерево с выделенной вершиной (корнем) называется корневым деревом, а все отличные от корня вершины степени 1 этого дерева считаются его листьями. Ориентированный граф, который получается из корневого дерева заменой каждого его неориентированного ребра на соответствующую дугу, «направленную» к корню, называется ориентированным деревом.Дерево (ориентированное дерево) D, являющееся остовным подграфом графа G, называется его остовным поддеревом, а дерево D0 , которое получается из D в результате«подсоединения» всех не вошедших в него ребер G к своим«начальным» вершинам, — остовным наддеревом графа G.Очевидно, что при этом граф G может быть получен из дерева D0 в результате присоединения некоторых вершин степени 1 (листьев) к другим его вершинам.
Заметим, что любой неориентированный связный граф, а также любой ориентированный ациклический граф с 1 стоком всегда имеютостовные поддеревья и наддеревья соответствующего типа.Граф, вершинам и (или) ребрам которого сопоставлены определенные символы (пометки), считается помеченным графом. Примером такого графа является, в частности, корневое дерево. Другим примером помеченного графа является ациклический граф с монотонной нумерациейвершин, когда для любой дуги номер вершины, из которойона исходит, больше номера вершины, в которую эта дугавходит. Ориентированный граф G называется упорядочен-12Глава 2.
Основные классы управляющих системным, если для любой его вершины 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 соответственно,причем выборка V 0 является выборкой без повторений, называется (p, q)-сетью. При этом выборка V 0 (выборка V 00 )считается входной (соответственно выходной) выборкой, а ееi-я вершина называется i-м входным (соответственно выходным) полюсом или, иначе, i-м входом (соответственно выхо-§1.
Основные понятия из теории графов, сетей, схем.13дом) сети 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, входят в свою первую общую вершину.Для произвольныхвыборок V 0 = v10 , .
. . , vp0 и V 00 == v100 , . . . , vq00 из множества V (G) графа G определим матрицу достижимости выборки V 0 из выборки V 00 как матрицу M, M ∈ B p,q , для которой(1, если vj00 достижима из vi0 ,M hi, ji =0, в остальных случаях.Заметим, что в случае V 0 = V 00 матрица M является рефлексивной и транзитивной1 , а если, кроме того, G — неори1Матрица M, M ∈ B m,m , считается рефлексивной (транзитивной)14Глава 2. Основные классы управляющих систементированный граф, то и симметричной матрицей. Заметим также, что транзитивность рефлексивной матрицы 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].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
