Раскраска вершин гиперграфа — страница 4

  • Просмотров 2793
  • Скачиваний 466
  • Размер файла 2482
    Кб

инцидентности — 4mn сравнений (попадание в область) и mn присваиваний. матрице инцидентности формируется матрица смежности — m2/2 операций сравнения строчек, в каждую из которых входит n операций инкремента, т.е. m2n/2 операций присваиваний. И тогда оценка: m ( n + 5 ) + m2 n / 2 — присваиваний и 4mn + m2/2 — сравнений. Итого (n + 1)( 5m + m2/2) операций. Вместе с алгоритмом это составляет m(5n + 6) + m2 (2n+7)/4 операций. Также можно сказать, что сложность

алгоритма составляет O(m2n). Сложность программы больше сложности алгоритма. Это связано с выбранным способом считывания данных.   При вводе, данных используются простые циклы, поэтому можно сказать, что сложность аввода составляет O(m) + O(n). При выводе, данных используются простые циклы и вложенные циклы для вывода матриц инцидентности и смежности поэтому можно сказать, что сложность вывода составляет O(m) + O(n) + O(nm) + O(m2) т.е. O(m( m + n

)). Данная оценка показывает, что сложность всей программы остается O(m2n).       Приведем иллюстрации тестовых примеров.   1)     Цикл с нечетным числом вершин Результат — 3 цвета. 2)     “Цепочка” Результат — 2 цвета. 3)     Одно ребро с 8 смежными вершинами Результат — 8 цветов. 4)  “Пирамида”   Результат — 5 цветов. 5)        “Матрица”   Результат — 3

цвета. 6)     Цикл с нечетным числом вершин Результат — 2 цвета. 7)     Ввода 256-ой вершины и 256-ого ребра не происходит. 8)     Одна вершина инцидентная одному ребру — один цвет. 9)     Ввод только вершин — раскраска не происходит, ввод только ребер — раскраска не происходит. Прикладная задача.   Задача раскраски в “чистом” виде редко встречается на практике. Однако ее

разновидности находят широкое применение в большом числе прикладных задач. С помощью составленной программы очень удобно производить распределение ресурсов. Пользователю современной ЭВМ (с многозадачной операционной системой) требуется выполнить несколько процессов. Процессы могут выполняться параллельно, но при этом иногда они запрашивают один и тот же ресурс (принтер, факс, модем, жесткий диск), который может быть

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