Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Выбор структур данных





В качестве структур данных для аналитического представления гиперграфа будем использовать массивы динамических векторов, так как над ними выполняются только операции доступа. При работе алгоритма будут формироваться и использоваться массивы .

Над массивом мы будем выполнять следующие действия: последовательная выборка элементов, добавление выбранной вершины в конец массива. Таким образом, структура данных для - динамический вектор. В массив будем добавлять новые вершины-кандидаты и исключать из него вершину . Для массива целесообразно использовать одно- или двусвязный список. Над массивом будут выполняться только операции просмотра его элементов (последовательного доступа), так как его элементы после корректировки пересчитываются заново. Следовательно, структура данных массива - динамический вектор.

Основные пункты одного из вариантов алгоритма.

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. Конец работы алгоритма.

 







Дата добавления: 2015-04-19; просмотров: 457. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Хронометражно-табличная методика определения суточного расхода энергии студента Цель: познакомиться с хронометражно-табличным методом опреде­ления суточного расхода энергии...

ОЧАГОВЫЕ ТЕНИ В ЛЕГКОМ Очаговыми легочными инфильтратами проявляют себя различные по этиологии заболевания, в основе которых лежит бронхо-нодулярный процесс, который при рентгенологическом исследовании дает очагового характера тень, размерами не более 1 см в диаметре...

Примеры решения типовых задач. Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2   Пример 1.Степень диссоциации уксусной кислоты в 0,1 М растворе равна 1,32∙10-2. Найдите константу диссоциации кислоты и значение рК. Решение. Подставим данные задачи в уравнение закона разбавления К = a2См/(1 –a) =...

Интуитивное мышление Мышление — это пси­хический процесс, обеспечивающий познание сущности предме­тов и явлений и самого субъекта...

Объект, субъект, предмет, цели и задачи управления персоналом Социальная система организации делится на две основные подсистемы: управляющую и управляемую...

Законы Генри, Дальтона, Сеченова. Применение этих законов при лечении кессонной болезни, лечении в барокамере и исследовании электролитного состава крови Закон Генри: Количество газа, растворенного при данной температуре в определенном объеме жидкости, при равновесии прямо пропорциональны давлению газа...

Studopedia.info - Студопедия - 2014-2025 год . (0.015 сек.) русская версия | украинская версия