Покрытие графа кликами.

Revision ru1, by Extraordinary_, 2022-03-22 21:01:47

Такой вопрос назрел. Дан граф. Требуется покрыть все ребра графа минимальным количеством клик.(ВАЖНО: каждое ребро РОВНО в одной клике). Например: Граф из ребер (1, 2), (1, 3), (2, 3), (3, 4), (2, 4) Ответ 3.

Пытался гуглить, ничего не нашел путного. Если кто может пруфануть класс сложности, буду благодарен.

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 Первая редакция (опубликовано)