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

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

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

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

Первоначальная допустимая раскраска может быть получена так: 1)     Окрасить все вершины в цвет 1. 2)     Перейти к следующей вершине (изначально берем первую ): a)     если среди смежных к данной ранее встречался ее цвет, увеличить номер цвета на 1 b)     иначе вернуться в пункт 2 если еще остались вершины. Для обычного графа дальше следует улучшение раскраски, ее минимизация. Но в данном случае мы

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

ЭВМ. Нельзя создавать вершины расположенные слишком близко друг к другу и к краям “экрана”. 2)     Все введенные вершины окрашиваются в цвет “0”. Это делается для того, чтобы изолированные вершины тоже имели свой цвет. 3)     Формируется матрица инцидентности, если вершина (полностью, ибо она вообще имеет некоторый размер) попала в область, то она инцидентна соответствующему ребру. Попутно, все вершины

попавшие в область окрашиваются в цвет “1” 4)     По матрице инцидентности формируется матрица смежности. Просматриваются все вершины. Если две вершины инцидентны одному и тому же ребру то они смежные. Обратите внимание, что для гиперграфа обратный процесс невозможен(!). 5)     Собственно сам алгоритм. Просмотр всех вершин, если смежные с данной вершиной (используется матрица смежности) имеют такой же цвет,