グラフ
概要 ドミノはトランプと同じくそれひとつでいろいろなゲームを楽しむことができる玩具のひとつである.本記事では,ドミノを用いたパズルの自動生成の手法とサンプルコードを紹介する. 準備 1セットのドミノは28枚の牌からなる*1.それぞれの牌は2つの領域…
勝敗グラフ 本記事における勝敗グラフを次のように定義する.勝敗グラフは有向グラフの一種である. 頂点集合,辺集合を持つ有向グラフを考える. に対しを次のように定義する. が次に示す条件を満たすとき,かつその場合に限り,は勝敗グラフである. 本記…
この記事で扱う問い 無向グラフの染色数をと表すとき,グラフに対する頂点数についての制約および染色数についての制約を同時に満たす無向グラフのうちで,辺数が最大であるものはいかなるグラフであろうか.ただし, 特殊なに対する答え まず,特殊なについ…
本文は後で書こう.次に示すSQL文は,有向グラフおよび辺に対する重みを与える写像について,最短経路のコストを導く.これをそのまま実行すると,次のについて,すべての2頂点間の最短経路のコストを導く.
本文は後で書こう.とりあえず使えそうなSQL文だけ載せておく.次に示すSQL文は,二部グラフについて,最大マッチングを発見する.これをそのまま実行すると,次のに対して最大マッチングを発見する.