一、圖論

? ? ? ? 圖論是數(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ù)

對于連通圖而言，最大連通分量就是其本身