Построить контур из графика, который выводит 1, если граф имеет независимое множество

Question

Допустим, у меня есть график,

и на этом графике я хочу создать схему K, чьи входы можно установить так, чтобы K выдает истину, если график имеет независимый набор размером ≥2. Я видел кое-что приличное в Интернете / YouTube о том, как это сделать. Но мне было интересно, если есть стандартный набор шагов, которые нужно выполнить, как это сделать.

Мой мыслительный процесс был в некотором роде: иметь схему, принимающую ребра в качестве входных данных, и вывод 1 (true), если по крайней мере один ребро отсутствует (так как этот ребро является независимым набором).

Но если я честен, мне трудно обдумать это.

Answer 1

Ваш подход корректен в концепции, но есть еще более простой способ: подсчитать ребра на графике. Для N узлов, если | E | = 2. Все, что вам нужно, - это один пропущенный край, как вы заметили.

Чтобы найти наибольший независимый набор, есть довольно простой в концепции прием преобразования: переверните график: переключите все не ребра и ребра. Например, ваш опубликованный график содержит 4 из 6 возможных ребер. Инвертируйте это, чтобы ребра вашего графа были только DB и DC.

Возьмите полученный график и найдите самую большую клику (об этом много материала). Эта самая большая клика - самый большой независимый граф.