図論総説

図の記憶

図通はG=(V,E)で表されることが多い.Vは頂点(vertex)集合,Eはエッジ(Edge)集合である.
図の物理記憶には、2つの方法があります.
1.隣接行列は、2次元配列であり、直感的であるが、重辺を格納することはできない.
2.チェーンと順序付けされたストレージである隣接テーブル.

//  
#include
#include
#define M 100
using namespace std;
struct edge{
	int v;
	int distance;
	int cost;
};

void adjacency_table(){//  
	// 3  5 ， 6， 7， ：
	vector  graph[M];
    edge t;
	t.v=5;t.distance=6;t.cost=7;
    graph[3].push_back(t); 
}

void adjacency_matrix(){// 
	edge graph2[M][M];
	edge t;t.distance=6;t.cost=7;
	graph2[3][5]=t;
}

n個の頂点の連通図には少なくとも何個のエッジがありますか?
答え:少なくとも(n-1)辺が必要です.単純な図ではn*(n-1)/2辺まで多く、この場合は完全図である.

図の遍歴

深度の優先順位:
1.図中のある頂点vから出発して、その頂点にアクセスし、その後、その未アクセスの隣接頂点を順に深さ優先的に巡回する.これにより、vに接続された頂点がアクセスされます.
2.図にアクセスされていない頂点がある場合は、すべての頂点がアクセスされるまで、それらの深さを遍歴します.
優先度:
1.図中のある頂点vから出発し、その頂点をキューqueueに入れる.
2.キューqueueから頂点xを取り出し、その頂点にアクセスし、xに隣接するすべての頂点をキューに入れます.
3.すべての頂点がアクセスされるまで手順2を繰り返します.

二部図

二部図:図Gの頂点を二つの集合AとBに分割し、図中のいずれかの辺の二つの隣接頂点が異なる頂点セットに属するようにする分割方法がある.
一致:2つの図に共通の頂点がないエッジセット.エッジ数が最も多いマッチングを最大マッチングと呼びます.図の各頂点が一致するエッジに隣接している場合は、完全一致と呼ばれます.
[キャップされていないポイント]:一致するエッジに隣接しない頂点.
拡張路:非整合エッジ、整合エッジ、非整合エッジ......交互に行い、最終的には未蓋点で終わり、この経路を拡張路と呼ぶ.拡張路では、元のマッチングエッジを非マッチングエッジと置き換えると、元の複数のエッジよりも新しいマッチングが得られる.
ハンガリーアルゴリズム:拡大の道を探し続け、最終的に最大のマッチングを得た.
2部図の最小オーバーライド:図の各エッジに少なくとも1つの端点が選択されるように、できるだけ少ない点を選択します.最小オーバーライド数=最大一致数であることが証明されます.
2部図の独立セット:このセットの任意の2点が隣接していない.独立セット頂点の数=合計頂点数-最大一致するエッジの数.
一つの図Gは、その頂点セットVが、異なる集合の任意の2点が隣接するように交差しない3つの集合V 1,V 2,V 3に分割されているが、同一集合内の任意の2点が隣接していない場合、Gを完全3部図と呼ぶ.

ネットワーク・フロー-コンセプト

