Level Up

基本圖論
    探討問題
        存在性問題
        最佳化問題
    術語
        圖形(Graph)
            由邊線與節點構成的有限集合
            兩大種類
                有向圖
                無向圖
        有向圖(directed graph)
            具方向性邊線的圖性
            <V1,V2>代表一個有向的邊，V1是該邊的尾，V2是頭
            <V1,V2>和<V2,V1>代表不同的邊
        無向圖(undirected graph)
            不具方向性邊線的圖形
            (V1,V2)和(V2,V1)代表相同的邊
        節點(vertex)
        邊線(edge)
        路徑(path)
            從起點到終點所經過的節點串列
        路徑長度(path length)
            路徑所經過的邊數
        簡單路徑(simple path)
            不含重複節點的路徑
            除了起點與終點可能相同，其他節點皆不相同
        迴路(cycle)
            起訖為同節點的簡單路徑
        連通圖(connected graph)
            每個節點對任一節點都有路徑相通
            有向連通圖稱為強連通圖
        連通單元(connected component)
            非連接的圖形由多個連接的子圖形組成，這些子圖即為連接元件
        樹(tree)
            無迴路的圖形
            由一個以上節點構成的有限集合
            有一特定節點稱為樹根
            其餘節點分為n(n>=0)個互斥集合，這些互斥集合也為一棵樹
        森林(forest)
            一群不相連的樹所組成
            n(n>=0)個互斥樹之集合
        生成樹(spanning tree)
            又稱展開樹
            非唯一
            由連通圖的子圖所構成的樹，此樹連接圖形所有節點
            不連通=>無生成樹
            同圖形的生成樹不一定有交集的邊
        最小生成樹
            邊線權值總和最小的生成樹
        完全圖(complete graph)
            n節點無向圖，具n(n-1)/2個邊
        稀疏圖(sparse graph)
        茂密圖(dense graph)
        權值(weight)
        加權圖(weighted graph)
            邊線具有權值的圖形
        網路(network)
            加權有向圖
        分支度(Degree)
            每個節點的子樹個數
        樹葉(Leaf)
            又稱終端節點(Terminal Node)
            分支度為零的節點
        非終端節點(Nonterminal Node)
            又稱非樹葉節點(Non-Leaf Node)
            Degree>=1的節點
        子點(Child Node)
        父點(Parent Node)
        兄弟(Sibling)
            同一父點的子點
        祖先(Ancestors)
            樹根到該節點路徑中所包含的節點
        階度(Level)
            樹根階度為1
            某節點階度為I，則子節點階度為I+1
        樹的分支度(Degree of Tree)
            樹中節點的最大分支度
            Max(各Node之Degree)
        高度(Height)
            又稱深度(Depth)
            樹中節點的最大階度
            Max(各Node之Level)
        入支度(In-Degree)
            有向圖中指向節點的邊數
        出支度(Out-Degree)
            有向圖中從節點出去的邊數
        源點(source)
        匯點(sink)
        剩餘流量網路(residual network)
            容量值-流量值
            表任兩節點間還能容納的流量
        遞增路徑
            可以遞增總流量的路徑
    圖形表示法
        相鄰矩陣(adjacency matrix)
            特點
                n個節點的圖形需使用n*n的空間
                無向圖的相鄰矩陣是對稱的
                有向圖的相鄰矩陣不一定是對稱的
            分支度計算
                無向圖的分支度為列元素和
                有向圖的出支度為列元素和，入支度為行元素和
            優缺點
                優點
                    簡單
                    存取效率高
                    計算分支度方便
                    插入刪除邊線容易
                    易判斷邊線存在與否，時間複雜度為O(1)
                缺點
                    空間浪費
                        邊線多寡所需空間皆固定
        相鄰串列(adjacency list)
            優缺點
                優點
                    節省空間
                缺點
                    求算邊數與判斷是否連通，時間複雜度為O(n*n)
                        需搜尋整條串列才能獲知邊線存在與否
                    加入刪除邊線不便
        相鄰多元串列(Adjacency Multilist)
        索引表(Index Table)
            以一維陣列紀錄相鄰節點編號
            以索引陣列記錄相鄰節點起始位置
    圖形搜尋法
        又稱圖型的走訪(graph traversal)
        有系統地依循邊線拜訪圖形節點
        演算法
            深度優先搜尋(depth-first search)
                用遞迴或堆疊
            廣度優先搜尋(breadth-firth search)
                用佇列
        應用
            偵測圖形是否有迴路
                利用深度優先搜尋
                相鄰節點若拜訪過則表示有迴路
            判斷圖形是否連通
            找圖形的連通單元
            找出圖形的雙連通單元
            找連通圖形的生成樹
    加權圖
        最小生成樹
            演算法
                普林(Prim)
                    令U=空集合，另一為V-U集合
                    挑出最小成本的邊(u,w),其中u屬於U，w屬於V-U
                    (u,w)自E中刪除，加入生成樹中，同時將w自V-U刪除，並加到U
                    Repeat 2~3步驟直到U=V或無邊可挑
                克魯斯克爾(Kruskal)
                    E中挑出最小成本的邊並刪除
                    若此邊加入生成樹未造成迴路則加入，否則取消挑選
                    Repeat 1~2步驟直至無邊可挑
                Sollin
                    每個節點皆是為獨立的Free Root
                    從各樹中挑出最小成本的樹邊
                    刪除重複挑出的樹邊
                    Repeat 2~3直到剩一棵樹或無邊可挑為止
            應用
                電路佈局
                連接多個城市之交通連線的最小架設成本
                旅遊多個城市的最少花費
        最短路徑
            種類
                單源最短路徑(Single-source shortest-path)
                任意兩節點之最短路徑(All-pairs shortest-path)
            演算法
                迪杰斯特拉(Dijkstra)
                    圖形不能存在負加權值，否則可能有誤
                    從起點開始循序確定到各相鄰節點的最短路徑
                貝爾曼-福特(Bellman-Ford)
                    反覆檢查每條邊線,進行最短路徑放鬆
                    可用於負邊線加權值有向圖
                弗洛伊德(Fly-Warshall)
                    節點X到Y的距離，可因節點W的加入而縮短，那就將W加入X和Y之間的最短路徑
        網路流
            最大流量問題
                從源點到匯點之間的最大流量
                演算法
                    Ford-Fulkerson
                    Edmonds-Karp
            配對問題