圖的概念比較雜亂，國內(nèi)各種書籍對(duì)一些概念也是各執(zhí)己見，比如圈和環(huán).......這里旨在按照一個(gè)規(guī)則了解一些概念，對(duì)于與其他書籍材料的不同，還要看情況再定

我們討論的圖大多為簡(jiǎn)單圖->沒有環(huán)和重邊

環(huán)：一個(gè)頂點(diǎn)到他自身的邊

圈：v1=vn的一條路徑。對(duì)于有向圖，路徑長(zhǎng)度為1的即為一個(gè)環(huán)（非簡(jiǎn)單圖）。對(duì)于無向圖，路徑長(zhǎng)度為1的還是環(huán)，不是圈。且對(duì)于沒有重邊的無向圖，u，v，u不算做圈，因?yàn)?/p>

（u，v），（v，u）是同一條邊，這樣的圈討論是無意義的，所以無向圖的圈，長(zhǎng)度至少為3。

DAG：有向無圈圖

連通圖：在無向圖中，每一個(gè)頂點(diǎn)到其他每個(gè)頂點(diǎn)均存在路徑

強(qiáng)連通圖：在有向圖中，每一個(gè)頂點(diǎn)到其他每個(gè)頂點(diǎn)均存在路徑

弱連通圖：有向圖不是強(qiáng)連通圖，但去掉方向后，對(duì)于這個(gè)無向圖，是連通的

連通分量：無向圖的極大連通子圖，應(yīng)滿足：子圖，連通，極大邊數(shù)，極大頂點(diǎn)數(shù)。因此對(duì)于無向圖，連通圖只有一個(gè)連通分量，即他本身，非連通圖存在大于一個(gè)的連通分量

強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖，滿足：子圖，強(qiáng)連通，極大邊數(shù)，極大頂點(diǎn)數(shù)。強(qiáng)連通圖也只有一個(gè)強(qiáng)連通分量，即他本身，非強(qiáng)連通圖存在大于一個(gè)的強(qiáng)連通分量

生成樹：

對(duì)于無向圖，要是連通的，生成樹為包含全部頂點(diǎn)的一個(gè)極小連通子圖

對(duì)于有向圖，生成樹為一棵有向樹，有一個(gè)頂點(diǎn)的入度為0，其他為1