グラフの木分解〜グラフ理論とわたし - エンジニアのソフトウェア的愛情グラフを木分解します。 …。 木分解。わたしもひと月前まで聞いたこともありませんでした。 木分解とは。おおざっぱに言うと、グラフからルールに従って部分グラフの集合を取り出し、その部分グラフを木構造のノードとする木を作ること。 くわしいことはこことかを参照してみてください。 なぜこのようなことをやっているかというと。仕事でアルゴリズムの実装というのを引き受けまして。これがグラフ理論の論文でして。このひと月ほど集中的にグラフ理論の勉強をしているとこでして。 そのアルゴリズムの実装に木分解が必要になり、木分解のアルゴリズムのひとつである最小次数法というのを実装してみた次第。 Graphクラスを定義した graph.rb を用意します。 require 'Set' class Graph attr_reader :edges, :vertices def initialize @edges = {
