基本介紹
- 中文名：有向圖
- 外文名：oriented graph
- 類型：表示物件與物件之間的關係
- 三元組：V(D)，A(D)，ψD
相關概念,鄰接矩陣,最短路的求解,可達性,
相關概念
孤立點：V中不與E中任一條邊關聯的點稱為D的孤立點．
簡單圖：不含平行邊的圖稱為簡單圖．
完備圖：圖中任兩個頂點U與u之間，恰有兩條有向邊(u，v)，及(v，u)，則稱該有向圖D為完備圖．
基本圖：把有向圖D的每條邊除去定向就得到一個相應的無向圖G，稱G為D的基本圖．稱D為G的定向圖．
強連通圖：給定有向圖G=(VE)，並且給定該圖G中的任意兩個結點u和v，如果結點u與結點v相互可達，即至少存在一條路徑可以由結點u開始，到結點v終止，同時存在至少有一條路徑可以由結點v開始，到結點u終止，那么就稱該有向圖G是強連通圖。
弱連通圖:若至少有一對結點不滿足單向連通，但去掉邊的方向後從無向圖的觀點看是連通圖，則D稱為弱連通圖．
單向連通圖:若每對結點至少有一個方向是連通的，則D稱為單向連通圖.
強連通分支:有向圖G的極大強連通子圖稱為該有向圖的強連通分支。
有向通路：無環有向圖D中總存在這樣一個獨立集5，使得y—Js中任何一點"，存在H∈S，從M到"有長度不超過2的有向通路．
鄰接矩陣
除了孤立頂點外，任意頂點都至少與一條邊相關聯，因此，任何有向圖，不考慮孤立頂點，可以由其邊集完全描述．例如，如果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.....
依照這種思想，我們可以用矩陣來完全地描述任何有向圖，這就是有向圖的鄰接矩陣．
最短路的求解
對於有向圖最短路問題，計算步驟與求解無向圖最短路問題相同，主要區別在於：無向圖最短路問題使用單標號法。單標號法是對每一點賦予一個路權標號；而有向最短路問題使用雙標號法．雙標號法是對每一點賦予兩個標號：路徑和路權。
可達性
對於一個無向圖來說，如果它是連通的，那么它的任意兩個頂點之問必存在一條路徑，因此，通過這一路徑可從一個頂點“到達”另一個頂點，若從頂點“可以到達u，則從u也可以到達“，也即v和u之間是互相可以到達的。
對於有向圖，情形就不同了，因為存在從u到v的路徑，並不蘊涵也存在從v到u的路徑。
設D是一個有向圖，且u、v∈D，若存在從頂點u到頂點v的一條路徑，則稱從頂點v到頂點u可達。
可達的慨念與從u到v的各種路徑的數目及路徑的長度無關。另外，為了完備起見，規定任一頂點到達它自身的是可達的。
可達性是一個有向圖頂點的二元關係，依照定義，它是自反的，且是傳遞的。一般來說，可達不是對稱的，也不是反對稱的。
