片側に N 個のノードがあり、反対側にほぼ 100 個のノードがある二部グラフがあります。ここで、最初の部分の各ノードが他の部分のノードへのリンクを持ち、最初の部分の 2 つのノードが 2 番目の部分の同じノードに一致しないように、一致をカウントする必要があります (1 つのジョブを 1 つのノードに割り当てることができるように)。申込者のみ）
このカウントを見つけるのは簡単ではなく、#P 困難な問題であることがわかりました (リンクから: https://cs.stackexchange.com/questions/19924/counting-and-finding-all-perfect-maximum-matchings-in -一般的なグラフ)
しかし、そうするための野蛮な解決策は何でしょうか?誰かがコードまたは疑似コードで説明してください。
入力が、u が v に接続されていることを示す X ペアを持っているようなものであると仮定します
N=2 および X=4 で、ペアが (1,1)、(1,2)、(2,3)、(2,4) の場合。