ポーサの定理

グラフ理論におけるポサの定理は、無向グラフの頂点の次数に基づいてハミルトン閉路が存在するための十分条件です。この定理は、次数に基づく他の2つの十分条件、ハミルトン閉路に関するディラックの定理とオレの定理を導きます。これらの条件とは異なり、ポサの定理は次数が低い頂点の数が少ないグラフにも適用できます。この定理は、 1947年生まれでポール・エルデシュの弟子であり、1962年にこの定理を発見したラヨシュ・ポサにちなんで名付けられました。

有限無向グラフのポサ条件${\displaystyle G}$持っている${\displaystyle n}$頂点の次数が${\displaystyle n}$頂点を昇順に並べると

${\displaystyle d_{1}\leq d_{2}\leq ...\leq d_{n},}$

次に各インデックスについて${\displaystyle k<n/2}$不平等${\displaystyle k<d_{k}}$満足している。

ポサの定理は、有限無向グラフがポサ条件を満たすならば、そのグラフにはハミルトン閉路が存在すると述べている。

• Pósa、L. (1962)、「ハミルトン線に関する定理」、Magyar Tud。アカド。マット。クタト国際空港ケズル。、7 : 225–226、MR 0184876 
• Katana–Recski–Szabó: A számítástudomány alapjai、Typotex、ブダペスト、2003 年、(ハンガリーの学部レベルのコース ブック)。
• Kronk, Hudson V. (1969)、「Pósaの定理の一般化」、ア​​メリカ数学会紀要、21 (1): 77–78、doi : 10.2307/2036861、JSTOR 2036861、MR 0237377  
• Kühn, Daniela ; Osthus, Deryk ; Treglown, Andrew (2009)、「有向グラフにおけるハミルトンサイクルを強制する次数列」、欧州組合せ論・グラフ理論・応用会議（EuroComb 2009）、Electron. Notes Discrete Math.、第34巻 、アムステルダム：Elsevier Sci. BV、pp. 347–351、doi：10.1016/j.endm.2009.07.057、MR 2591466  
• Yin, Jian-Hua; Zhang, Yue (2011)、「Pósa条件とnowhere-zero 3-フロー」、Discrete Mathematics、311 (12): 897–907、doi : 10.1016/j.disc.2011.02.023、MR 2787300 

• ワイスタイン、エリック W.、「ポーサの定理」、MathWorld
• ポサの定理について