Способы задания структур

 

Структуру объекта можно задавать (описывать) разными способами, наиболее известные из них: графический, матричный, в виде таблицы, аналитический, множественный [6].

Графический способ (см. рис. 1.6) используется для представления структур с небольшим числом элементов и уровней. Его главное достоинство – наглядность, недостаток – громоздкость.

Матричный способ. Структура может быть описана матрицей смежности или матрицей инцидентности. Матрица смежности строится по правилу: число элементов в матрице – n ´ n, где n – число вершин графа; a _ij – элемент матрицы; i – номер строки; j – номер столбца матрицы; i = 1… n, j = 1… n, i ¹ j, если не допускаются петли, т. е. связи элемента с самим собой:

0, если отсутствует связь элемента i с j,

α _ij =

1, если имеется связь элемента i с j.

 

Матрица инцидентности строится по правилу: число элементов в матрице – n ´ m, где n – число вершин графа, m – число ребер графа, b _ij – элемент матрицы, i – номер строки, j – номер столбца матрицы, i = 1… n, j = 1… m:

0, если отсутствует связь элемента i с ребром j,

β _ij =

1, если имеется связь элемента i с ребром j.

 

Матричное описание целесообразно использовать для многоэлементных и многосвязных структур.

Описание структуры в виде таблицы (см. табл. 1.3).

Аналитическое представление используется только для описания строгих иерархических структур. Правило чтения структу-
ры – строго слева направо на каждом уровне и сверху вниз по уровням иерархии. Например, для структуры на рис. 1.6:

F ₁(f ₁₁(f ₁₁₁, f ₁₁₂)), f ₁₂(f ₁₂₁, f ₁₂₂), f ₁₃,), F ₂(f ₂₁, f ₂₂, f ₂₃ (f ₂₃₁, f ₂₃₂)).

Число пар скобок равно уменьшенному на единицу числу уровней иерархии. Запятая служит разделителем при перечислении элементов одного уровня. Этот способ является самым компактным при описании многоуровневых иерархических систем.

Множественный способ – это способ задания структуры в виде списков соответствия вершин, например, G (i) = (i, j, k, …, n) – множество переходов вправо, т. е. множество вершин, в которые можно попасть из вершины i; или G (i)^–1 = (i, j, k, …, n) – множество переходов слева, т. е. множество вершин, из которых можно попасть в вершину i.