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


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

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

to C300G:
Спасибо за ссылки, я на английском почему-то не догадался искать. А на русском действительно ничего в сети нет. ]]> dan-leech Алгоритмы https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266547 Fri, 19 Dec 2003 11:46:07 +0000 https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266547
А что делать с 1-кратными ребрами? Они в определении не описаны...

Если их не учитывать, ета задача в общем-то сводится к задаче на обычном графе: между вершинами есть связь, если есть гиперсвязь в гиперграфе... ]]> Visitor Алгоритмы https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266465 Fri, 19 Dec 2003 09:53:21 +0000 https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266465

насколько мне известно в качестве первого приближения можно применить вероятностый алгоритм
смотри Noga Alon probabilistic methods ]]> esperanto Алгоритмы https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266280 Thu, 18 Dec 2003 23:30:11 +0000 https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266280 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 Алгоритмы https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266108 Thu, 18 Dec 2003 17:17:21 +0000 https://forum.sources.ru/index.php?showtopic=41016&view=findpost&p=266108

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

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

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

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

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