inamori https://blog.hatena.ne.jp/inamori/ inamori’s diary https://inamori.hateblo.jp/ グラフ プログラミング m点で辺の数がm-1で連結のとき、グラフは木になる。ループがなくて連結のグラフを木と呼ぶ。 m点で辺の数がm-1のグラフの数を数える。辺の種類はm(m-1)/2ある。ここからm-1辺を選ぶから、 m(m-1)/2Cm-1 そのうち、連結なグラフの数をT(m)で表す。前々回、T(4) = 16、T(5) = 125であることを確認した。一般にはどうなるだろう。 m点のうちの1点を取り出す。これは他の点と連結している。1点かもしれないし、2点かもしれない。1点だとすると、この点を取り除くとこのグラフは連結である。だから、1点で繋がっている場合は、T(m-1)あることになる。2点なら連結のグラフが2… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finamori.hateblo.jp%2Fentry%2F20090404%2Fp1" title="グラフが連結である確率（3） - inamori’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/i/inamori/20090407/20090407210449.png Hatena Blog https://hatena.blog 2009-04-04 00:00:00 rich https://inamori.hateblo.jp/entry/20090404/p1 1.0 100%