【圖】

圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G=(V,E)，其中 V 是非空有限集合，?代表頂點，E 是可以為空的有限集合，代表邊。

若頂點 vi 和 vj 間的邊沒有方向，則稱這條邊為無向邊，用無序偶對 (vi,vj) 表示；若頂點 vi 和 vj 間的邊有方向，則稱這條邊為有向邊（弧），用有序偶對 <vi,vj>?表示，其中 vi 稱為弧頭，vj 稱為弧尾。

若圖的任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖；若圖的任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖。

?

【基本術語】

• 在一個圖中，不存在頂點到其自身的邊，且同一條邊不重復出現，則稱圖為簡單圖
• 在一個無向圖中，對于任意兩個頂點 vi 和頂點 vj，若存在邊 (vi,vj)，則稱頂點 vi 和頂點 vj 互為鄰接點，同時稱邊 (vi,vj) 依附于頂點 vi 和頂點 vj
• 在一個有向圖中，對于任意兩個頂點 vi 和頂點 vj，若存在弧 <vi,vj>，則稱頂點 vi 鄰接到頂點 vj，頂點 vj 鄰接自頂點 vi，同時稱弧 <vi,vj> 依附于頂點 vi 和頂點 vj
• 在一個無向圖中，如果任意兩個頂點之間都存在邊，則稱該圖為無向完全圖，其有 n*(n-1)/2 條邊
• 在一個有向圖中，如果任意兩個頂點之間都存在方向相反的兩條弧，則稱該圖為有向完全圖，其有 n*(n-1) 條邊。?
• 一個邊數接近完全圖的圖稱為稠密圖，一個邊數遠遠少于完全圖的圖稱為稀疏圖
• 在無向圖中，依附于頂點 v 的邊數稱為頂點的度，記為 TD(v)，在 n 個頂點 m 條邊的無向圖中，所有點的度的和為 2m
• 在有向圖中，以頂點 v 為弧頭的弧的數目稱為頂點的入度，記為 ID(v)，在 n 個頂點 m 條邊的有向圖中，所有點的入度和為 m
• 在有向圖中，以頂點 v 為弧尾的弧的數目稱為頂點的出度，記為 OD(v)，在 n 個頂點 m 條邊的有向圖中，所有點的出度和為 m
• 對邊賦予的有意義的數值量稱為權（權值），邊上帶權的圖，稱為網（帶權圖），根據圖是無向圖或有向圖，分為有向網圖、無向網圖
• 在無向圖 G=(V,E) 中，對于一個滿足? 的頂點序列 ，稱為從頂點 vp 到頂點 vq 之間的路徑，若?G 是有向圖，則 G 的路徑是有方向的
• 在路徑序列中，起點和終點相同的路徑稱為回路（環）
• 在路徑序列中，頂點不重復出現的路徑稱為簡單路徑
• 在路徑序列中，除起點終點外，其余頂點不重復出現的回路稱為簡單回路
• 對于一個非帶權圖，路徑上邊的個數稱為路徑長度，對于一個帶權圖，路徑上各邊權的和稱為路徑長度
• 對于圖 G=(V,E) 和 G'=(V',E')，若?，則稱 G' 為 G 的子圖，一個圖可以有多個子圖
• 在無向圖中，如果從一個頂點 vi 到另一個頂點 vj(i≠j) 有路徑，則稱頂點 vi?和 vj 是連通的，如果圖中任意兩個頂點都是連通的，則稱該圖是連通圖
• 非連通圖的極大連通子圖稱為連通分量，其中，極大是指包括所有連通的頂點及這些頂點相關聯的所有邊
• 在有向圖中，對圖中任意一對頂點 vi 和 vj(i≠j)，若從頂點 vi 到頂點 vj 和從頂點 vj 到頂點 vi 均有路徑，則稱該有向圖是強連通圖，非強連通圖的極大強連通子圖稱為強連通分量
• 對于一個具有 n 個頂點的連通圖 G ，包含 G 中全部頂點的一個極小連通子圖稱為生成樹，其中，極小是指子圖中只有一個入度為 0 的點且其他點的入度均為 1
• 在非連通圖中，由每個連通分量都可以得到一棵生成樹，這些連通分量的生成樹就組成了一個非連通圖的生成森林

【圖的存儲結構】

圖的存儲結構分為鄰接矩陣、鄰接表、鏈式向前星、十字鏈表、鄰接多重表等，這些存儲結構各有優劣，應根據實際情況進行選用，具體內容：點擊這里

總結

以上是生活随笔為你收集整理的理论基础 —— 图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。