解の一意性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/22 07:43 UTC 版)
解の一意性を証明することは、 ( ω + d d ′ φ 1 ) m = ( ω + d d ′ φ 2 ) m {\displaystyle (\omega +dd'\varphi _{1})^{m}=(\omega +dd'\varphi _{2})^{m}} の時に、φ1 と φ2 が定数のみ異なることを示すことである（すると、正規化されていて、平均値が 0 であることの双方を示すと同一であるはずである）。カラビは、このことを | d ( φ 1 − φ 2 ) | 2 {\displaystyle |d(\varphi _{1}-\varphi _{2})|^{2}} の平均値が多くとのゼロである表現により与えられることを証明した。少なくともゼロであることが示すと、ゼロとなるはずであるから、 d ( φ 1 − φ 2 ) = 0 {\displaystyle d(\varphi _{1}-\varphi _{2})=0} となり、このことは φ1 と φ2 が定数しか異なっていないことを示していることとなる。
※この「解の一意性」の解説は、「カラビ予想」の解説の一部です。
「解の一意性」を含む「カラビ予想」の記事については、「カラビ予想」の概要を参照ください。
解の一意性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/11/24 15:50 UTC 版)
もしトポロジカルソートされたノードのすべてのノードが隣接する次のノードへの辺を持つなら、元の有向非巡回グラフはハミルトン路を含む。もしハミルトン路が含まれるなら、トポロジカルソートの結果は一意、つまり2つ以上の解は存在しない。逆に、トポロジカルソートがハミルトン路を作らないなら、元の有向非巡回グラフは2つ以上のトポロジカルソート結果を持つ。その場合、ある結果のうち直接辺によってつながっていないノードを交換することで2番目のトポロジカルソート結果を得ることができる。従って、一般のグラフにおけるハミルトン路の問題はNP困難であるが、一意なトポロジカルソート結果が存在するかどうか、あるいはハミルトン路が存在するかどうかは多項式時間で決定することができる。
※この「解の一意性」の解説は、「トポロジカルソート」の解説の一部です。
「解の一意性」を含む「トポロジカルソート」の記事については、「トポロジカルソート」の概要を参照ください。
- 解の一意性のページへのリンク
