

どういった場合が森に分類されるのですか？


CC BY-SA 3.0
2015-07-14T14:56:23.983
12355
2015-07-14T15:35:30.237
10531
question
アルゴリズム
完全二分木は森に分類されますか？


[Wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%A8_\(%E6%95%B0%E5%AD%A6\))によれば、木と森の定義は以下の通りです。

木: 連結で閉路を持たない無向グラフ  
森: 閉路を持たない無向グラフ

森の特殊な形が木なので、すべての木は森です。完全二分木も、もちろん森です。

いくつか例を挙げます。xが節で-と|が枝だと思ってください。

[code]

        x---x
        |
    x---x---x
        |
        x---x
    
[/code]

これは **木** であり、 **森** でもあります。

[code]

        x---x
        |   |
    x---x---x
        |
        x---x
    
[/code]

これは閉路があるので **木** でもなく、 **森** でもありません。

[code]

        x---x         x
        |             |
    x---x---x    x----x----x
        |                
        x---x
    
[/code]

これは連結していないので **木** ではありませんが、 **森** です。  
（2つの連結しているグラフを個別に見れば **木・森** です）

[code]

        x---x         x
        |   |         |
    x---x---x    x----x----x
        |                
        x---x
    
[/code]

これは閉路があって連結もしていないので **木** でもなく、 **森** でもありません。  
（右のグラフだけを見れば **木・森** です）

[code]

        x---x        x
        |            |
    x---x---x---x----x----x
        |                
        x---x
    
[/code]

これは **木** であり、 **森** でもあります。


CC BY-SA 3.0
2015-07-14T15:26:41.107
12356
2015-07-14T15:35:30.237
2015-07-14T15:35:30.237
3639
3639
12355
answer