ペアのリストのペアの最大数を見つける

Question

私は特定の数から生成したペアのリストを持っています。私の質問は、私がそれを理解したように私のペアがどのように計算されるかに関しては関係ありませんが、可能な限り多くのペアを最大限にしています。例えば
：

{1:[19,13,21], 
3:[7,19], 
7:[3,19,13], 
19:[1,3,7,21], 
13:[1,7,21], 
21:[1,19,13]} 

1の結果は、19、13、または21 3とペアリングすることができる

[1,3,7,19,13,21] 

そうで7または19と対とすることができます。私の目標は、ユニークなペアリングを最大限にして、ペアのないポイントを最小限に抑えることです。この場合、1-13、3-7、および19-21を持つことができ、残りは0になります。しかし、あなたは1-19、7-13もやって、相手がいなくても3と21を残すことができます。

以前にこの問題を処理していたアルゴリズムはありますか？私はそれらをグラフに入れ、ハミルトニアンの最大の経路を見つけようと考えましたが、それは事実上不可能と思われます。私はPythonでこれをやっているので、コンテナとして使用している辞書とリストがあります。

編集：数字がペアになるかどうかの条件は、ペアと特定のパターンを形成するかどうかです。 2つの数xとyが与えられると、x == yになるまでこのパターンに従うか、それは永遠に続く。 x <yの場合、 y = y - x、x = 2 * xです。そして、それはあなたが記述問題は、（iがjとペアになっている場合、あなたの例では、その後、jもiと対になっているので、あなたがすることによって、それらを接続することができ、グラフでmaximal matchingを見つけることです

Answer 1

...など、再び行きます縁）。以下のpython packageおよび this codeには、関連する実装が含まれています。