マトロイド

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

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

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

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

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

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

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