вершинная раскраска гиперграфа

Гиперграф это граф ребра которого могут содержать не 2 вершины, как у обычного, а большее или меньше.


Это так картинка для примера. Точки - вершины, а овалы ребра. Прямая тоже ребро - содержит 2 вершины.

Теперь о самом главном: Гиперграф называется k-раскрашиваемым, если любое ребро содержит две вершины, окрашенные в разные цвета.

Есть способ выделения независимых множеств вершин.(Множество в. независимое, если оно не содержит ребер) Тогда как, я понял, вершины в из каждого множества красятся в разные цвета и получаем правильную минимальную раскраску.

Кто-нибудь сталкивался с раскраской гиперграфа? Как искать эти независимые подмножества? Или есть еще какие-нибудь методы?

Принимаются любые идеи и соображения. Может среди них найдется то, что является решением для составления алгоритма правильной вершинной раскраски гиперграфа.
А может кто-нибудь алгоритм где-то видел или знает? Напишите, пожайлуста.

Сообщение отредактировано: dan-leech - 18.12.03, 17:42

На русском ничего не нашел, а на аглицком вот эти ссылки глянь, авось пригодится:
http://math.net.md/voloshin/mh.html
http://citeseer.ist.psu.edu/lu98deterministic.html
http://citeseer.nj.nec.com/cs?q=hypergraph...+Documents&cs=1

Сообщение отредактировано: C300G - 18.12.03, 23:34

скорее всего задача НП полная так что лучшее решение известное на сейчас это грубый перебор


насколько мне известно в качестве первого приближения можно применить вероятностый алгоритм
смотри Noga Alon probabilistic methods

Ну да задача, в общем случае да, NP-НЕполная. Т.к. ребер может быть до ~2^N...

А что делать с 1-кратными ребрами? Они в определении не описаны...

Если их не учитывать, ета задача в общем-то сводится к задаче на обычном графе: между вершинами есть связь, если есть гиперсвязь в гиперграфе...

Сообщение отредактировано: Visitor - 19.12.03, 11:57

Понятненько...

Про 1-кратные ребра я так понимаю, что вершина краситься в один цвет и все. А вот про то, есть ли петля(если приводить к обычному) понятия не имею.
Я так понял, что можно представить гиперграф ввиде обычного, где все вершины, которые были внутри одного ребра гиперграфа, соединены ребром. И расматривать задачу как на обычном графе.


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

Я пока не реализововал, но похоже на правду. Может кто упращение предложит или модернизацию. Мне скорость алгоритма не важна, главное результат. Препода потешить.

to C300G:
Спасибо за ссылки, я на английском почему-то не догадался искать. А на русском действительно ничего в сети нет.

Люди, а как определить сложность алгоритма для этого алгоритма???
И как их вобще определять(сложности)?

Через оценку времени исполнения попробуй:
http://algolist.manual.ru/misc/o_n.php

Подумал, что может быть кому-нибудь данная задача пригодиться. Там реализовано рисование графа под WinAPI, прям в окне и алгоритм переборной, лобовой так сказать, раскраски вершин. Вобще алгоритм годиться для любых графов.
Исходники на VS 6 и сама прога

Кто найдет почему у меня после многих перерисовок все становиться черно-белым(где-то память вроде теряется с кистями или перьями). Напишите пожайлуста как это исправить на [EMAIL]dan-leech@mail.ru[/EMAIL].

Всем еще раз большое спасибо за помощь!!! Прога написана, заказчик доволен...
И С ПРАЗДНИКАМИ ВСЕХ!!!

Сообщение отредактировано: dan-leech - 05.01.04, 16:53