圖(Graph)

第 11 屆 iThome 鐵人賽

DAY 20

自我挑戰組

11th鐵人賽

1250 瀏覽

點(node)：圖形中的點，上圖中有點1、點2、點3、點4與點5。。
邊(edge)：兩個點之間可以有邊相連，上圖中的邊有(1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(2,5)六個邊。
路徑(path)：兩點之間可以由許多邊連接起來，上圖中的點1與點4的連接，可以由點1連接到點3的邊(1,3)，點3再連接到點2的邊(3,2)，點2再連接到點4的邊(2,4)，這樣就是一個連接點1到點4的路徑。
路徑長度(path length)：一個路徑所包含的邊的個數。
簡單路徑(simple path)：一個路徑的起點與終點外，其餘點都不能相同。
循環(cycle)：是簡單路徑，且路徑的起點與終點相同。
子圖(subgraph)：G2是G1的子圖，G2的出現過的點與邊，G1也有相同的點與邊。
若圖的邊有方向性稱有向圖，反之則稱無向圖。