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

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

то данная вершина перекрашивается в цвет на единицу больший. Для простоты и удобства проверки, я вместо цвета каждой вершине сопоставляю число, которое называю “цветом”. 6)     Вывод на экран нарисованного пользователем гиперграфа, с раскрашенными вершинами. Вывод матрицы смежности и инцидентности. Здесь я не привожу организации ввода и вывода программы. С алгоритмической точки зрения это не столь интересно,

хотя играет некоторую роль в оценке сложности программы. В пункте 3, необходим поиск максимального и минимального числа из неупорядоченного множества, для определения границ областей. В данном случае я использовал стандартные алгоритмы языка программирования C++. Но это можно сделать и вручную: объявить некоторое число первое минимальным (максимальным), если найдется число меньше (больше) этого, то его объявить минимальным

(максимальным), повторять пока не завершится последовательность. Вершина представлена как структура из трех единиц ( координаты и цвет), ребро — из четырех (координаты углов прямоугольника) Оценка сложности   Для начала проведем оценку самого алгоритма. Пусть m — число вершин, n — число ребер. В данном случае мы не рассматриваем случай когда все вершины гиперграфа изолированные, программа не даст создать такой

гиперграф. Раскраска всех вершин в цвет “1” займет m шагов независимо от расположения вершин. Далее, просмотр всех вершин займет еще m шагов. Проверка среди смежных вершин ранее встречавшегося цвета — m/2 шагов (сумма арифметической прогрессии), но так как на данном этапе мы проверяем и наличие элемента в матрице смежности и цвет, то здесь имеем m шагов. В лучшем случае, граф не содержит смежных вершин. И тогда оценка

алгоритма: m — присваиваний и m2 — сравнений. Итого m2 + m операций. В худшем случае, все вершины графа смежные тогда, для каждой вершины мы должны инкрементировать ее цвет согласно ее номеру. А это m2/2 операций. Тогда оценка алгоритма: m + m2/2 — присваиваний и m2 — сравнений. Итого 3m2/2 + m операций. Вообще, учитывая строение современных ЭВМ, и особенности выбранного языка программирования, можно утверждать, что мы выполняем лишь m

присваиваний, ибо операция инкремента, значительно “дешевле” присваивания. Но общая оценка остается прежней. Средняя оценка 5m2/4 + m операций. Также можно сказать, что сложность алгоритма составляет O(m2);   Далее, проведем оценку самой программы без ввода-вывода. Раскраска всех вершин в цвет “0” займет m шагов. 4m на формирование границ областей. Сложность стандартных алгоритмов не учитываем. Формируется матрица