Набор-функция fff монотонно субмодулярная , если для всех A,BA,BA,B , f(A)+f(B)≥f(A∪B)+f(A∩B).f(A)+f(B)≥f(A∪B)+f(A∩B). f(A) + f(B) \geq f(A \cup B) + f(A \cap B). Более сильным свойством является...
Для двудольного графа с положительными весами пусть с равным максимальному совпадению весов в графе .f : 2 U → R f ( S ) G [ S ∪ V ]G=(U∪V,E)G=(U∪V,E)G = (U \cup V, E)f:2U→Rf:2U→Rf: 2^U \rightarrow \mathbb{R}f(S)f(S)f(S)G[S∪V]G[S∪V]G[S\cup V] Правда ли, что субмодулярная...
Учитывая субмодульную функцию еff на Ω =Икс1∪Икс2Ω=X1∪X2\Omega=X_1\cup X_2 где Икс1X1X_1 а также Икс2X2X_2 не пересекаются и е( S) =е1( S∩Икс1) +е2( S∩Икс2)f(S)=f1(S∩X1)+f2(S∩X2)f(S)=f_1(S\cap X_1)+f_2(S\cap X_2), Воте1f1f_1 а также е2f2f_2 субмодульный на Икс1X1X_1 а также Икс2X2X_2...