【グラフ理論とネットワーク理論】Extended Complete Graph
Connectivity and Damage Index
Connectivity
Connectivity express the reliability of the graph
- Node Connectivity Cv(G) : Minimum number of nodes to be removed to make a graph unconnected.
- Branch Connectivity Ce(G) : Minimum number of branches to be removed to make a graph unconnected.
- Node connectivity = d → d - 1 node failures OK
- Branch connectivity = d → d - 1 branch failures OK
Theorem1
Cv(G) ≦ Ce(G) ≦ δ(G) : δ = degree (the number of branches of one node)
Damage index
Damage index is an index of the increase of hops to connect in case of failure.
α-Node(Branch) Damage Index Iα(G) (Jα(G)) is defined as blow
Maximum diameter of a graph without α nodes(branches)-Diameter of the original graph G
Design Method of Extended Complete Graph
Extended Complete Graph : Complete graph Gd → Line conversion, m times → Extended complete graph.
Lm(Gd) = L(L(…(L(G))…)) (m times)
Ex. 1
| Number of nodes | Number of branched | |
|---|---|---|
| Gd | d+1 | (d+1)d |
| L(Gd) | (d+1)d | (d+1)d2 |
| L2(Gd) | (d+1)d2 | (d+1)d3 |
Comparison
| Complete graph | Extended Complete Graph | |
|---|---|---|
| 正則性 Regularity | d-Regular | d-Regular |
Number of nodes V |
d + 1 | (d + 1)dm |
Number of branches E |
(d + 1)d | (d+1)dm+1 |
| 直径 Diameter k(G) | 1 | m+1 |
| Node connectivity Cv(G) | d | d |
| Branch connectivity Ce(G) | d | d |
| 次数 Degree δ(G) | d | d |
| 節点罹障度 Node damage index Iα(G) | 0 | ≦ m |
| 枝罹障度 Branch damage index Jα(G) | 1 | ≦ m+1 |
Throughput ratio in case of failure
k(G)/(Jα(G) + k(G)) → 0.5 for both Gd and Lm(Gd)
Least Recently Used (LRU) cache を実装する
合計の入れ替え Cracking The Coding Interview
問題
２つの整数配列が与えられる。それぞれの配列から１つずつ要素を決め、それらを交換した時に２つの配列の要素の合計値が一致するようなペアを見つける問題。
入力: {4, 1, 2, 1, 1, 2} と {3, 6, 3, 3}
出力: {1, 3}
解法
全列挙の解法 O(A*B)
i, jを添え字にしてforループを２つネストすることで２つの配列における全ての要素の組合せを得られる。i, jをスワップさせた時に合計値が一致すればそれらを出力する。この解法の計算量は(O(A*B)) (２つの配列のサイズをそれぞれA, Bとする)
O(A + B)の解法
実は、配列Aから交換する要素が決定されれば、配列B内の交換するべき要素の候補は決定する。配列A, Bの総和をsumA, sumBとし、それぞれの配列内の交換するべき要素をa, bと置くと。 sumA - a + b = sumB - b + aが成り立つ。あとはaだけを全列挙すればbが決定されるので、計算して得たbが配列B内に存在するかをチェックしてあげれば良い。この解法の計算量はO(A + B)。
ソースコード
古い携帯電話 ガラケーのキーボード
問題
ガラケーのキーボードにおいて、入力値としてキーボード上の押した数字が与えられる(連打回数は無視)。 この時に、押した数字によって得られる単語の組合せの内、辞書に乗っているものを出力する問題。辞書は予め与えられ、データ構造は自由に設定できるものとする。
例: 「２」を押すと'a', ‘b’, ‘c'のどれかとなる。
「３」を押すと’d’, ‘e’, ‘f'のどれかとなる。
解法
全列挙で頑張る
全列挙を考えると、数字に対応する全ての文字のパターンを列挙し、辞書に存在するかを確認する方法が挙げられる。この解法の計算量はO(N4)となる。Nは入力値の桁数であり、１つの数字に対して対応する文字は最大４つなので、全パターンを列挙するためには約N4通り存在するからだ。この解法はとても遅い。
トライ木を用いた解法
上記の解法を少し工夫する。上記の解法で悪い点は、全てのパターンの文字列を生成している点である。中には始めの２文字を選んだ時点で辞書に乗っている単語か否かをチェックすることができれば、その文字は生成する必要がなく途中で処理を止めることができる。枝刈りができるわけだ。これを得意とするのがトライ木である。
事前準備をしてO(N)で解く
最も早い解法は、辞書の中身の単語を予め、ガラケーのキーボードに対応して数字に変換しておくことだ。辞書の単語とその単語を数字に変換したものをHashMapに保存しておけば、入力値の数字から辞書中に存在する単語はO(1)で取得するこができる。
ソースコード
【グラフ理論とネットワーク理論】線形構成法
線形構成法 Linear Design Method
直径最小化問題 Minimizing Diameter Problem
(n, d) グラフとは、接点数n, 各接点は出枝、入枝をそれぞれd本ずつもっているグラフのこと。このグラフの事をd正則有向グフラと呼ぶ。 また、経路の長さは、経路中の枝の数で決まる。そして、距離δ(i, j)はiからjへの最短経路の長さと定義する。
グラフの直径とは、グラフ内における２接点間距離の最大値。
(n, d)グラフの直径最小化問題を解きたい。
直径１以下の(5, 2)グラフは存在しない。
→ このグラフが(5, 2)グラフ最小化問題の解の１つ。
(n, d)グラフの直径の下界値
1 + d + d2 + d3 + … + dk = (dk+ 1 - 1)/(d - 1)
距離がｋ以下の接点数を最大化。
直径の下界値をｍとすると
(dm - 1) / (d - 1) >= n
↓
m >= 「log_d {n(d - 1) + 1}」 - 1 => l(n, d)
「x」= Smallest integer >= x
「log_d n」 - 1 <= l(n, d) <= 「log_d n」 (3.1)
線形構成法 Linear Design Method
定義 枝(i, j)とした時に、jは次式で計算される。
j ≡ (a*i + b) * d + α (mod n) , α = 0, 1, 2, 3, ,,,d - 1 (3.2)
a, b: 整数
定理１
式(3.2)が(n, d)グラフを構成するのは、a*dとnの最大公約数がｄの約数のときである。
例
n = 6, d = 2, a = b = 1 => (n, d)グラフを構成できる
i = 0の時
j = (1 * 0 + 1) * 2 + 0 ≡ 2 (mod 6)
= (1 * 0 + 1) * 2 + 1 ≡ 3 (mod 6)
i = 1の時, j = 4, 5
i = 2の時, j = 0, 1
i = 3の時, j = 2, 3
i = 4の時, j = 4, 5
i = 5の時, j = 0, 1
これらのiとjは、iからjに枝が伸びている事を表す。
有向線形構成法 Effective Linear Design Method
定義
1 = ± 1 の場合の線形構成法
定理２
有向線形構成された(n, d)グラフの直径は、「log_d n」を超えない。
定理２と式(3.1)より有向形成された(n, d)グラフの直径は最適解と等しいか１大きい。
湖の大きさを列挙する
問題
{
{0, 2, 1, 0},
{0, 1, 0, 1},
{1, 1, 0, 1},
{0, 1, 0, 1}
}
が与えられる。0の部分が湖で、縦横斜めで０が連なっている所は同じ湖とする。全ての湖のサイズを列挙する問題。
