Покрытие графа кликами.
Difference between ru1 and en1, changed 383 character(s)
Такой вопрос назрел. Дан граф. Требуется покрыть все ребра графа минимальным количеством клик.(ВАЖНО: каждое ребро РОВНО в одной клике).↵
Например:↵
Граф из ребер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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Extraordinary_ 2022-03-23 10:57:11 32
en1 English Extraordinary_ 2022-03-23 09:46:51 383 Initial revision for English translation
ru1 Russian Extraordinary_ 2022-03-22 21:01:47 339 Первая редакция (опубликовано)