algorithm - ファンインエッジカラーリングアルゴリズムを構築する際に色付けされていないエッジを処理する方法

Question

Misra & Gris エッジ カラーリング アルゴリズムの実装に問題があります。簡単な質問があります-最大ファンの構築で色付けされていないエッジをどのように処理するのですか?

無色はすべての頂点で自由な色ですか、無色の頂点でのみ自由です(無色を別の色として扱います)、または他の方法ですか?

Answer 1

どうやらそれは問題ではありません (すべての証明を注意深く読んでコードを書いた後)。ただし、無色のエッジを使用すると、誤ってエッジの色が失われる可能性があるため、そのようなセットアップで追跡する必要があります。また、そのような場合、最大ファンは大きくなります。