@IIepyH

Здравствуйте помогите пожалуйста с 2-мя заданиями, или хотя бы каким алгоритмом его делать. Я совсем не понимаю как их сделать. буду очень очень благодарен.


1) -=Транзитивный подграф=-

условие:
заданы ориентированный граф G=(V,A) и положительное целое число k<=|A|

вопрос:
существует ли подмножество А' , принадлежащее множеству А, такое что |A'|>=k и граф G=(V,A') транзитивен? (Граф называется транзитивным, если для любой пары вершин u и v существует третья вершина (w принадлежащее v), такая что (u,w),(w,v) принадлежат A', то ( u,v) принадлежащее A'

2) -= сравнительное содержание=-


условие:
Заданы два набора R={R1,R2,....,Rk} и S={S1,S2,.....,Si} подмножеств конечного множества Х и для всех i и j (1<=i<=k,1<=j<=i) веса w(Ri),w(Si) принадлежащее множеству положительных целых чисел

вопрос:

Существует ли такое подмножество Y принадлежащее множеству Х, что
сумма( по всем Y ,принадлежащим Ri,) от w(Ri) >= сумме( по всем Y ,принадлежащим Si,) от w(Si)


помогите пожалуйста или с рекурсивным кодом или с алгоритмом что бы эти задания сделать.

0

@IIepyH

помогите хотя бы с заданием с подграфом

0