木
#グラフ理論
定義
無向グラフ
サイクル
がない
連結グラフ
である
性質
次の4つは同値である
$ T
は木である
$ T
は連結で、
$ T
の辺は全て橋である
$ T
は連結で、サイズ
$ |E(T)|
は
$ |V(T)| - 1
である
$ T
は閉路を含まないが、
$ T
の非隣接な2頂点を辺で結ぶとちょうど1個の閉路ができる
位数2以上の木には、次数1の頂点が少なくとも2点存在する
次数1の頂点を
葉
と呼ぶのではなく
葉
は有向木の概念
関連
有向木
根つき木
気持ち
「一本道」
木の問題はまず「一本道」で考える
次にウニで考える
色々な木
Union-Find
BIT(Fenwick Tree)
Segment Tree
例題
E - Virus Tree 2
ABC138 D - Ki
Removing Coins - AGC 033 - C