7 - Специальный раздел (1094798), страница 4
Текст из файла (страница 4)
S3, s3=/S3/ - позиции s1+ s2+1: s1+s2+s3 этого же вектора, и т.д.
В таблице 2.2 приведены значения элементов множества, различающиеся значением индекса:
Таблица 2.2 – Значения элементов множества
| список элементов S1 | список элементов S2 | и т.д. |
| А1, А2 ... , Аs1 | Аs1+1, Аs1+2,… Аs1+s2 | Аs1+s2+1… |
| S1 1:s1 k0=0 k1=s1 | S2 s1+1:s1+ s2 k2=s1+ s2 | S3 s1+ s2+1 |
Чтобы получить сведения о диапазонах индексов для каждого подмножества, достаточно завести еще один массив k(0:r) с целочисленными компонентами по числу подмножеств, в котором хранить значения:
k(0)=0
k(1)=s1
k(2)=s1+ s2
……………..
k(r)=s1+ s2+….+ sr
Очевидно, Sq представлено элементами массива:
(2.34)
Разделители подмножеств могут содержаться и в самом массиве А.
3. Если множества S1, S2, ... , Sr не пересекаются, связанный список легко разбить на r циклов, соответствующих разбиению N на подмножества . Кроме связанного списка необходимо хранить r указателей FIRST1, FIRST2, ... , FIRSTr на какие-либо элементы - представители S1, S2, ... , Sr. Если N содержит элементы не входящие ни в одно из подмножеств S1, S2, ... , Sr, из них можно составить особое подмножество или просто не заботиться об них.
4. Чтобы модифицировать характеристический вектор на случай дизъюнктных подмножеств S1, S2, ... , Sr достаточно вместо единицы в компоненту массива В занести номер содержащего данный элемент подмножества.
. (2.35)
Как было указано в начале этого раздела, для нахождения кратчайших путей преступника и, следовательно, для разработки алгоритма определения надежности СООПЗ необходимо представить в виде графа, это позволит рассчитать минимальное время прохождения к материальной ценности. Поэтому рассмотрим представление графов и их состав в теории алгоритмов.
Поскольку определение графа включает пару множеств - вершин и дуг, описание графа обязательно включает эти два объекта. Информационные структуры, соответствующие вершинам и дугам сети, чаще всего имеют последовательное представление (файл, вектор), поэтому и нумерация вершин и дуг предпочтительнее последовательная. В дальнейшем будем считать, что вершины графа занумерованы целыми числами из диапазона (1 :т), а дуги (1 :п), что снимает проблему представления этих объектов.
Остается отображение, сопоставляющее каждой дуге е из Е пару вершин (v, w) - начало и конец дуги.
При работе с графами необходимо отслеживать соотношение смежности, т.е. находить G(v,-) - множество концов дуг с началом в v и G(v,+) - множество начал дуг с концом в v.
При построении графа удобно рассматривать матрицу смежности:
R(V,W): R(i,j)=число дуг из i в j.
Эта матрица определяет смежность вершин графа, но имеет два основных недостатка: - занимая много места, практически почти всегда, она заполнена, в основном, нулями и единицами, что нерационально, - информация матрицы не позволяет восстановить номер дуги, реализующей связи между вершинами.
Построение матрицы инцидентности, позволяет избавиться от второго недостатка:
(2.36)
Построенная матрица также заполнена редко и не допускает петель в графе но, представление графа получается сжатием этих матриц.
Каждый столбец матрицы инцидентности содержит ровно два ненулевых элемента, 1 и -1 вводя пару векторов Left(E) и Right(E), запишем в компонентах Left(e) = v и Right(e) = w для дуги е из Е , е = (v,w).
Полученное представление называется списком начал и концов дуг. Недостаток этого способа - неудобство работы со множествами G(v,-) и G(v,+). Удобнее находить G(v,-) или G(v,+), если отсортировать список дуг в порядке возрастания начал (концов) дуг, т.к. множества E(v,-) для v из V(E(v,+)) образуют разбиение множества Е которое можно задать как указано выше.
Чтобы одинаково легко оперировать с G(v,-) и G(v,+) следует отсортировать множество дуг и по началам и по концам, создавая два индексных массива указателей.
Недостаток этого метода проявляется, если граф не ориентирован, или в нем присутствуют не ориентированные дуги. С алгоритмической точки зрения пара концов дуги е = (v,w) обязательно упорядочена, и любая попытка повысить эффективность структуры данных за счет сортировки или сжатия усложняет учет их несимметричности. Существует два пути решения этой проблемы:
1. Если количество неориентированных дуг невелико - каждая из них заменяется парой ориентированных противоположно. При таком подходе смежность задается множеством G(v) = G(v,-) + G(v,+).
2. Если наличие ориентации дуги указывается в виде признака ее параметра, например, отрицательного значения длины. Расшифровка такого признака должна быть предусмотрена в алгоритме.
50
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
