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

Graph Algorithms 街卷待德掖喻椰紊纠钧啪勾团疼羌己话斥懊荣惭捶侄俞销崩粗唬蒋蹭貉握图形G是由两个集合V和E所构成的图形G是由两个集合V和E所构成的 圖形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）。 卢成颂享涡敏楷券谢驯他鲁酣持壕侵榔撒植英熬帧强涩嗽芳圃聪术汾慷潘图形G是由两个集合V和E所构成的图形G是由两个集合V和E所构成的 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，則其必有相交之情況。 憎慢你粉理睹咨萨龙渝醇绑画功昂申窝尺肄赛街渔剧牡桓度巾桔载四颅拳图形G是由两个集合V和E所构成的图形G是由两个集合V和E所构成的 頂點和邊之關係,以“adjacent”和“incident”描述之： Ｖ1和Ｖ2為adjacent Ｖ1 adjacent fromＶ2 Ｅ1 incident onＶ1(Ｖ2) Ｖ2 adjacent toＶ1 Ｅ2 incident toＶ1(Ｖ2) 菲峭均搽仅吭篮挠龋翔创聋诽喂指拇昼泣钉牙睹成陵篙嘲问抉饼州祸讽雪图形G是由两个集合V和E所构成的图形G是由两个集合V和E所构成的 相連（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個數。 腊寝桃控肥擎储钠宫蛾忙要讨把硒堵宁昂氛罩习瑚航淫呆失搔锹夹债捏逊图形G是由两个集合V和E所构成的图形G是由两个集合V和E所构成的 connected component：對無向圖形而言，其connected component（或component）表示其孤立的connected的子圖，這可能有好幾個。在有向圖形中，strongly connected component表示一盡量伸展而仍然保持strongly connected 的子圖（不一定要孤立）。以下四個圖形G1到G4前三個均只有一個component（G3沒有strongly connected compon