ホールの定理

OR事典

ホールの定理

読み方：ほーるのていり
【英】：Hall's theorem

2部グラフ において, 左側点集合 に関する完全マッチングが存在するための必要十分条件は次のように書ける:

この不等式の右辺は, 中に左側点をもつ枝の右側点の数を表す.この必要十分条件をホールの定理と呼ぶ. ケーニグ・ホールの定理 (K\"onig--Hall's Theorem) と呼ばれることもある.

「OR事典」の他の用語

グラフ･ネットワーク：

フェンシェル型双対定理  プリム法  ベルマン・フォード法  ホールの定理  ポリマトロイド  マッチング  マッチング問題

ウィキペディア

ホールの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/14 20:57 UTC 版)

ホールの定理（英: Hall's theorem）または結婚定理（英: marriage theorem）は、組合せ数学の帰結の1つで、有限集合の集まりのそれぞれから別個の元を選択できる条件を与える。名称の由来は数学者のフィリップ・ホール（1904年-1982年）。

ウィキペディア小見出し辞書

ホールの定理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 23:42 UTC 版)

「ホール部分群」の記事における「ホールの定理」の解説

Hall (1928) は G が有限可解群で π が素数からなる任意の集合とするとき、G がホール π-部分群を持ち、任意の二つのホール π-部分群が互いに共軛となることを示した。さらに言えば、π に属する素数の積を位数に持つ任意の部分群は、適当なホール π-部分群に含まれる。この結果は、シローの定理のホール部分群に対する一般化と考えることができるが、前述の例にあるとおり群が可解でない場合にはそのような一般化はできない。 ホール部分群の存在性は、任意の有限可解群は基本アーベル正規部分群を持つという事実を用いて、G の位数に関する帰納法で示せる。より精確には、G が π-分離的なる限り A が π-群または π′-群となるような極小の正規部分群 A を固定するとき、帰納法により、G の A を含む部分群 H が存在して、H/A が G/A のホール π-部分群となるようなものが存在する。A が π-群ならば H は G のホール π-部分群である。他方、A が π′-群ならば、シューア–ツァッセンハウスの定理（英語版）により A は H の補群を持ち、それが G のホール π-部分群になる。