图形G是由两集合V和E所构成的.ppt

圖形G是由兩個集合V和E所構成的，可以寫成G=(V,E)。其中V是非空的由有限個頂點(Vertex)所構成的集合，E則是由頂點對所構成的集合，這些頂點對叫做邊(edge)。V(G)和E(G)各表示組成G的頂點集合和邊集合。依據E中邊之型態，所組成之圖形又可分成下列兩種： E中之邊沒有方向性，亦即（Ｖ1,Ｖ2）和（Ｖ2,Ｖ1）表示相同的邊，如此構成之圖形稱作無向圖形（undirected graph）。 E之邊沒有方向性，頂點對（邊）以＜Ｖ1,Ｖ2＞表示，其中Ｖ２表頭（head），Ｖ1表尾（tail）；很自然地，＜Ｖ2,Ｖ1＞和，＜Ｖ1,Ｖ2＞是完全不同的兩個邊。以此種邊集合構成之圖形稱作有向圖形（directed graph，又稱digraph）。 complete graph：各種頂點的組合均存在之圖形稱作complete graph。無向圖形若有n個頂點，則最大可能之邊組合有（）＝　　　　種，而有向圖形將有兩倍於此為n(n-1)種組合；含有n個頂點之complete graph將有如上數目之邊。 subgraph：若?為Ｇ之subgraph，則?為一graph，且Ｖ(?)＜V(V)，E(G)＜E(G)。 path：由圖形中頂點所構成的序列Ｖp,Ｖ1,Ｖ2,…ＶN,Ｖq，若其中(Ｖp,Ｖ1), (Ｖ1,Ｖ2),…，(ＶN,Ｖq)均為圖形中之邊，則此序列稱做一path；一path中edge之數目稱做該path之長度；在有向圖形之情況下，則要求＜Ｖp,Ｖ1＞, ＜Ｖ1,Ｖ2＞,…，＜ＶN,Ｖq＞均為有向edge，而此path又稱做directed path。 Simple path：在上面之定義中，其除了Ｖp和Ｖq之外，其他vertex均不重複出現的path稱之。在simple path中，若Ｖp=Ｖq，則稱之為cycle或circuit。一graph若有cycle則稱cyclic，反之則可稱做acyclic。 一path若不為simple，則其必有相交之情況。 頂點和邊之關係,以“adjacent”和“incident”描述之： 相連（Connected） connected of two vertices：若一圖形中之兩頂點間存在任何path，則稱他們為connected的。在有向圖形中，若兩點頂間存在自其中某頂點到另一頂點和回來之有向path，則稱此兩頂點為strongly connected。 connected of a graph：若一圖形其所有頂點對均為6 connected，則此graph為connected：相似地，若一有向圖形所有頂點對間均為strongly connected，該圖形亦為strongly connected。 degree (of a vertex)：表示一個vertex所adjacent之其他vertices之個數。在有向圖形中，degree又分成in-degree和out-degree，其中前者表示該vertex所adjacent from之vertex個數，而後者表示所adjacent to之vertex個數。 connected component：對無向圖形而言，其connected component（或component）表示其孤立的connected的子圖，這可能有好幾個。在有向圖形中，strongly connected component表示一盡量伸展而仍然保持strongly connected 的子圖（不一定要孤立）。以下四個圖形G1到G4前三個均只有一個component（G3沒有strongly connected component），而G4有兩個component。 Representations of graphs：undirected graph An undirected graph G have five vertices and seven edges An adjacency-list representation of G The adjacency-matrix representation of G Representations of graphs：directed graph An directed graph G have six vertices and eight edges An adjacency-list representation of G The adjacency-matrix representation of G The operation of BFS on an undirected graph Breadth-first sea