Покажите, что с учетом графа G и числа k можно каким-то образом преобразовать его в график H такой, что G имеет независимый набор размеров размером не менее k тогда и только тогда, когда H имеет клику размером не менее к.Уменьшение самостоятельного набора клики?
Независимый набор представляет собой группу узлов, где для любой пары узлов в наборе существует не граница между этими узлами. Клика - это группа узлов, где для любой пары узлов в наборе является границей между этими узлами. Поэтому независимое множество в графе G является кликой в complement группы G и наоборот.
Учитывая это, простое преобразование будет дано G и k для получения G c (дополнение к G) и k. Тогда G имеет независимый набор размеров k тогда и только тогда, когда G c имеет клику размера k.
Надеюсь, это поможет!