ケイリーの公式とは何？わかりやすく解説 Weblio辞書

ケイリーの公式

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

ケイリーの公式（ケイリーのこうしき、英: Cayley's formula）は、グラフ理論における公式のひとつ。正整数 n に対し、n 個のラベル付き頂点を持つ木の個数は n^n-2 であるというもの。ケイリーは19世紀のイギリスの数学者。

「ケイリーの公式」の続きの解説一覧

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:32 UTC 版)

「プリューファー列」の記事における「ケイリーの公式」の解説

n {\displaystyle n} 頂点の木に対するプリューファー列は n − 2 {\displaystyle n-2} の長さの、 1 {\displaystyle 1} から n {\displaystyle n} の整数からなる一意な列である。逆に、長さ n − 2 {\displaystyle n-2} で 1 {\displaystyle 1} から n {\displaystyle n} の整数からなるすべての列について、対応する木がただ一つ存在する。この定理は、ただちに「 n {\displaystyle n} 頂点の木と長さ n − 2 {\displaystyle n-2} で 1 {\displaystyle 1} から n {\displaystyle n} の整数からなる列に全単射が存在する」という系を導く。列としてありうるものは n n − 2 {\displaystyle n^{n-2}} 個存在するので、 n {\displaystyle n} 頂点の木は n n − 2 {\displaystyle n^{n-2}} 通り存在するとするケイリーの公式が示される。

※この「ケイリーの公式」の解説は、「プリューファー列」の解説の一部です。
「ケイリーの公式」を含む「プリューファー列」の記事については、「プリューファー列」の概要を参照ください。

ウィキペディア小見出し辞書の「ケイリーの公式」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。お問い合わせ。


	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアのケイリーの公式 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
	Text is available under GNU Free Documentation License (GFDL). Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのプリューファー列 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。