118
качественную, чем количественную оценку надежности
рассматриваемых вариантов схемных решений.
6.2. Элементы теории графов
Графом (Y, B) называется упорядоченная пара множеств:
конечного непустого множества Y, элементы которого y
i
называются
узлами графа, и множества В, элементы которого b
k
(i, j) называются
ветвями этого графа. Последние представляют собой пары элементов
множества Y. В дальнейшем для упрощения записи узлы и ветви
графа будем обозначать их индексами: ,iY
где i = 1, 2, ... , n;
(, ) ,ij B∈ где ,.iYjY∈∈ Ветви графа бывают ориентированными и
неориентированными.
Ориентированная ветвь имеет начало и конец
(направление). В связи с этим графы могут быть ориентированными,
неориентированными и смешанными. Ветвь, соединяющая два узла,
инцидентна им и, наоборот, оба узла инцидентны этой ветви.
Два узла (, )ij Y∈ называются
смежными, если соединены
ветвью (, )ij B∈ . Две ветви смежные, если существует хотя бы один
узел, инцидентный им обеим (общий узел).
Путь (1–n) между двумя узлами y
1
и y
n
есть последовательность
ветвей, смежных одна с другой {(1,2),...,(l,i),(i,j),(j,h),...,(k,n)}, в
которой у каждой ветви (i, j) один из инцидентных ей узлов i также
инцидентен предыдущей ветви последовательности (l, i), а другой
узел j инцидентен последующей ветви (j, h). Путь, в котором
начальный узел совпадает
с конечным (1 = n), называется контуром
(замкнутым путем). Ориентация отдельных ветвей может не
совпадать с ориентацией пути в целом. Ветви, направление которых
совпадает с направлением пути, называются
прямыми ветвями, а при
несовпадении направлений пути и ветви ветвь называется
обратной.
Граф
связен, если между любыми двумя узлами его можно
проложить путь.
Несвязный граф состоит из нескольких