總度數(D)等於邊數(e)的兩倍。D=2e圖G的頂點數n和邊數e的關係1、若G是無向圖，則0≤e≤n(n-1)/2。恰有n(n-1)/2條邊的無向圖稱無向完全圖(Undireet-edCompleteGraph)。2、若G是有向圖，則0≤e≤n(n-1)。恰有n(n-1)條邊的有向圖稱為有向完全圖(DirectedCompleteGraph)。對於有向圖最短路問題，計算步驟與求解無向圖最短路問題相同，主要區別在於：無向圖最短路問題使用單標號法。單標號法是對每一點賦予一個路權標號；而有向最短路問題使用雙標號法．雙標號法是對每一點賦予兩個標號：路徑和路權。擴充套件資料對於有向圖，情形就不同了，因為存在從u到v的路徑，並不蘊涵也存在從v到u的路徑。設D是一個有向圖，且u、v∈D，若存在從頂點u到頂點v的一條路徑，則稱從頂點v到頂點u可達。可達的慨念與從u到v的各種路徑的數目及路徑的長度無關。另外，為了完備起見，規定任一頂點到達它自身的是可達的。可達性是一個有向圖頂點的二元關係，依照定義，它是自反的，且是傳遞的。一般來說，可達不是對稱的，也不是反對稱的。
總度數(D)等於邊數(e)的兩倍。D=2e圖G的頂點數n和邊數e的關係1、若G是無向圖，則0≤e≤n(n-1)/2。恰有n(n-1)/2條邊的無向圖稱無向完全圖(Undireet-edCompleteGraph)。2、若G是有向圖，則0≤e≤n(n-1)。恰有n(n-1)條邊的有向圖稱為有向完全圖(DirectedCompleteGraph)。對於有向圖最短路問題，計算步驟與求解無向圖最短路問題相同，主要區別在於：無向圖最短路問題使用單標號法。單標號法是對每一點賦予一個路權標號；而有向最短路問題使用雙標號法．雙標號法是對每一點賦予兩個標號：路徑和路權。擴充套件資料對於有向圖，情形就不同了，因為存在從u到v的路徑，並不蘊涵也存在從v到u的路徑。設D是一個有向圖，且u、v∈D，若存在從頂點u到頂點v的一條路徑，則稱從頂點v到頂點u可達。可達的慨念與從u到v的各種路徑的數目及路徑的長度無關。另外，為了完備起見，規定任一頂點到達它自身的是可達的。可達性是一個有向圖頂點的二元關係，依照定義，它是自反的，且是傳遞的。一般來說，可達不是對稱的，也不是反對稱的。