容量ネットワーク(capacity network):G(V,A)を有向ネットワークとし、Vにソースポイント(Vsと記す)と別の頂点を指定し、集約ポイント(Vtと記す)と呼ぶ.各アーク∈Aに対して、アークの容量(capacity)と呼ばれる重みc(u,v)>0が対応する.このような有向ネットワークGを一般に容量ネットワークと呼ぶ.ソースポイントから集約ポイントへの最大実行可能なストリームを最大ストリームと呼びます.
可行ストリーム(Valid Flow):可行ストリームf(u,v)は、頂点uから頂点vへの流量を表す.
前方円弧:元の図の円弧.
逆円弧:順方向円弧を反転します.
増広路(augmenting path):
fは1つの容量ネットワークGの中の1つの実行可能なストリームであり、PはVsからVtまでの1つの経路であり、Pが以下の条件を満たすとする.
1)Pの全ての順方向アークにおいて,0≦f(u,v)
2)Pのすべての後方アーク上で,0
Pを可行流fに関する増幅路と呼び、単に増幅路と呼ぶ.
拡張-拡張路に沿って実行可能なストリームを改善する動作を拡張(augmenting)と呼ぶ.
増幅路P上の全てのアーク上の流量は以下の規則に従って変化する:(常に実行可能な流れの2つの条件を満たす)
a)前方アーク上で、f(u,v)=f(u,v)+x;
b)後方アーク上でf(u,v)=f(u,v)−x.
xは、各前方アーク上のc(u,v)−f(u,v)と各後方アーク上のf(u,v)の最小値に等しいはずである.次のようになります.
x=min{ min{c(u,v)-f(u,v)}, min{f(u,v)}}.
 
さいしょうわりこみさいだいりゅう
割——図G=(V,E)に対して,頂点集合VをSとTに分割する.ここで,ソース点s∈S,合流点t∈T,T=V−Sである.(S,T)を1割と呼ぶ.割の容量はcapacity(S,T)=Σcapacity(u,v)と定義され,ここでu∈S,v∈Tである.
任意のs−tストリームf、および任意のs−tカット(S,T)に対して、|f|<=capacity(S,T)がある.なぜなら、ストリームfは必ずカット中のいくつかのエッジを越えるからである.
最後の増幅路が見つかって次のBFSで新しい増幅路が見つからない場合,符号化された点を集合S(いずれの点vに対してもa[v]>0)と見なし,V−SをTと見なし,このときの割が最小割である.
 
最小費用最大フロー
 

最小生成ツリー

1つの図の連通成分は、この図の極大連通サブ図である.一方、1つの連通図の生成ツリーは、極小連通サブ図である.エッジに重みを付与すると,最小生成ツリーは重みと最小生成ツリーであり,アルゴリズムにはPrimeとKruskalがある.原図はG=(V,E);生成ツリーG 1=(V 1,E 1)を生成する.
Prime:
1.初期化、V 1、E 1はすべて空であり、任意のvをV 1に加える.
2.最小重み値を有する辺(u,v)を求め、uはV 1に属し、vはV−V 1に属する.vをV 1に加え、この辺をE 1に加える.
3.V 1=Vになるまで手順2を繰り返します.
複雑度はO(n*n)である.
Kruskal:
1.エッジを小さい順に並べ替えます.V 1=Vにする.
2.各辺edge[i]を順に遍歴し、この辺G 1にループがあれば捨て、そうでなければE 1を加える.
複雑度はO(辺数)である.

最短パス

原図はG=(V,E)で,sから任意の頂点への最短経路を求める.補助配列dist[i]は、現在ソース点sから頂点iまでの最短経路を表し、補助配列visited[]は集合Aを表す.
1.初期化、dist[i]=graph[s][i]、Aにはs点のみを置く.
2.最小値を持つdist[x]を見つけ、xはV-Aに属する.xはAを加え,すべてのdist[y]を更新し,yはV−Aに属する.更新ステップif(dist[x]+graph[x][y]
3.V=Aになるまで手順2を繰り返します.

トポロジのソート

は、G内のすべての頂点を線形シーケンスに並べて、図中の任意のアーク(u,v)、頂点uが頂点vの前になるように、有方向無ループ図(Directed Acyclic Graph略称DAG)Gをトポロジーソートする.
基本思想を見てください.
1.すべての頂点の入力を統計します.頂点xの入度は、弧の終点が頂点xを指す弧の本数である.
2.入力度0の頂点xを探し、線形シーケンスに入れ、その点を図から削除します.
3.すべての頂点が出力されるまで、手順2を繰り返します.頂点が完全に出力されていないのに0の頂点が見つからない場合は、この図にループがあり、ソートに失敗していることを示します.