Определение операций преобразования исходного графа в граф результата. Выбор способа представления графов и его реализация в памяти ЭВМ

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

• граф, являющийся математической моделью объекта проектирования, его характеристики и свойства;

• вид, характеристики и свойства графа – математической модели результата проектирования;

• целевая функция и ограничения задачи, т. е. функции, зависящие от управляемых параметров (характеристик графа результата) и свойств, которыми должен обладать этот граф. Анализируя эту информацию и зная элементарные теоретико-множественные и алгебраические операции над графами, мы можем определить операции, необходимые для преобразования исходного графа в граф результата.

Напомним, что к элементарным операциям над графом относятся операции удаления, добавления, разбиения, стягивания или свертки, установления соответствий и раскраски его вершин или ребер. Следует отметить, что далеко не всегда эти операции очевидны и однозначны.

Обратимся ко второму свойству решения: граф результата – дерево, т. е. не должен иметь циклов. Обязательно ли мы получим дерево, удалив (m - n +1) ребер и сохранив связность графа? Проанализировав определение остовного дерева, мы получим положительный ответ. Мы выполнили достаточно полный анализ и определили основную операцию преобразования графа G в остовное дерево. Является ли операция удаления ребер единственно возможной и эффективной с точки зрения вычислительной сложности алгоритма с учетом проверки связности получаемого графа? Точные алгоритмы решения этой задачи – алгоритмы Прима и Краскала используют операцию добавления ребер, причем количество таких операций n -1. В ходе работы алгоритма Краскала связность получаемого графа обеспечивается автоматически, а для того, чтобы избежать циклов при построении дерева посредством подсоединения ребра u (xi, xj) минимального веса, достаточно проверить принадлежность вершин – концов этого ребра разным подграфам. Эта операция имеет вычислительную сложность O (1).

От способа представления графа и его реализации в памяти ЭВМ в значительной степени зависят как вычислительная, так и емкостная сложность алгоритма.

Построение эффективной организации включает два этапа:

• выбор способа представления графа множествами;

• выбор организации связных множеств, представляющих граф, в памяти ЭВМ.

Организация данных в памяти ЭВМ должна обеспечивать высокую эффективность их обработки и экономное использование объема.

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