资源描述：
《图形G是由两个集合V和E所构成的.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、GraphAlgorithms圖形G是由兩個集合V和E所構成的，可以寫成G=(V,E)。其中V是非空的由有限個頂點(Vertex)所構成的集合，E則是由頂點對所構成的集合，這些頂點對叫做邊(edge)。V(G)和E(G)各表示組成G的頂點集合和邊集合。依據E中邊之型態，所組成之圖形又可分成下列兩種：E中之邊沒有方向性，亦即（Ｖ1,Ｖ2）和（Ｖ2,Ｖ1）表示相同的邊，如此構成之圖形稱作無向圖形（undirectedgraph）。E之邊沒有方向性，頂點對（邊）以＜Ｖ1,Ｖ2＞表示，其中Ｖ２表頭（head），Ｖ1表尾（tail）；很自然地，＜Ｖ2,Ｖ1＞和，＜Ｖ1,Ｖ2＞是完全不同的兩個邊
2、。以此種邊集合構成之圖形稱作有向圖形（directedgraph，又稱digraph）。completegraph：各種頂點的組合均存在之圖形稱作completegraph。無向圖形若有n個頂點，則最大可能之邊組合有（）＝ 種，而有向圖形將有兩倍於此為n(n-1)種組合；含有n個頂點之completegraph將有如上數目之邊。subgraph：若Ĝ為Ｇ之subgraph，則Ĝ為一graph，且Ｖ(Ĝ)＜V(V)，E(G)＜E(G)。path：由圖形中頂點所構成的序列Ｖp,Ｖ1,Ｖ2,…ＶN,Ｖq，若其中(Ｖp,Ｖ1),(Ｖ1,Ｖ2),…，(ＶN,Ｖq)均為圖形中之邊，則此序列
3、稱做一path；一path中edge之數目稱做該path之長度；在有向圖形之情況下，則要求＜Ｖp,Ｖ1＞,＜Ｖ1,Ｖ2＞,…，＜ＶN,Ｖq＞均為有向edge，而此path又稱做directedpath。Simplepath：在上面之定義中，其除了Ｖp和Ｖq之外，其他vertex均不重複出現的path稱之。在simplepath中，若Ｖp=Ｖq，則稱之為cycle或circuit。一graph若有cycle則稱cyclic，反之則可稱做acyclic。一path若不為simple，則其必有相交之情況。頂點和邊之關係,以“adjacent”和“incident”描述之：Ｖ1Ｖ2Ｖ1Ｖ2Ｅ
4、1Ｅ2(有向)(無向)Ｖ1和Ｖ2為adjacentＶ1adjacentfromＶ2Ｅ1incidentonＶ1(Ｖ2)Ｖ2adjacenttoＶ1Ｅ2incidenttoＶ1(Ｖ2)相連（Connected）connectedoftwovertices：若一圖形中之兩頂點間存在任何path，則稱他們為connected的。在有向圖形中，若兩點頂間存在自其中某頂點到另一頂點和回來之有向path，則稱此兩頂點為stronglyconnected。connectedofagraph：若一圖形其所有頂點對均為6connected，則此graph為connected：相似地，若一有向圖形所有頂
5、點對間均為stronglyconnected，該圖形亦為stronglyconnected。degree(ofavertex)：表示一個vertex所adjacent之其他vertices之個數。在有向圖形中，degree又分成in-degree和out-degree，其中前者表示該vertex所adjacentfrom之vertex個數，而後者表示所adjacentto之vertex個數。connectedcomponent：對無向圖形而言，其connectedcomponent（或component）表示其孤立的connected的子圖，這可能有好幾個。在有向圖形中，strong
6、lyconnectedcomponent表示一盡量伸展而仍然保持stronglyconnected的子圖（不一定要孤立）。以下四個圖形G1到G4前三個均只有一個component（G3沒有stronglyconnectedcomponent），而G4有兩個component。1234G11237654G2213▼▲G31324G4H15678H21423路徑長度為n之鄰接矩陣在找出路徑矩陣p時，首先要找到a2，然後a3，一直到an，最後再將a1，a2，…，an加起來得到Sn，再由Sn得到p。Warshall’salgorithm:1. p←a（把鄰接矩陣a拷貝至p）2.
7、 for（k=1；k<=n；k++）for（i=1；i<=n；i++）for（j=1；j<=n；j++）p[i][j]=p[i][j]
8、p[i][k]&p[k][j]；Warshall’salgorithmRepresentationsofgraphs：undirectedgraphAnundirectedgraphGhavefiveverticesandsevenedgesAnadjacency-listrepresentationofGTheadja
