使用者50301481548692021-06-10 17:24:14度數（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的各種路徑的數目及路徑的長度無關。另外，為了完備起見，規定任一頂點到達它自身的是可達的。可達性是一個有向圖頂點的二元關係，依照定義，它是自反的，且是傳遞的。一般來說，可達不是對稱的，也不是反對稱的。頭條萊垍
仔仔2022-01-06 23:22:45總度數（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）。垍頭條萊
