圖論1江川圖論1江川1七橋問題七橋問題2七橋問題七橋問題3七橋問題七橋問題4圖、點、邊G=(V,E)V頂點集E邊集圖的基本概念圖、點、邊圖的基本概念5G=(V,E)有向圖、無向圖無向圖V&Ve={a,b}有向圖VxVe=<a,b>={{a},{a,b}}圖的基本概念G=(V,E)圖的基本概念6G=(V,E)度（入度、出度）環路徑割圖的基本概念G=(V,E)圖的基本概念7G=(V,E)簡單圖完全圖二分圖平面圖圖的基本概念G=(V,E)圖的基本概念8鄰接矩陣圖的表示鄰接矩陣圖的表示9鄰接表（邊表）圖的表示鄰接表（邊表）圖的表示10判定連通度數平衡（有向、無向）歐拉環判定歐拉環11求解“有邊就走”回溯歐拉環求解歐拉環12其他歐拉路混合圖歐拉環其他歐拉環13漢密爾頓回路漢密爾頓回路14NP-Complete對于頂點個數大于2的圖，如果圖中任意兩點度的和大于或等于頂點總數，那這個圖一定是哈密頓圖。漢密爾頓回路vs歐拉回路漢密爾頓回路NP-Complete漢密爾頓回路15如果一個問題不是多項式時間可解的……1、加強條件，針對特定情況2、減弱要求，求近似解3、降低問題規模漢密爾頓回路如果一個問題不是多項式時間可解的……漢密爾頓回路16O(n!*n）？狀態壓縮動態規劃要考慮的狀態：已經經過哪些點？2^n經過點的順序？n！n*nn漢密爾頓回路O(n!*n）？漢密爾頓回路17例：[1,0,1,1,0][3]表示經過了1、3和4，并停在3狀態數：2^n*n轉移：n復雜度：O（2^n*n^2）POJ3311漢密爾頓回路例：[1,0,1,1,0][3]漢密爾頓回路18Floyd點對間的距離O（n^3）動態規劃的思想F[i,j,k]F[i,j]最短路Floyd最短路19Dijkstra單源最短路徑貪心算法尋找未處理的最小的點更新其他點不能有負權邊O（V^2）O（VlogV+E）最短路有效的程序員不應該浪費很多時間用于程序調試，他們應該一開始就不要把故障引入。Dijkstra最短路有效的程序員不應該浪費很20Bellman-Ford對每一條邊進行松弛操作，重復V次：foreachedge(u,v)ifd[v]>d[u]+w(u,v)d[v]=d[u]+w(u,v)允許負權邊，可判斷負權圈O（VE）最短路Bellman-Ford最短路21SPFAShortestPathFasterAlgorithmBellman-Ford的優化用一個隊列存儲被更新的點期望復雜度：O（kE）最短路SPFA最短路22特殊的圖連通性結構實用序層次樹特殊的圖樹23最小生成樹Prim算法兩個點集（加入生成樹和未加入生成樹）O（V^2）Kruscal算法按邊權順序從小到大枚舉O（ElogE）生成樹最小生成樹生成樹24次小生成樹在最小生成樹上添邊生成環刪邊新的生成樹在最小生成樹上求兩點路徑上最大的邊poj1679生成樹次小生成樹生成樹25拓撲排序1、選擇入度為0的點v2、刪除v和從v出發的所有邊拓撲排序與強連通分量拓撲排序拓撲排序與強連通分量26強連通分量Tarjan算法基于對圖深度優先搜索的算法DFN（u）：u搜索到的次序編號（時間戳）Low（u）：u或者u的子樹能夠追溯到的最早的搜索棧中的節點的次序號。DFN(u)=Low(u)時，以u為根的搜索子樹上所有節點是一個強連通分量。拓撲排序與強連通分量強連通分量拓撲排序與強連通分量27拓撲排序與強連通分量拓撲排序與強連通分量28拓撲排序與強連通分量拓撲排序與強連通分量29拓撲排序與強連通分量拓撲排序與強連通分量30拓撲排序與強連通分量拓撲排序與強連通分量31拓撲排序與強連通分量拓撲排序與強連通分量32拓撲排序與強連通分量O（V+E）POJ2762拓撲排序與強連通分量O（V+E）33割點v：去掉點v后圖不連通橋/割邊e：去掉邊e后圖不連通雙連通分量：1、（邊）任意去掉一條邊，圖仍連通2、（點）任意去掉一個點，圖仍連通割點、橋、雙連通分量割點v：去掉點v后圖不連通割點、橋、雙連通分量34Tarjan算法求割點在圖的搜索樹中，如果u為割點，當且僅當滿足下面的條件：1、如果u為樹根，那么u必須有多于1棵子樹2、如果u不為樹根，那么（u,v）為樹枝邊，當Low[v]>=DFN[u]時。割點、橋、雙聯通分量Tarjan算法求割點割點、橋、雙聯通分量35割點、橋、雙聯通分量割點、橋、雙聯通分量36在一個網絡中，某些點之間可以接發信息（單向）。問至少增加多少條邊可以使從任一點發送的信息可以到達其他所有點？

例題1在一個網絡中，某些點之間可以接發信息（單向）。問至少增加多少37強連通分量看做一個點觀察入度為0的點和出度為0的點poj1236

例題1強連通分量看做一個點例題138給定一個有向無環圖，n個點，m條邊（1<=n<=100000,

0<=m<=1000000），每個點有點權。要求選擇一條從某個入度為0的點到某個出度為0的點的路徑，使得整個路徑上點的權值之和最大。

例題2給定一個有向無環圖，n個點，m條邊（1<=n<=10000039有向無環圖拓撲排序圖DPpoj3249例題2有向無環圖拓撲排序例題240謝謝！謝謝！41圖論1江川圖論1江川42七橋問題七橋問題43七橋問題七橋問題44七橋問題七橋問題45圖、點、邊G=(V,E)V頂點集E邊集圖的基本概念圖、點、邊圖的基本概念46G=(V,E)有向圖、無向圖無向圖V&Ve={a,b}有向圖VxVe=<a,b>={{a},{a,b}}圖的基本概念G=(V,E)圖的基本概念47G=(V,E)度（入度、出度）環路徑割圖的基本概念G=(V,E)圖的基本概念48G=(V,E)簡單圖完全圖二分圖平面圖圖的基本概念G=(V,E)圖的基本概念49鄰接矩陣圖的表示鄰接矩陣圖的表示50鄰接表（邊表）圖的表示鄰接表（邊表）圖的表示51判定連通度數平衡（有向、無向）歐拉環判定歐拉環52求解“有邊就走”回溯歐拉環求解歐拉環53其他歐拉路混合圖歐拉環其他歐拉環54漢密爾頓回路漢密爾頓回路55NP-Complete對于頂點個數大于2的圖，如果圖中任意兩點度的和大于或等于頂點總數，那這個圖一定是哈密頓圖。漢密爾頓回路vs歐拉回路漢密爾頓回路NP-Complete漢密爾頓回路56如果一個問題不是多項式時間可解的……1、加強條件，針對特定情況2、減弱要求，求近似解3、降低問題規模漢密爾頓回路如果一個問題不是多項式時間可解的……漢密爾頓回路57O(n!*n）？狀態壓縮動態規劃要考慮的狀態：已經經過哪些點？2^n經過點的順序？n！n*nn漢密爾頓回路O(n!*n）？漢密爾頓回路58例：[1,0,1,1,0][3]表示經過了1、3和4，并停在3狀態數：2^n*n轉移：n復雜度：O（2^n*n^2）POJ3311漢密爾頓回路例：[1,0,1,1,0][3]漢密爾頓回路59Floyd點對間的距離O（n^3）動態規劃的思想F[i,j,k]F[i,j]最短路Floyd最短路60Dijkstra單源最短路徑貪心算法尋找未處理的最小的點更新其他點不能有負權邊O（V^2）O（VlogV+E）最短路有效的程序員不應該浪費很多時間用于程序調試，他們應該一開始就不要把故障引入。Dijkstra最短路有效的程序員不應該浪費很61Bellman-Ford對每一條邊進行松弛操作，重復V次：foreachedge(u,v)ifd[v]>d[u]+w(u,v)d[v]=d[u]+w(u,v)允許負權邊，可判斷負權圈O（VE）最短路Bellman-Ford最短路62SPFAShortestPathFasterAlgorithmBellman-Ford的優化用一個隊列存儲被更新的點期望復雜度：O（kE）最短路SPFA最短路63特殊的圖連通性結構實用序層次樹特殊的圖樹64最小生成樹Prim算法兩個點集（加入生成樹和未加入生成樹）O（V^2）Kruscal算法按邊權順序從小到大枚舉O（ElogE）生成樹最小生成樹生成樹65次小生成樹在最小生成樹上添邊生成環刪邊新的生成樹在最小生成樹上求兩點路徑上最大的邊poj1679生成樹次小生成樹生成樹66拓撲排序1、選擇入度為0的點v2、刪除v和從v出發的所有邊拓撲排序與強連通分量拓撲排序拓撲排序與強連通分量67強連通分量Tarjan算法基于對圖深度優先搜索的算法DFN（u）：u搜索到的次序編號（時間戳）Low（u）：u或者u的子樹能夠追溯到的最早的搜索棧中的節點的次序號。DFN(u)=Low(u)時，以u為根的搜索子樹上所有節點是一個強連通分量。拓撲排序與強連通分量強連通分量拓撲排序與強連通分量68拓撲排序與強連通分量拓撲排序與強連通分量69拓撲排序與強連通分量拓撲排序與強連通分量70拓撲排序與強連通分量拓撲排序與強連通分量71拓撲排序與強連通分量拓撲排序與強連通分量72拓撲排序與強連通分量拓撲排序與強連通分量73拓撲排序與強連通分量O（V+E）POJ2762拓撲排序與強連通分量O（V+E）74割點v：去掉點v后圖不連通橋/割邊e：去掉邊e后圖不連通雙連通分量：1、（邊）任意去掉一條邊，圖仍連通2、（點）任意去掉一個點，圖仍連通割點、橋、雙連通分量割點v：去掉點v后圖不連通割點、橋、雙連通分量75Tarjan算法求割點在圖的搜索樹中，如果u為割點，當且僅當滿足下面的條件：1、如果u為樹根，那么u必須有多于1棵子樹2、如果u不為樹根，那么（u,v）為樹枝邊，當Low[v]>=DFN[u]時。割點、橋、雙聯通分量Tarjan算法求割點割點、橋、雙聯通分量76割點、橋、雙聯通分量割點、橋、雙聯通分量77在一個網絡中，某些點之間可以接發信息（單向）。問至少增加多少條邊可以使從任一點發送的信息可以到達其他所有點？

例題1在一個網絡中，某些點之間可以接發信息（單向）。問至少增