異なる a, b について，a が b の倍数になるときに a から b に辺を張るような N 頂点のグラフを考える．このグラフは推移的グラフであるので，最大独立集合 = 最小パス被覆 である (Dilworth の定理)．DAG の最小パス被覆は二部グラフの最大マッチングで解…