第四部分 圖[2]

    無向完全圖在無向圖中如果任意兩個頂點之間都存在邊則稱該圖為無向完全圖【釋無箭頭】
　　
　　有向完全圖在有向圖中如果任意兩個頂點之間都存在方向相反的兩條弧則稱該圖為有向完全圖【釋有箭頭】
　　
　　稀疏圖稱邊數很少的圖為稀疏圖稠密圖稱邊數很多的圖為稠密圖
　　
　　頂點的度在無向圖中頂點v的度是指依附於該頂點的邊數【釋邊數】
　　
　　頂點的入度在有向圖中頂點v的入度是指以該頂點為弧頭的弧的數目記為ID（v）【釋進來的邊數】
　　
　　頂點的出度在有向圖中頂點v的出度是指以該頂點為弧尾的弧的數目記為OD（v）【釋出去的邊數】
　　
　　權是指對邊賦予的有意義的數值量【釋邊上的值】
　　
　　網邊上帶權的圖也稱網圖
　　
　　路徑在無向圖G=（VE）中從頂點vp到頂點vq之間的路徑是一個頂點序列（vp=vivivi…vim=vq）其中（vijvij）∈E（≤j≤m）若G是有向圖則路徑也是有方向的頂點序列滿足<vijvij>∈E【釋能走過去就是有路徑】
　　
　　路徑長度
　　非帶權圖——路徑上邊的個數
　　帶權圖——路徑上各邊的權之和
　　
　　回路（環）第一個頂點和最後一個頂點相同的路徑
　　
　　簡單路徑序列中頂點不重復出現的路徑
　　
　　簡單回路（簡單環）除了第一個頂點和最後一個頂點外其余頂點不重復出現的回路【釋無環】

    返回《數據結構》考研復習精編

[]  []  []  []  []  []  []  []  []  []  

From:http://tw.wingwit.com/Article/program/sjjg/201311/23288.html