圖論基礎(chǔ)

概念

圖是由頂點V和邊E的集合組成的二元組赤兴，記G=(V,E)

有向圖妖滔、無向圖、有權(quán)圖桶良、無權(quán)圖座舍、連通圖（聯(lián)通分量）、二分圖

頂點的度（無向圖種與頂點相連的邊的數(shù)目）陨帆、入度（有向圖中以該頂點為終點的邊的數(shù)目）曲秉、出度（有向圖中以該頂點為起點的邊的數(shù)目），度等于入度和出度之和疲牵，所有邊的入度和=所有邊的出度和=邊數(shù)

圖的定義是指將邊作為一個集合承二，從而允許兩個無向邊具有相同的端點。對于兩個有向邊可以有相同的起點和終點纲爸。這種邊稱為平行邊或者多重邊亥鸠。另一種邊的特殊類型是頂點和自己連接，也就是說兩個頂點重合，我們稱這樣的邊為自循環(huán)负蚊。除了少數(shù)例外神妹，圖沒有平行邊和自循環(huán)

圖G中從頂點u到頂點v有一條路徑，我們稱u到達v盖桥，并且v是從u可達的灾螃。在無向圖中，可達性的概念是對稱的揩徊。

如果一個圖是連通的腰鬼，則意味著對于任何兩個頂點，它們中間都是有路徑的塑荒。

如果對于G的任何兩個頂點u和v熄赡，都有u可達v并且v可達u，則有向圖是強連通的

圖G的子圖是頂點和邊是G的頂點和邊的各自的子集的圖H齿税。G的生成子圖是包含圖G的所有頂點的圖彼硫。

如果圖G是不連通的，它的最大聯(lián)通子圖稱為G的連通分支凌箕。

森林是沒有循環(huán)的圖拧篮。樹是連通的森林，即沒有循環(huán)的聯(lián)通圖牵舱。圖的生成樹是樹的生成子圖

重要特性

特性1：如果G是由m條邊和頂點集V的圖串绩，那么 $\sum_{v\ in\ V}deg(v)=2m$ ，即邊對頂點度數(shù)的總貢獻度是邊數(shù)目的兩倍

特性2：如果G是有m條邊和頂點集V的有向圖芜壁，那么 $\sum_{v\ in\ V}in\ deg(v)=\sum_{v\ in\ V}out\ deg(v)=m$ 即邊對它的起點u的出度貢獻了一個單元礁凡，對終點v的入度貢獻了一個單元。因此邊對頂點出度的總貢獻和邊的數(shù)目相等慧妄，入度也是一樣顷牌。

特性3：給定G為具有n個頂點m條邊的簡單圖。如果G是無向的塞淹，那么 $m<=\frac{n(n-1)}{2}$ 窟蓝，如果G是有向的，那么 $m<=n(n-1)$

假設(shè)G是無向的饱普。因為沒有兩條邊可以有相同的端點且沒有自循環(huán)运挫，在這種情況下G的頂點的最大度是n-1，通過特性1可知费彼， $2m<=n(n-1)$ 滑臊。假設(shè)G是有向的口芍，因為沒有兩條邊具有相同的起點和終點箍铲，且沒有自循環(huán)，這種情況下G的頂點的最大入度是n-1鬓椭，通過特性2颠猴， $m<=n(n-1)$

特性4：給定G是有n個頂點和m條邊的無向圖关划。

如果G是聯(lián)通的，那么 $m>=n-1$
如果G是一棵樹翘瓮，那么 $m=n-1$
如果G是森林贮折，那么 $m<=n-1$

圖的數(shù)據(jù)結(jié)構(gòu)

邊列表：對所有邊采用無序的列表。但是沒有有效的辦法找到特定的邊(u,v)?资盅，或者將所有的邊入射到頂點v

鄰接列表：為每個頂點維護一個單獨的列表调榄，包括入射到頂點的那些邊『强福可以通過取較小集合的并集來確定完整的邊集合每庆，也可以更高效地找到所有入射到給出頂點的邊

鄰接圖：和鄰接列表非常相似，但是所有入射到頂點的邊的次級容器被組織成一個圖今穿，而不是一個列表缤灵，用相鄰的頂點作為鍵。這允許在O(1)的時間內(nèi)訪問特定的邊(u,v)

鄰接矩陣：對于有n個頂點的圖維持一個n*n矩陣來提供最壞的情況下訪問特定邊(u,v)的時間O(1)蓝晒。每一項專用于為頂點u和v的特定對存儲一個參考邊(u,v)腮出；如果沒有這樣的邊存在，該表項即為空

邊列表

可能是最簡單的芝薇，但不是最有效的胚嘲。所有頂點存儲在一個無序的列表V中，并且所有的邊對象存儲在一個無序的列表E中

鄰接列表結(jié)構(gòu)

將圖形的邊存儲在較小的位置來對其進行分組剩燥，從而和每個單獨的頂點相關(guān)聯(lián)的次級容器結(jié)合起來慢逾。具體的，對每個頂點v維持一個集合l(v)灭红，該集合被稱為v的入射列表侣滩，其中全部都是入射到v的邊。（在有向圖的情況下变擒，輸出邊和輸入邊分別存儲在兩個單獨的集合lout(v)和lin(v)中君珠。

同時要求鄰接列表的基本結(jié)構(gòu)在某種程度上保持頂點集合V，因此可以在O(1)時間內(nèi)為給出的頂點v找出次級結(jié)構(gòu)l(v)

傳遞閉包

命題：對于i=1娇斑，...策添，n，當(dāng)且僅當(dāng)有向圖 $G$ 從 $v_i$ 到 $v_j$ 有一條有向路徑時毫缆，有向圖 $G_k$ 有邊 $(v_i,v_j)$ 唯竹，其中中間的頂點在集合 ${v_1,...,v_k}$ 中，特別的苦丁， $G_k$ 和 $G^*$ 相等浸颓， $G^*$ 是 $G$ 的傳遞閉包

該命題為計算G的依賴于一系列界限的每個 $G_k$ 傳遞閉包提出了一個簡單算法。這個算法被稱為Floyd_Warshall算法

沒有有向循環(huán)的有向圖被叫作有向非循環(huán)圖，或者簡稱DAG