サイクルが一意ではない二部グラフに完全に一致していますか?

Hallの定理(非特異的である)を満たす均衡のとれた二部グラフが与えられれば、それは少なくとも一つの完璧なマッチングを有することを示した。

私の質問は、均衡のとれた二者グラフも非巡回の場合、完璧な一致一意であるかどうかです。

もしそうなら(私はほとんどそれが確信しています)、引用できるソースに私を向けることができますか?私はそのような書類を手に入れることができませんでした。

ベストアンサー

グラフが二項であることを意味する非周期的なグラフである場合、完璧なマッチングは次のアルゴリズムによって一意である。

グラフが空ではない間に、葉の頂点$ u $(グラフが非周期的であるために存在する)を選び、$ u $とその固有の隣人$ v
$の間のエッジをマッチングに追加し、$ u $と$ v $
。インシデントエッジのないグラフが生成される場合は、完璧なマッチングはありません。

これはたぶん民間の知識であり、引用可能な情報源がないことを意味します。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です