Parallel-algorithm-graph-algorithm
グラフアルゴリズム
グラフは、オブジェクトのペア間の接続を表すために使用される抽象的な表記です。 グラフはで構成されます-
- 頂点-グラフ内の相互接続されたオブジェクトは頂点と呼ばれます。 頂点は*ノード*とも呼ばれます。
- エッジ-エッジは、頂点を接続するリンクです。
グラフには2種類あります-
- 有向グラフ-有向グラフでは、エッジには方向があります。つまり、エッジはある頂点から別の頂点に移動します。
- 無向グラフ-無向グラフでは、エッジには方向がありません。
グラフの色付け
グラフの色付けは、隣接する2つの頂点が同じ色にならないように、グラフの頂点に色を割り当てる方法です。 いくつかのグラフの色の問題は-
- 頂点カラーリング-隣接する2つの頂点が同じ色を共有しないようにグラフの頂点をカラーリングする方法。
- Edge Coloring -2つの隣接するエッジが同じ色を持たないように、各エッジに色を割り当てる方法です。
- 顔の色-平面グラフの各面または領域に色を割り当て、共通の境界を共有する2つの面が同じ色を持たないようにします。
色数
色数は、グラフの色に必要な色の最小数です。 たとえば、次のグラフの色数は3です。
グラフの色付けの概念は、時刻表、モバイル無線周波数の割り当て、Suduku、レジスタ割り当て、およびマップの色付けの準備に適用されます。
グラフの色付けの手順
- n次元配列の各プロセッサーの初期値を1に設定します。
- 次に、特定の色を頂点に割り当てるには、その色が既に隣接する頂点に割り当てられているかどうかを判断します。
- プロセッサが隣接する頂点で同じ色を検出した場合、配列の値を0に設定します。
- n ^ 2 ^比較を行った後、配列の要素が1である場合、それは有効なカラーリングです。
グラフの色付けのための擬似コード
begin
create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
status[i0,..in-1] = 1
for j varies from 0 to n-1 do
begin
for k varies from 0 to n-1 do
begin
if aj,k=1 and ij=ikthen
status[i0,..in-1] =0
end
end
ok = ΣStatus
if ok > 0, then display valid coloring exists
else
display invalid coloring
end最小スパニングツリー
すべてのエッジの重み（または長さ）の合計がグラフGの他のすべての可能なスパニングツリーよりも小さいスパニングツリーは、*最小スパニングツリー*または*最小コストスパニング*ツリーとして知られています。 次の図は、重み付き連結グラフを示しています。
上記のグラフのいくつかの可能なスパニングツリーは以下に示されています-
Spanning Tree Spanning Tree 1 Spanning Tree 2 Minimum Spanning Tree Spanning Tree 3 Spanning Tree 4 スパニングツリー5
上記のすべてのスパニングツリーの中で、図（d）は最小スパニングツリーです。 最小コストスパニングツリーの概念は、巡回セールスマン問題、電子回路の設計、効率的なネットワークの設計、効率的なルーティングアルゴリズムの設計に適用されます。
最小コストスパンニングツリーを実装するには、次の2つの方法が使用されます-
- プリムのアルゴリズム
- クラスカルのアルゴリズム
プリムのアルゴリズム
プリムのアルゴリズムは貪欲なアルゴリズムであり、重み付き無向グラフの最小スパニングツリーを見つけるのに役立ちます。 最初に頂点を選択し、その頂点に最小の重みを持つエッジを見つけます。
プリムのアルゴリズムの手順
- グラフGのv〜1〜などの頂点を選択します。
- エッジを選択します。たとえば、Gのe〜1〜は、e〜1〜= v〜1〜v〜2〜およびv〜1〜≠v〜2〜であり、e〜1〜はvに入射するエッジの中で最小の重みを持ちます。グラフGの〜1〜
- ここで、ステップ2に続いて、v〜2〜の最小加重エッジインシデントを選択します。
- n–1個のエッジが選択されるまでこれを続けます。 ここで、 n は頂点の数です。
最小スパニングツリーは-
Prim’s Algorithm Minimum Spanning Tree
クラスカルのアルゴリズム
Kruskalのアルゴリズムは貪欲なアルゴリズムであり、接続された重み付きグラフの最小スパニングツリーを見つけるのに役立ち、各ステップでコストアークが増加します。 これは、フォレスト内の2つのツリーを接続する最小の重みのエッジを見つける最小スパンニングツリーアルゴリズムです。
クラスカルのアルゴリズムの手順
- 最小重量のエッジを選択します。 Graph Gのe〜1〜とe〜1〜はループではないとします。
- e〜1〜に接続されている次の最小重み付きエッジを選択します。
- n–1個のエッジが選択されるまでこれを続けます。 ここで、 n は頂点の数です。
上記のグラフの最小全域木は-
最短経路アルゴリズム
最短パスアルゴリズムは、ソースノード（S）から宛先ノード（D）への最小コストパスを見つける方法です。 ここでは、Breadth First Search Algorithmとしても知られるMooreのアルゴリズムについて説明します。
ムーアのアルゴリズム
- ソース頂点Sにラベルを付け、 i にラベルを付け、 i = 0 に設定します。
- i というラベルの付いた頂点に隣接するラベルのないすべての頂点を見つけます。 頂点Sに頂点が接続されていない場合、頂点DはSに接続されません。 Sに接続されている頂点がある場合、それらに i + 1 というラベルを付けます。
- Dにラベルが付いている場合は、ステップ4に進み、そうでない場合は、ステップ2に進んでi = i + 1を増やします。
- 最短パスの長さが見つかったら停止します。
