基本概念

圖：

頂點集+邊集

頂點集：所有頂點的集合，不能為空（因為圖是頂點集和邊集組成，其中一個頂點集不能為空，則圖肯定不為空）

邊集：所有邊的集合，邊是由頂點集中的2個頂點構成，如果邊集里的邊不是由頂點集里的2個頂點構成，那就構不成圖，可以為空

無向圖：

（只有度、邊、連通、連通圖、極大連通子圖(連通分量)、生成樹、帶權路徑長度的概念）

各個邊沒有方向，A和B有一條線，則A可以到B，B可以導A。邊用圓括號()，（A，B）=（B，A）

度：

依附于該頂點的邊的條數，也就是這個頂點有多少條線。記為TD(V)。TD(C)=2。一條邊為2個頂點提供一個度，即無向圖的度數之和是邊數的2倍

有向圖：

（只有入度、出度、弧頭、弧尾，強連通、強連通圖、強連通分量概念）：

各個邊有方向，各個邊又稱為弧，用尖括號<>表示邊，<A,B>≠<B,A>，A指向B，B沒有指向A，則B就不能到A。有箭頭指向的頂點稱為弧頭，沒有箭頭指向的頂點稱為弧尾，如<v,w>是從v到w的距離，v指向w，w是是弧頭，v是弧尾

頂點的入度：

以該頂點為基準，往該頂點指的箭頭有幾個。有多少邊指向該頂點。ID(A)=1

頂點的出度：

以該頂點為基準，往外指的箭頭有幾個。該頂點指向多少邊。OD(A)=4

?簡單圖：沒有頂點到自身的邊+沒有重復邊

多重圖：加了頂點到自身的邊

路徑(2個頂點之間)：

從1個頂點到另外一個頂點經過了哪些頂點序列（頂點可以重復，沒有重復的頂點序列就是簡單路徑)。

距離(2個頂點之間)：

路徑的長度。估摸是路徑中的頂點序列個數

無向圖A到D的路徑：ABD頂點序列(簡單路徑)或ABED(簡單路徑)序列或ABECD(簡單路徑)序列或ABEBD（出現重復頂點B，不是簡單路徑，但還是路徑）即頂點序列

無向圖連通(2個頂點之間)：

從一個頂點到另外一個頂點之間有沒有路徑存在，有路徑就是連通，沒路徑就是不連通。F頂點沒邊，即和其他頂點沒有連接，沒有路徑，不連通，沒有路徑的距離都是∞，距離都是最短序列（沒邊的頂點都沒有路徑，沒有路徑的距離都是∞）

有向圖強連通(2個頂點之間)：

如果從A到E有路徑，從E到A有路徑，則稱為兩個頂點強連通。如果有向圖A到E有路徑，E到A沒有路徑，因為沒有從E指出的箭頭，

連通圖：

針對無向圖來說，任意2個頂點都是連通的，即都有路徑，稱為連通圖，否則稱為非連通圖。

強連通圖：

針對有向圖來說，任意2個頂點都是強連通的，就是強連通圖

子圖：

從一個圖的頂點集合拿出一些頂點，再從圖的邊集里拿出一些邊，拿出的邊集和頂點集構成的圖（一定要構成圖，有的還構不成圖，如下圖就夠不成圖）就是原圖的子圖

生成子圖：

有2個圖，圖A和圖B，圖A和圖B的頂點集完全相同，但是圖B的邊集比圖A的邊集少（即少幾條邊）那圖B就是圖A的生成子圖?

?

連通分量（極大，無向圖）：

極大連通子圖（無向圖的子圖中的任意2個頂點之間都是連通的，即有路徑，并且盡可能都多的頂點和邊)稱為連通分量

連通分量如下：無向圖中G的三個子圖中都是連通圖(任意2個頂點之間都有路徑，子圖G只有一個頂點沒邊，所以認為也是連通的吧，各個子圖帶多個頂點啥的就不是連通圖了，比如把J這個頂點放到GHI這個子圖里，GHI子圖就不連通了)，且盡可能多的包含了無向圖G中的頂點和邊（那意思是無向圖G原來不是連通圖吧，因為J這個頂點和任意頂點都不連通且G、I、H和帶A的子圖也不連通）

?強連通分量（有向圖）：

有向圖中的ABCDE頂點是強連通的(因為各個頂點之間可以逆推)，但是加上F頂點不是(因為ABCDE頂點都可以推到F頂點，即連通，但是F頂點沒有到ABCDE的箭頭指向，即沒有路徑不能逆推，故不是強聯通的)，所以要把F頂點抽離出來，G頂點同，故構成如下三個強聯通子圖即強連通分量（跟無向圖類似，還是讓每個子圖盡量有多的可強連通的頂點和邊）

生成樹（極小）：

針對無向圖來說，首先生成樹包含圖中的所有頂點還要保持連通，但是還要在連通的請情況下保證邊少，即在保證連通的情況下，頂點數-1為最少的邊數，因為少一條邊的樹有各種形式，則一個圖的生成樹可能有多條。對于生成樹而言，少一條邊就會變成非連通圖，多一條邊就會形成一個回路。

一般生成樹用于各個沒有打通的村修路，各個村就相當于各個頂點，要讓各個村打通，不一定要把各個村之間都修上路，因為花費太大，所以可以使用生成樹的概念，在保證各個村連通的前提下，有最少的邊，邊修少了意味著修路的花費變少，且因為一個圖的生成樹樣式不只一種，則可以根據現實中修每條路的實際成本有多少，來確定到底怎樣修路

?

生成森林：

順序是圖是非連通圖，然后形成一個個連通分量(各個連通分量都是連通的且是圖的極大連通子圖，即在保證連通的前提下，每個連通分量擁有盡可能多的圖的頂點和邊)，然后連通分量再形成生成樹(生成樹都是連通的，且生成樹擁有連通分量的全部頂點和在保證連通的前提下盡可能少的邊)，然后就形成了生成森林（估摸是所有的連通分量的生成樹合在一起叫生成森林吧）

?

帶權路徑長度：

給路徑標上值，從北京到上海的帶權路徑長度=經過的路徑上標的值之和

帶權圖：

給路徑上標值的圖

?

?

有向樹并不是強連通圖，不是不都是是不是強連通圖?

?

做個記錄。。。。。。?