Покрытие графа кликами.
Разница между ru1 и en1, 383 символ(ов) изменены
Такой вопрос назрел. Дан граф. Требуется покрыть все ребра графа минимальным количеством клик.(ВАЖНО: каждое ребро РОВНО в одной клике).↵
Например:↵
Граф из реберSuch a question is ripe. There is a graph. It is required to cover all the edges of the graph with the minimum number of cliques.↵
↵
IMPORTANT: each edge is EXACTLY in one click.↵
↵
Example:↵
Graph edges: (1, 2), (1, 3), (2, 3), (3, 4), (2, 4).↵
Ответ 3.↵
↵
Пытался гуглить, ничего не нашел путного.↵
Если кто может пруфануть класс сложности, буду благодарен.Output: 3.↵
↵
I tried googling, but couldn't find anything.↵
↵
Who can prove complexity class, I will be grateful!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Extraordinary_ 2022-03-23 10:57:11 32
en1 Английский Extraordinary_ 2022-03-23 09:46:51 383 Initial revision for English translation
ru1 Русский Extraordinary_ 2022-03-22 21:01:47 339 Первая редакция (опубликовано)