選択したエッジがサイクルを形成せず、選択したすべてのエッジの重みの積が最大になるようにグラフからエッジを選択することを目的とする codechef の質問を見ました。社説では、プリムとクルスカルのアルゴリズムが機能することが示されています。 here.実際、エッジの対称単調関数を最大化するために機能することが与えられています。では、対称単調関数とは正確には何であり、このアルゴリズムを他にどこで使用できるのでしょうか。
選択したエッジがサイクルを形成せず、選択したすべてのエッジの重みの積が最大になるようにグラフからエッジを選択することを目的とする codechef の質問を見ました。社説では、プリムとクルスカルのアルゴリズムが機能することが示されています。 here.実際、エッジの対称単調関数を最大化するために機能することが与えられています。では、対称単調関数とは正確には何であり、このアルゴリズムを他にどこで使用できるのでしょうか。