Выбор структур данныхВ качестве структур данных для аналитического представления гиперграфа будем использовать массивы динамических векторов, так как над ними выполняются только операции доступа. При работе алгоритма будут формироваться и использоваться массивы . Над массивом мы будем выполнять следующие действия: последовательная выборка элементов, добавление выбранной вершины в конец массива. Таким образом, структура данных для - динамический вектор. В массив будем добавлять новые вершины-кандидаты и исключать из него вершину . Для массива целесообразно использовать одно- или двусвязный список. Над массивом будут выполняться только операции просмотра его элементов (последовательного доступа), так как его элементы после корректировки пересчитываются заново. Следовательно, структура данных массива - динамический вектор. Основные пункты одного из вариантов алгоритма. 1. Включаем в формируемое множество некоторую вершину :
2. Определяем количество рёбер , соединяющих с :
3. Находим множество вершин - кандидатов на включение в : , где 4. Для каждой вершины определяем множество инцидентных ей рёбер , подмножество рёбер, приходящих в разрез, и подсчитываем показатель . Для этого: 4.1. 4.2. для выполняем: 4.2.1. Находим множество вершин , входящих в ребро 4.2.2. Проверяем условие Если условие не выполняется (ребро остаётся в разрезе) переходим к пп. 4.2.4. Выполнение условия означает, что ребро уходит из разреза – переходим к пп. 4.2.3. Подсчитываем показатель и переходим к п. 4.2.
Проверяем условие Если условие выполняется (ребро приходит в разрез при включении xi в Xl), переходим к пп. 4.2.5. При невыполнении условия переходим к анализу следующего ребра, т.е. к п. 4.2. 4.2.5. Включаем ребро в множество : , подсчитываем показатель : и возвращаемся к п. 4.2. 4.3. Определяем значение : и заносим его значение в массив :
5. Находим вершину , для которой минимально:
6. Подсчитываем количество рёбер , соединяющих множества и после включения в :
7. Проверяем ограничение на количество внешних выводов l -й части схемы: Если условие выполняется, то переходим к п. 8, иначе – к п. 12.
8. Включаем вершину в множество и исключаем её из :
9. Проверяем условие: , где nl – требуемое количество элементов в l -й части схемы.Если условие выполняется, то переходим к п.10, иначе – к п.13.
10. Определяем множество вершин, входящих в множество рёбер :
11. Корректируем множество вершин кандидатов : и возвращаемся к п. 4.
12. Дальнейшее формирование невозможно из-за нарушения ограничения на число внешних выводов. Переход на окончание работы алгоритма к п. 14.
13. Вывод результатов.
14. Конец работы алгоритма.
|