抽象によるソフトウェア設計 付録A 練習問題 その4

付録A続きます。

• A.1.6 スパニング木
  • ここに書いてある定義だけではスパニング木の仕様はよくわかりませんでしたがこういうことかな

pred isTree (r: univ -> univ) {
     r.~r in iden
     no iden & r
     no x: univ | univ in x.^r
  }

pred spans (r1, r2: univ -> univ) {
    r1.univ + univ.r1 = r2.univ + univ.r2    
  }

• A.1.7 リングを特徴付ける
  • 全体で1つのリングを構築するとします。

sig Node {next: set Node}

pred isRing() {
  all n1, n2: Node {
    one n1.next
    n2 in n1.^next
    }
  }

• A.1.8 無向グラフに対して非循環性を定義する
  • これは比較的簡単。自分の隣接するノード(adjs)に自分自身が含まれないことを制約に追加する。しかし難しい問題であることを指すクローバーマークがついているので何か見落しているのかも。

sig Node {adjs: set Node}

pred acyclic() {
  adjs = ~adjs
  no n: Node { n in n.adjs }
  }