nkhrlab~

140字超の記事

グラフ

無向グラフに関する頂点数・染色数制約下での辺数の最大化

この記事で扱う問い 無向グラフの染色数をと表すとき,グラフに対する頂点数についての制約および染色数についての制約を同時に満たす無向グラフのうちで,辺数が最大であるものはいかなるグラフであろうか.ただし, 特殊なに対する答え まず,特殊なについ…

ワーシャル-フロイド法による最短経路の導出 - SQLによる解法

本文は後で書こう.次に示すSQL文は,有向グラフおよび辺に対する重みを与える写像について,最短経路のコストを導く.これをそのまま実行すると,次のについて,すべての2頂点間の最短経路のコストを導く.

二部グラフの最大マッチングの発見問題 - SQLによる解法

本文は後で書こう.とりあえず使えそうなSQL文だけ載せておく.次に示すSQL文は,二部グラフについて,最大マッチングを発見する.これをそのまま実行すると,次のに対して最大マッチングを発見する.