機械学習基礎理論独習

誤りがあればご指摘いただけると幸いです。数式が整うまで少し時間かかります。リンクフリーです。

勉強ログです。リンクフリーです
目次へ戻る

PRML演習問題 8.12(基本) www

問題

M個の異なる確率変数集合に対して2^{M(M-1)/2}個の異なる無向グラフが存在することを示せ。
M=3の場合における8個の可能なグラフをすべて描け。

解答

ノードはM個あり、あるノードが選ばれたとして、そのノードとリンクで結ばれるノードはM-1個あるので、リンクの数はM(M-1)個あります。
無向グラフなので、重複を除くとリンクの数は{M(M-1)/2}個になります。
リンクの有無を考えるので、求める無向グラフの数は2^{M(M-1)/2}となります。

M=3の場合における8個の可能なグラフを、以下の図1に記します。

図1
f:id:olj611:20211004032328p:plain:w600

目次へ戻る