什么是有向圖
編輯在數學中,更具體地說,在圖論中,有向圖(或二維圖)是由一組頂點組成的圖,這些頂點由有向邊連接,通常稱為弧。
有向圖的定義
編輯在形式上,一個有向圖是一個有序的對G=(V,A),其中V是一個集合,其元素被稱為頂點、節點或點;A是一組有序的頂點對,被稱為弧、有向邊(有時僅僅是邊,相應的集合被稱為E而不是A)、箭頭或有向線。它與普通圖或無向圖不同,因為后者是以無序的頂點對來定義的,通常被稱為邊、鏈接或線。上述定義不允許有向圖有多個具有相同源節點和目標節點的箭頭,但有些作者考慮了一個更廣泛的定義,允許有向圖有這樣的多個弧(即他們允許弧集是一個多集)。有時這些實體被稱為有向多圖(或多圖)。另一方面,上述定義允許有向圖有循環(即直接連接節點與自身的弧),但有些作者考慮采用較窄的定義,不允許有向圖有循環。無循環的有向圖可稱為簡單有向圖,而有循環的有向圖可稱為循環圖(見有向圖的類型一節)。有向圖的類型子類對稱有向圖是指所有的邊都出現了兩次,每個方向都有一個(也就是說,對于每個屬于二維圖的箭頭,相應的反向箭頭也屬于它)。(這樣的邊有時被稱為雙定向,這樣的圖有時也被稱為雙定向,但這與雙定向圖的含義相沖突。)簡單有向圖是指沒有循環(直接將頂點連接到自己的箭頭)和沒有具有相同源節點和目標節點的多個箭頭的有向圖。如前所述,在有多個箭頭的情況下,該實體通常被稱為有向多圖。有些作者把帶有循環的數字圖描述為循環圖。完整的有向圖是簡單的有向圖,其中每一對頂點由一對對稱的有向弧連接(它等同于無向完整圖,其邊由一對反向弧代替)。因此,一個完整的數字圖是對稱的。半完整的多部分數字圖是簡單的數字圖,其中頂點集被劃分為不同的集合,對于不同集合中的每一對頂點x和y,x和y之間有一個弧。半完整的數字圖是簡單的數字圖,其中每一對頂點之間有一個弧。每個半完全數位圖都是一個半完全的多分位數位圖,以一種微妙的方式,每個頂點構成分區的一個集合。準跨度數位圖是簡單數位圖,對于每個不同頂點的三重x,y,z,有從x到y和從y到z的弧,x和z之間有一條弧,注意x和z之間可以只有一條弧,或者兩個方向相反的弧。一個半完整的數位圖是一個準跨度數位圖。準遍歷圖有一些擴展,叫做k-準遍歷圖。有向圖是沒有對向邊的有向圖(即(x,y)和(y,x)中最多有一條可能是圖的箭頭)。由此可見,當且僅當一個有向圖沒有2-循環時,它就是一個有向圖。(這不是定向圖的xxx含義;見定向(圖論)。)錦標賽是通過為無定向完整圖的每條邊選擇一個方向而得到的定向圖。請注意,錦標賽是一個半完全圖。如果一個有向圖沒有有向循環,那么它就是無循環的。
這種圖的通常名稱是有向無環圖(DAG)。多樹是指從同一起始頂點到同一終止頂點沒有兩條不同的有向路徑的DAG。有向樹或多樹是通過對樹(連接的、無環的無向圖)的邊進行定向形成的DAG。有根樹是定向樹,其中底層無向樹的所有邊要么遠離根,要么指向根(它們分別被稱為樹冠或外樹,以及內樹。具有補充屬性的圖加權有向圖(也稱為有向網絡)是(簡單的)有向圖,其箭頭被分配了權重,類似于加權圖(也稱為無向網絡或加權網絡)。流網絡是加權有向圖,其中有兩個節點被區分為源和匯。有根有向圖(也稱為流圖)是有根圖,其中一個頂點被區分為根。控制流圖是有根圖,在計算機科學中作為一種代表。
內容由匿名用戶提供,本內容不代表www.gelinmeiz.com立場,內容投訴舉報請聯系www.gelinmeiz.com客服。如若轉載,請注明出處:http://www.gelinmeiz.com/164454/