2015年5月15日金曜日

R-99 グラフ - Prolog-99 Ruby版 日本語訳

R-99: 99 の Ruby の問題 - 6. グラフ

  • 訳注1:問題番号の後のアスタリスクはPrologで解くときの難易度の目安。

グラフ問題

グラフ理論では、用語の意味がかなり変わる。一部の著者は、異なる意味で同じ単語を使用している。 一部の著者は、同じことを意味する別の単語を使用している。ここで使う用語の定義では、 矛盾がないことを願っている。

グラフは、エッジのセットとノードのセットの集合として定義される。

Ruby でグラフを表現する方法はいくつかある。

一つの方法は、一節として別個にエッジを表す方法である。 この形態では、上記のグラフは以下のように表すことができる。

a = new Edge(h,g),
b = new Edge(k,f),
c = new Edge(f,b),
...

ここでは、この形態をエッジ節フォームと呼ぶ。

明らかに、孤立したノードを表現することができない。別の方法は、1つのデータオブジェクトとして グラフ全体を表すことである。 二組(ノードとエッジ)のグラフの組の定義に従うと、上記の例のグラフを 表すために、次の関数を使用することがある。

graph([b,c,d,f,g,h,k],[e(b,c),e(b,f),e(e,f),e(f,k),e(g,h)])

ここではこれをグラフ要素フォームと呼ぶ。リストがソートされていることに注意せよ。 それらは既に設定されているものと重複する要素はない。各エッジは、エッジのリストに一度だけ表される。 たとえば、エッジ表現のノード X からノード Y は e(x,y)と表され、要素e(y,x)は存在しない。 グラフ要素フォームは、ここでの標準的な表現とする。

第3の表現方法は、各ノードにそのノードに隣接するノードの集合を関連付けることである。 ここでは、これを隣接リストフォームと呼ぶ。この例では:

[n(b,[c,f]), n(c,[b,f]), n(d,[]), n(f,[b,c,k]), ...]

これまでに導入された表現は、構文がユーザフレンドリではない。 要素を手入力すると、面倒でエラーを起こしやすい。次のように、よりコンパクトで「ヒューマンフレンドリ」な 表記法を定義する。 グラフはタイプ X-Y の最小単位と要素数で表される(例えば、関数記号 '-' と引数の数 2)。 最小単位は孤立ノードを表し、X-Y の要素はエッジを表す。 X は、エッジの終端として表されている場合、自動的にノードとして定義されている。 今回の例は以下のように記述できる。

[b-c, f-c, g-h, d, f-b, k-f, h-g]

