-
有向圖
(有向圖)
鎖定
- 中文名
- 有向圖
- 外文名
- oriented graph
- 類 型
- 表示物件與物件之間的關係
- 三元組
- V(D),A(D),ψD
有向圖相關概念
孤立點:V中不與E中任一條邊關聯的點稱為D的孤立點.
簡單圖:不含平行邊的圖稱為簡單圖.
完備圖:圖中任兩個頂點U與u之間,恰有兩條有向邊(u,v),及(v,u),則稱該有向圖D為完備圖.
強連通圖:給定有向圖G=(VE),並且給定該圖G中的任意兩個結點u和v,如果結點u與結點v相互可達,即至少存在一條路徑可以由結點u開始,到結點v終止,同時存在至少有一條路徑可以由結點v開始,到結點u終止,那麼就稱該有向圖G是強連通圖。
弱連通圖:若至少有一對結點不滿足單向連通,但去掉邊的方向後從無向圖的觀點看是連通圖,則D稱為弱連通圖.
單向連通圖:若每對結點至少有一個方向是連通的,則D稱為單向連通圖.
[3]
有向圖鄰接矩陣
(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的各種路徑的數目及路徑的長度無關。另外,為了完備起見,規定任一頂點到達它自身的是可達的。
可達性是一個有向圖頂點的二元關係,依照定義,它是自反的,且是傳遞的。一般來説,可達不是對稱的,也不是反對稱的。