グラフ理論入門 ７ 応用とアルゴリズム
７ 応用とアルゴリズム
7.1 全域木アルゴリズム
- グラフ理論のテキストで言うところのアルゴリズム
- 直観や実験によってはとくことができないほど複雑なグラフ(頂点数1000以上など）についての問題を解こうとしたときに、いつでも作動できることが保証されているような、形式的な手順のこと。
- また、効率的であることもアルゴリズムの特徴のひとつである。
- 全域木検出アルゴリズム
- 最小重みの全域木(minimum-weight spanning tree)検出アルゴリズム(Kruskal)
7.2 グラフにおけるマッチング、予定表問題
- マッチング(matching)
- 2部グラフにおけるマッチングとは、1正則の部分グラフのことである。すなわち、マッチングは、端点を共有しないような辺の集合である。
- 最大マッチング(maximum matching)
- 可能な限り多くの辺を持つマッチング。
- 赤頂点の個数と青頂点の個数が等しいならば、最大マッチングは1-因子となることがある。
- 予定表問題(scheduling problem)
- ハンガリーのアルゴリズム(Hungarian algorithm)
- 2部グラフにおける最大マッチングを見つけ出すための効率的アルゴリズム。
- M-交互道(M-alternating path)とM-増大道(M-augmenting path)
- 2部グラフにおいて、与えられたマッチングMに対して、Mに属する辺とMに属さない辺とが交互に現れる道のことをM-交互道と呼ぶ。M-交互道のうち、Mによってマッチされていない2つの頂点を結ぶものを、M-増大道と歩武。
- M-交互道を検出するアルゴリズム
- depth-first search
- 木を成長させる方法のうち、道が分岐する前に可能な限り遠くまで行くようにするアルゴリズムのこと。
7.3 2進木と接頭辞付きコード
- 入次数(indegree)と出次数(outdegree)
- 有向グラフにおいて、頂点vに入っていく弧の個数をvの入次数と言い、出て行く弧の個数をvの出次数と言う。
- 隣接(有向グラブの場合)
- 頂点vから頂点wに向かう弧が存在するとき、wはvから隣接するといい、vはwに隣接するという。
- 根付き木(rooted tree)
- 入次数0の頂点がただひとつだけ持つ有向木のこと。
- 根(root,r)
- 根付き木の入次数0の頂点。
- 2進木(binary tree)
- 根付き木でさらに各頂点の出次数が0,1または2のいずれかになっているもの。
- 葉(leaf, leaves)
- 根付き木の出次数0の頂点。
- コード(code)、コード語(codewords)、暗号文にする(encode)
- ある集合Aがあったとき、Aの要素の列を元とする集合のことをコードと言い、コードの元をコード語と言う。
- 接頭語(prefix)と接頭語付きコード(prefix code)
- コードからなる暗号文は、コードの始点終点の認識ができないと、デコードが困難である。コードの占める空間を統一するために追加された部分を接頭語と呼ぶ。
- 接頭語付きコードにおいては、どのコード語もそのコードのコード語の接頭語ではない。
- この原則を守っていれば、コードの長さはまちまちでもかまわない。
- このコードを作るにあたって、2進木を利用すると、コードは葉として得られる。
- 重み付き2進木(weighted binary tree)
- 葉に重み付けをしてある2進木。
- 2進木のTの重み(weight)
- Tの各葉bに対して、bの重みをw(b)で表し、根からbまでの距離をl(b)で表したとき、
- w(T)=summation(l(b)w(b)).
- Tの各葉bに対して、bの重みをw(b)で表し、根からbまでの距離をl(b)で表したとき、
- 多重集合(multiset)
- 要素が繰り返し現れることを許した、要素の集まりのこと。
- 多重集合に関する最小重みの2進木
- 2進木で、その葉が、多重集合の要素でラベル付けされ、w(T)が最小となるもの。
- ホフマンのアルゴリズム
