Team TripleFalcon. http://www.triplefalcon.com/

概要

 離散数学で最もポピュラーな分野でしょう。数学よりの一般書にはグラフ上の証明や定理が面白く紹介されていることが多いです。また、電気回路のモデルなども与えてくれます。

 巡回セールスマン問題、最小木問題、スタイナ木問題、等は、理論上の難問でもあり、ほとんどそのまま工学上の応用分野で高速な解法が望まれているものでもあります。これほど数学と応用が直結している例は少ないと思われます。

 グラフは、頂点の集合 V(有限集合)と頂点の対 E(V上の対)の組 G=(V,E) のことを言います。

Team TripleFalcon. http://www.triplefalcon.com/

定義

  有限集合 V とV上の2項関係を E(⊂V×V) とします。(参照→集合,関係) VとEの組を有向グラフ(directed graph) と呼びます。

定義1) G=(V,E) が有向グラフ
def
V が有限集合 ,E⊂V×V

 このとき、有限集合 V を頂点(vertex) と呼び、V上の2項関係 E を辺(edge) と呼びます。辺が、非順序対である場合は無向グラフ(undirected graph) と呼びます。

定義2) G=(V,E) が無向グラフ
def
V が有限集合 ,E⊂{ {x,y} | x,y∈V }

 上記定義の他に、無向グラフ(undirected graph) の定義を「 Eが対称的関係であるような有向グラフ」と定義している文献も多いです。本用語集ではどちらの定義も同一視し、都合よくどちらも使うことにします。

 ところで、頂点を V= {1,2,3, ... ,n} としている文献もあります。プログラミングでは、頂点を自然数とするのが一番自然な実装と思います。

 有向グラフ無向グラフを総称して単にグラフ(graph) と呼ぶことがあります。 有向グラフの辺を有向辺、無向グラフの辺を無向辺といいます。

 頂点 a,b 間に辺が存在する場合、隣接する(adjacent) といいます。

 頂点の次数(degree)は、その頂点に接続する辺の数です。有向辺の場合は、頂点に入ってくる辺の数として入次数(in-degree)と出て行く辺の数として出次数(out-degree) に区別することが多いです。

Team TripleFalcon. http://www.triplefalcon.com/

完全グラフ

 全ての頂点間に辺があるグラフを完全グラフ(complete graph) といいます。

定義3)

グラフ G=(V,E) が 
完全有向グラフ 
def


 任意の2頂点 x,y∈V 間
 に必ず辺が存在し、
 辺が (x,y) か (y,x) 
 のどちらか1個である
定義4)

グラフ G=(V,E) が 
完全無向グラフ 
def

 E={ {x,y} | x,y∈V }

 辺の数は正確に頂点の数 n の二乗 n2 になります。

Team TripleFalcon. http://www.triplefalcon.com/

重み付きグラフ

 グラフ G の頂点や辺に実数等が割り当てられる場合、重み付きグラフ(weighted graph) とかラベル付きグラフ(labeled graph) と呼びます。重みは、実数の場合もあり、また文字や文字列であることもあります。重み関数は頂点と辺の両方につけることも在ります。

 G=(V,E) をグラフとし、辺から実数への関数 w:E→R や頂点から文字列への関数 g:V→Σ*などが定義されているとします。

表記)

G=(V,E,w) とか G=(V,E,w,g) 等・・・重み付きグラフ

 頂点をに名称を定義したり、道に長さやコストなどを与えることができる様になります。

Team TripleFalcon. http://www.triplefalcon.com/

道(path)

 有向グラフ G=(V,E) から取り出した辺の列 e1,e2,e3, ... ,ek∈E が全ての i (1≦i≦k-1) について以下が成り立つとき道(path) といいます。無向グラフでも定義できます。

 (道と呼んでいるのは聞いたことがなく、日本語でもパスと呼ぶほうが多いです。)

定義5)

有向辺列が道である 
e1,e2,e3, ... ,ek 
def

 ∀i (1≦i<k) ei=(ui,vi)
 vi=ui+1
定義6)

無向辺列が道である 
e1,e2,e3, ... ,ek 
def

 ∀i (1≦i<k) ei∩ei+1≠φ 
              

 同じ辺を含まない道を単純(simple) といい、同じ頂点を含まない道を要素的(elementary) とか初等といいます。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

グラフ(graph)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール