有向圖

孤立點：V中不與E中任一條邊關聯的點稱為D的孤立點．

簡單圖：不含平行邊的圖稱為簡單圖．

完備圖：圖中任兩個頂點U與u之間，恰有兩條有向邊(u，v)，及(v，u)，則稱該有向圖D為完備圖．

基本圖：把有向圖D的每條邊除去定向就得到一個相應的無向圖G，稱G為D的基本圖．稱D為G的定向圖． ^[2] 

強連通圖：給定有向圖G=(VE)，並且給定該圖G中的任意兩個結點u和v，如果結點u與結點v相互可達，即至少存在一條路徑可以由結點u開始，到結點v終止，同時存在至少有一條路徑可以由結點v開始，到結點u終止，那麼就稱該有向圖G是強連通圖。

弱連通圖:若至少有一對結點不滿足單向連通，但去掉邊的方向後從無向圖的觀點看是連通圖，則D稱為弱連通圖．

單向連通圖:若每對結點至少有一個方向是連通的，則D稱為單向連通圖. ^[3] 

強連通分支:有向圖G的極大強連通子圖稱為該有向圖的強連通分支。 ^[4] 

有向通路：無環有向圖D中總存在這樣一個獨立集5，使得y—Js中任何一點"，存在H∈S，從M到"有長度不超過2的有向通路． ^[5] 

除了孤立頂點外，任意頂點都至少與一條邊相關聯，因此，任何有向圖，不考慮孤立頂點，可以由其邊集完全描述．例如，如果D的邊如下：

(1，1)，(1，2)，(1，3)，(1，4)，(2，2)，(2，3)，(2，4)，(3，3)，(3，4)，(4，4)，

注意，我們是按照字典序列出D的邊的，只不過這裏不是a，b，c，…，而是1，2，3.....

依照這種思想，我們可以用矩陣來完全地描述任何有向圖，這就是有向圖的鄰接矩陣． ^[6] 

對於有向圖最短路問題，計算步驟與求解無向圖最短路問題相同，主要區別在於：無向圖最短路問題使用單標號法。單標號法是對每一點賦予一個路權標號；而有向最短路問題使用雙標號法．雙標號法是對每一點賦予兩個標號：路徑和路權。 ^[7] 

對於一個無向圖來説，如果它是連通的，那麼它的任意兩個頂點之問必存在一條路徑，因此，通過這一路徑可從一個頂點“到達”另一個頂點，若從頂點“可以到達u，則從u也可以到達“，也即v和u之間是互相可以到達的。

對於有向圖，情形就不同了，因為存在從u到v的路徑，並不藴涵也存在從v到u的路徑。

設D是一個有向圖，且u、v∈D，若存在從頂點u到頂點v的一條路徑，則稱從頂點v到頂點u可達。

可達的慨念與從u到v的各種路徑的數目及路徑的長度無關。另外，為了完備起見，規定任一頂點到達它自身的是可達的。

可達性是一個有向圖頂點的二元關係，依照定義，它是自反的，且是傳遞的。一般來説，可達不是對稱的，也不是反對稱的。