握手補題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/03/24 14:08 UTC 版)
「次数 (グラフ理論)」の記事における「握手補題」の解説
グラフ G = ( V , E ) {\displaystyle G=(V,E)} の次数の総和は次の公式で表される。 ∑ v ∈ V deg ( v ) = 2 | E | {\displaystyle \sum _{v\in V}\deg(v)=2|E|\,} これの証明は double counting という手法（二通りに数え上げる）の例である。グラフ内の辺と頂点の接合の個数は式の左辺のように各頂点の次数の総和でも表されるし、右辺のように辺の両端を数え上げてもよい。 この公式が意味するのは、次数が奇数の頂点の個数は偶数個だということである。これを握手補題 (handshaking lemma) と呼ぶ。この補題の名称は、あるグループ内で奇数人の人々と握手した人の数は常に偶数になるという数学の証明問題に由来する。
※この「握手補題」の解説は、「次数 (グラフ理論)」の解説の一部です。
「握手補題」を含む「次数 (グラフ理論)」の記事については、「次数 (グラフ理論)」の概要を参照ください。
ウィキペディア小見出し辞書の「握手補題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
このページでは「ウィキペディア小見出し辞書」から握手補題を検索した結果を表示しています。
Weblioに収録されているすべての辞書から握手補題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から握手補題
を検索
Weblioに収録されているすべての辞書から握手補題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から握手補題
を検索
- 握手補題のページへのリンク
