圖的知識點大全

1~圖的基本概念

有向圖

若E是有向邊（簡稱弧）的有限集合時，則G為有向圖，弧是頂點的有序對，記為<v,w>，
其中 v，w 是頂點，v 是弧尾，w 是弧頭，稱為從頂點v到頂點w的弧，

有向圖

無向圖

若E是無向邊（簡稱邊）的有限集合時，則G為無向圖，邊是頂點的無序對，記為 (v,w) 或(w,v) ，
且有 (v,w) =(w,v) ，其中 v，w 是頂點，

無向圖

簡單圖

簡單圖滿足以下兩條內容：'①不存在重復邊'   '②不存在頂點到自身的邊'   則稱為'簡單圖'
   .

完全圖

無向圖中任意兩個頂點之間都存在邊【n(n-1)/2】，稱為'無向完全圖'
有向圖中任意兩個頂點之間都存在方向向反的兩潭訓【n(n-1)】，稱為'有向完全圖'

連通、連通圖、連通分量

在無向圖中，兩頂點有路徑存在，就稱為'連通的'，
若圖中任意兩頂點都連通，同此圖為'連通圖'，
無向圖中的極大連通子圖稱為'連通分量'，
'極大連通子圖'是'無向圖'的連通分量，'極大'-->要求該連通子圖包含其所有的邊，
'極小連通子圖'是既要保持圖的連通又要使得邊數'最少'的子圖，

強連通

在有向圖中，兩頂點'兩個方向'都有路徑，兩頂點稱為強連通，若任一頂點都是強連通的，稱為'強連通'，
有向圖中極大強連通子圖為有向圖的強連通分量，

生成樹和生成森林

連通圖的生成樹是包含圖中全部頂點的一個極小連通子圖，若圖中有n個頂點，則生成樹有'n-1條邊'，
所以對于生成樹而言，若砍去一條邊，就會變成'非連通圖'，

頂點的度、入度和出度

'無向圖'，頂點的邊數為度，度數之和是'頂點邊數的2倍'
'有向圖'，入度是以頂點為終點，出度相反，有向圖的全部頂點'入度之和'等于'出度之和'且等于'邊數'，
頂點的度等于入度與出度之和，

簡單路徑、簡單回路

在路徑序列中 頂點'不重復出現'的路徑稱為簡單路徑，
'除第一個頂點和最后一個頂點外'，其余頂點不重復出現的回路稱為簡單回路，

由于時間有限，寫的不好請見諒，理解萬歲(:

以上圖片均來自王道資料結構書中

僅為個人復習方便所寫，如有侵權立即洗掉！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/146906.html

標籤：Java