![ここから重心分解～!!!
N=5のとき: 重心+残った4頂点で(最大)4部分木
但し、重心に繋げられるのは、 N/2 頂点以下の部分木
[2,2,0,0] , [2,1,1,0] , [1,1,1,1]
それぞれのアルキル基は一意に定まっているので、合計3通り
(炭素数≦2なら(部分)木の形は1通りなので)](https://image.slidesharecdn.com/graphtheory-1-200501140326/85/1-27-320.jpg)
![次も重心分解で
N=6、一般にNが偶数の場合では場合分けが必要
(i)重心が1つの場合
N=5の時とほぼ同じだが、少し注意が必要
「偶数頂点かつ重心が1つ」?「重心にくっついている部分木の
頂点は N/2 未満」
N=6の場合、3頂点の部分木はくっつかない
残りの5頂点を振り分ける[2,2,1,0] , [2,1,1,1] の2通り](https://image.slidesharecdn.com/graphtheory-1-200501140326/85/1-28-320.jpg)
![解答1:N=7の場合
重心+残った6頂点で最大4部分木
部分木として繋げるのは3頂点以内の部分木
[3,3,0,0] [3,2,1,0] [3,1,1,1] [2,2,2,0] [2,2,1,1]
このうち、3頂点のアルキル基が絡む場合は厄介
[3,3,0,0]... 3頂点のアルキル基2つが重複組み合わせで3通り
[3,2,1,0] , [3,1,1,1]... 3頂点のアルキル基の繋ぎ方で2通り
結局、全部ひっくるめて9通り](https://image.slidesharecdn.com/graphtheory-1-200501140326/85/1-31-320.jpg)
![解答2:N=8の場合
(i) 重心が1つの場合
偶数頂点かつ重心が1つなので、つなげるアルキル基のサイズ
は3以下になる
[3,3,1,0]... 3頂点が2つ、重複組み合わせで3通り
[3,2,2,0]... 3頂点の繋ぎ方で2通り
[3,2,1,1]... 3頂点の繋ぎ方で2通り
[2,2,2,1]... 1通り](https://image.slidesharecdn.com/graphtheory-1-200501140326/85/1-33-320.jpg)
More Related Content
What's hot (20)
グラフ理論入門 1
- 8. 木の特徴(Wikipediaより) n 個の点からなるグラフ T について次は同値である。 T は木である T に閉路はなく、 n ? 1 本の辺を持つ T は連結で、 n ? 1 本の辺を持つ T は連結で、すべての辺は橋である T の任意の2点を結ぶ道がちょうど1つある T に閉路はないが、新しい辺をつけ加えると閉路が必ず1つで きる
- 11. 木の特徴(Wikipediaより)をやさしい日本語に N 個の点からなるグラフ T について次は同値である。 「T は木である」 →当たり前。そもそも議論の前提。 「T に閉路はなく、 n ? 1 本の辺を持つ」 閉路:「N重結合 = 多重辺」 か 「環 = ループ」 →木は「N頂点、N-1辺からなるループのない無向グラフ」
- 12. 木の特徴(Wikipediaより)をやさしい日本語に 「T は連結で、 n ? 1 本の辺を持つ」 →木は「N頂点をN-1本の辺で繋いだ無向グラフ」 「T は連結で、すべての辺は橋である」 →どの1つの辺を消したとしても、 木は2つに分割されてしまう
- 15. 具体的にどう求めるか? 辺の数: H + 2*O + 3*N + 4*C = x とおく 頂点の数: H + O + N + C = y とおく (辺の数は両側の原子でカウントされていることに注意) x = 2(y-1) ならグラフは木なので不飽和度は0 そうでない場合、不飽和度=余る辺の数は (x - 2(y-1)) / 2 (これが整数にならない場合は化合物として不適切) これを変形すると (2*C + N - H + 2) / 2 (いつもの)が求まる
- 17. 具体例
- 18. 同じグラフで重心がもうひとつ
- 19. 重心が高々2つであることの証明 頂点数 N の木において、☆を付けた2頂点が重心だったとする (雲の部分は何らかの木が繋がってると思ってください) 図のA,Bの領域で頂点数が N/2 以下である必要がある このとき☆の頂点が辺で隣接する必要がある (∵☆の間に頂点が挟まっていると、 A+Bの頂点数ののべの総和がNを超える なので、鳩の巣原理より、詰む)
- 26. アルキル基の场合の数も求めておく
- 27. ここから重心分解～!!! N=5のとき: 重心+残った4頂点で(最大)4部分木 但し、重心に繋げられるのは、 N/2 頂点以下の部分木 [2,2,0,0] , [2,1,1,0] , [1,1,1,1] それぞれのアルキル基は一意に定まっているので、合計3通り (炭素数≦2なら(部分)木の形は1通りなので)
- 28. 次も重心分解で N=6、一般にNが偶数の場合では場合分けが必要 (i)重心が1つの場合 N=5の時とほぼ同じだが、少し注意が必要 「偶数頂点かつ重心が1つ」?「重心にくっついている部分木の 頂点は N/2 未満」 N=6の場合、3頂点の部分木はくっつかない 残りの5頂点を振り分ける[2,2,1,0] , [2,1,1,1] の2通り
- 29. N=6の場合 (ii) 重心が2つの場合 サイズ N/2 のアルキル基を2つ組み合わせればよい サイズ3のアルキル基を2つ組み合わせるが、注意が必要 「サイズ3のアルキル基」には2通り考えられるが、この2つは重 複組み合わせで数える必要がある 2通りで2つ選ぶ→2H2 = 3C2 = 3 通り (i)(ii) 合わせて5通り
- 30. 课题1:狈=7の场合
- 31. 解答1:N=7の場合 重心+残った6頂点で最大4部分木 部分木として繋げるのは3頂点以内の部分木 [3,3,0,0] [3,2,1,0] [3,1,1,1] [2,2,2,0] [2,2,1,1] このうち、3頂点のアルキル基が絡む場合は厄介 [3,3,0,0]... 3頂点のアルキル基2つが重複組み合わせで3通り [3,2,1,0] , [3,1,1,1]... 3頂点のアルキル基の繋ぎ方で2通り 結局、全部ひっくるめて9通り
- 32. 课题2:狈=8の场合
- 33. 解答2:N=8の場合 (i) 重心が1つの場合 偶数頂点かつ重心が1つなので、つなげるアルキル基のサイズ は3以下になる [3,3,1,0]... 3頂点が2つ、重複組み合わせで3通り [3,2,2,0]... 3頂点の繋ぎ方で2通り [3,2,1,1]... 3頂点の繋ぎ方で2通り [2,2,2,1]... 1通り
- 34. 解答2:N=8の場合 (ii) 重心が2つの場合 サイズ N/2 のアルキル基を2つ組み合わせればよい サイズ4のアルキル基を2つ組み合わせるが、注意が必要 「サイズ4のアルキル基」には4通り考えられるが、この2つは重 複組み合わせで数える必要がある 4通りで2つ選ぶ→4H2 = 5C2 = 10 通り (i)(ii) 合わせて18通り
- 42. グラフ理論 2に続く …?