マトロイド

    https://ja.m.wikipedia.org/wiki/マトロイド

    貪欲法で最適化できる性質を持つ集合のこと

    • 空集合を含む
    • 部分集合は必ず含まれる
    • 小さいものから大きいものへの遷移が可能

    これであれば貪欲法の局所解が最適解と一緒になるのでで解ける

    グラフの辺集合における森の集合とかがマトロイドになるので、つまり最小全域木問題が解けることになる

    そういうマトロイドのことをグラフマトロイドとか閉路マトロイドとかいう

    閉路マトロイドの基は全域木になる