群暉 nas 做網(wǎng)站自媒體平臺注冊官網(wǎng)
一、圖論
? ? ? ? 圖論是數(shù)學的一個分支,它以圖為研究對象。圖論中的圖是若干給定的點(頂點)以及連接兩點的線(邊)構成的圖像,這種圖形通常用來描述某些事物之間的某種特定關系,用點代表事物,用連接兩點的線表示相應兩個事物間具有這種關系。
????????圖幾乎可以用來表現(xiàn)所有類型的結構或系統(tǒng),從交通網(wǎng)絡到通信網(wǎng)絡,從下棋游戲到最優(yōu)流程,從任務分配到人際交互網(wǎng)絡,圖都有廣闊的用武之地。
表示出最基礎的圖:(這些與點的大小,邊的粗細都無關,只表示點與點之間通過邊的關系)
?二、圖的基礎
? ? ? ? 1.頂點(vertex)
? ? ? ? ?在圖的應用中,每個頂點代表的含義均不相同,而是相互通過邊相聯(lián)系,因此將圖中的每個頂點進行標號進行區(qū)分。
???????????①.度數(shù)(degree)
? ? ? ????????? 與該頂點相關聯(lián)的總變數(shù),一個圖G的總度數(shù) d(V) 等于總邊數(shù)的兩倍,當圖的邊有方向時(有向圖),一個頂點的度可分為出度(out-degree)和入度(in-degree),出度是以該頂點為起點的邊數(shù),入度則是以該頂點為終點的邊數(shù)。
? ? ? ? ? ? ? ? ?②階數(shù)(order)
? ? ? ? ? ? ? ? ? 圖中含有頂點的個數(shù),即含有 n 個頂點,為 n 階圖
? ? ? ? 2. 邊(edge)
? ? ? ? 頂點與頂點之間通過邊聯(lián)系,構成一個完整的圖。
? ? ? ??????①權重(weight)
? ? ? ? ????????邊的權重(權值),即每條邊都有與之對應的值。
????????????????例如將兩個頂點看成兩個地點,邊看成兩個地點之間的距離。
三、圖的分類
? ? ? ? 綜合以上,圖可以分為以下幾種
????????1.有向圖/無向圖
???????????????最基本的圖通常被定義為“無向圖”,與之對應的則被稱為“有向圖”。兩者唯一的區(qū)別在于,有向圖中的邊是有方向性的。
? ? ? ? 無向邊:無固定方向的邊,既可 x 到 y,又可以 y 到 x
? ? ? ? 有向邊:固定方向的邊,即只能 x 到 y?,不能 y 到?x
? ? ? ? ?2.有權圖/無權圖
????????????有權圖:?權值就是一條邊的長度或代價。
????????????無權圖:?不是邊的權值為0,而是全都為1。
? ? ? ? 3.特殊的圖——環(huán)
????????????????在圖論中,環(huán)是一條只有第一個和最后一個頂點重復的非空路徑。一個沒有環(huán)的圖被稱作無環(huán)圖,一個沒有有向環(huán)的有向圖被稱做有向無環(huán)圖。一個無環(huán)的連通圖被稱作樹。
?
? ? ? ? ?4.連通圖/連通分量
? ? ? ? ? ? ? ? 在圖G中,任意兩個頂點之間都存在路徑,則稱G為連通圖
上圖雖然不是一個連通圖(例 點8 與 點4 不連通),但它有兩個連通子圖,1234,56789,
????????把一個圖的最大連通子圖稱為它的連通分量。5,6,7,8,9頂點構成的子圖就是該圖的最大連通子圖,也就是連通分量。
連通分量特點:①子圖
? ? ? ? ? ? ? ? ? ? ? ? ?②子圖是連通的
? ? ? ? ? ? ? ? ? ? ? ? ?③子圖含有最大的頂點數(shù)
對于連通圖而言,最大連通分量就是其本身