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

Правка ru1, от Extraordinary_, 2022-03-22 21:01:47

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

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

История

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