ここでは、ヒューマンフレンドリフォームと呼ぶ。例が示す通り、リストをソートする必要はなく、さらに 同一エッジを複数回含むことができる。孤立ノード d に注目せよ。 (実際には、孤立ノードも例の d の代わりに、d(3.75,"blue")のように、要素を混ぜ合わせることができ、 Ruby の最小単位である必要はない。

エッジに向きがある時、孤(アーク)と呼ぶ。これらは、順序のペアで表される。 このようなグラフは、有向グラフ(略してダイグラフ)と呼ぶ。

有向グラフを表すには、上のフォームをわずかに変更する。例えば、次のようにグラフが表される。

エッジ節フォーム
    arc(s,u),
    arc(u,r),
    ...
グラフ要素フォーム
    digraph([r,s,t,u,v],[a(s,r),a(s,u),a(u,r),a(u,s),a(v,u)])
間接リストフォーム
    [n(r,[]),n(s,[r,u]),n(t,[]),n(u,[r]),n(v,[u])]

隣接リストは、それがグラフや有効グラフであるかどうかについての情報を持っていないことに注意せよ。

ヒューマンフレンドリフォーム
    [s > r, t, u > r, s > u, u > s, v > u] 

最後に、グラフと有向グラフは、ノードとエッジ(アーク)に取り付けられた追加情報を有していてもよい。

アーク節フォーム
    arc(m,q,7)
    arc(p,q,9)
    arc(p,m,5)
グラフ要素フォーム
    digraph([k,m,p,q],[a(m,p,7),a(p,m,5),a(p,q,9)])
間接リストフォーム
    [n(k,[]),n(m,[q/7]),n(p,[m/5,q/9]),n(q,[])]

エッジ情報が対応するノードで、関数記号 '/' で引数が 2 の要素にパックされたことに注目せよ。

ヒューマンフレンドリフォーム
    [p>q/9, m>q/7, k, p>m/5]

ラベルづけされたグラフの表記法では、複数のエッジ(アーク)は2つの指定されたノード間で許可されている いわゆるマルチグラフに使用することができる。

6.01 (***) 変換

別のグラフ表現の間で変換する関数を書け。これらの関数では、全ての表現は同等である。 すなわち、以下の問題のために、あなたは常に最も便利な表記法を選ぶことができる。 この問題が(***)に評価された理由は、この問題が特に難しいからではなく、この問題の解が特別な場合に 対処するために役立つためである。

6.02 (**) 別のあるノードからのパス

グラフ G にノード A からノード B への非循環パス P を見つけるための関数 path(G,A,B) を書け。関数は、バックトラックして全てのパスを経由する必要がある。

6.03 (*) 指定されたノードから循環

グラフ G の指定されたノード A から始まる閉じたパス(循環) P を発見する関数 cycle(G,A) を書け。関数は、バックトラックを介して全ての循環を返す必要がある。

6.04 (**) 全てのスパニングツリーを作成せよ

訳注: 「スパニングツリー」とは、ループするグラフ内で、1度とったパスを2度と通らないような パスをツリー状に表したもの。

(バックトラックによって)与えられたグラフの全てのスパニングツリーを作成するための関数 s_tree(graph,tree)を書け。この関数を使用すると、上のグラフにある複数のスパニングツリーを 調べる。 関数s_tree(graph,tree)のための正しい解を持つ時、他の2つの有用な関数を定義して使う: is_tree(graph)is_connected(graph)。両方とも作成するのに5分程度の作業であろう。

6.05 (**)

与えられたラベル付きグラフの最小スパニングツリーを作成するための関数ms_tree(graph,tree) を書け。

ヒント: 「プリムのアルゴリズム」を使用せよ。問題 6.04 の解を小さく変更するのがコツである。

6.06 (**) グラフ同型

全単射 f が存在する時、2つのグラフ G1(n1,e1) 及び G2(n2,e2) が同型である。 f とは、n1 から任意のノード X,Y の間で x と y が隣接する時のみ、f(x) と f(y) が隣接する。

二つのグラフが同型であるかどうかを判断する関数を書け。 ヒント: 関数 f を書くために、オープンエンドリスト(訳注:終端の決まっていない構造のリスト) を使用する。

6.07 (**) ノードの次数とグラフ着色

訳注: 「次数」とは、繋がっているノードの数のこと。

  1. 与えられたノードの次数を測定する関数degree(graph,node)を書け。
  2. 度合いを降順ソートし、グラフの全てのノードのリストを作成する関数を書け。
  3. 隣接ノードは、異なる色を持つようにグラフのノードを描くために、ウェルチ-パウエルのアルゴリズム を使用せよ。

6.08 (**) 深さ優先グラフ探索

深さ優先グラフ探索の探索順を作成する関数をかけ。出発点を与える必要があり、出力は(深さ優先順で) この出発点から到達可能なノードのリストである必要がある。

6.09 (**) 連結した構成要素

その連結した構成要素にグラフを分割する関数をかけ。

6.10 (**) 2部グラフ

与えられたグラフは2部グラフであるかどうかを調べる関数を書け。

訳注: 「2部グラフ」とは、グラフのノードを2つのグループ A,B に分け、各エッジがグループ A の ノードからグループ B のノードに繋がっている(すなわち、同じグループ同士のノードが繋がっていない)時、 このグラフを「2部グラフ」と呼ぶ。

6.11 (***) N 個のノードを持つ K-正則単純グラフを作成せよ。

K 正則グラフでは、全てのノードは K の次数を持っている。すなわち、各ノードに繋がるエッジの数は K である。ノードが 6 個ある 3-正則グラフはいくつか。(非同型のもの!)

0 件のコメント:

コメントを投稿