リポジトリ 全域木(spanning tree), 極大木 : においてとなる辺集合があるとき、グラフが木（閉路を持たないグラフ）であるなら、 をの全域木と呼ぶ。 (全域木が存在することと連結であることは同値) 最小全域木(MST: Minimum Spanning Tree) : 使われる辺の…

リポジトリ Carden Lantern(AOJ No.0072) 無向グラフとの長さが与えられる。 全ての辺には100メートルごとに、１本の灯篭を立てる。 連結を維持したまま、辺を除いたときの、最小の灯篭の数を求める。 制約 の長さ アルゴリズム 要するに最小全域木の合計コ…

(無向)グラフの要素 要素が頂点(vertex), 点(point), 節点(node)の集合 辺(edge)と呼ばれる頂点の順序対の集合 隣接(adjacent) : 辺(u,v)が存在するとき頂点は隣接するという。 接続(incident) : が辺の端点(endpoint)であるとき、はに接続するという。 多重…