【正文】 少的點覆蓋?；蛘哒f是“點” 覆蓋了所有“邊”。. 圖論中特殊的集合 Sets in graph點覆蓋(集)(vertex covering (set))：，滿足對于，有，關(guān)聯(lián)。記號表示一端在S中另一端在中的所有邊的集合。若某一邊就構(gòu)成就了邊割集，則稱此結(jié)點割邊(cut edge)或橋(bridge)。邊割集(edge cut set)：邊集，若G刪除了后不連通，但刪除了的任意真子集后G仍然連通。若某一結(jié)點就構(gòu)成就了點割集，則稱此結(jié)點割點(cut vertex)。割(cut)：點割集(vertex cut)：點集，若G刪除了后不連通，但刪除了的任意真子集后G仍然連通。圖G連通當(dāng)且僅當(dāng)。具體說，若圖G的頂點集V(G)可劃分為若干非空子集，使得兩頂點屬于同一子集當(dāng)且僅當(dāng)它們在G中連通，則稱每個子圖為圖G的一個連通分支（）。連通圖(connected graph)：圖G中任二頂點都連通。強(qiáng)連通(strongly connected)：在有向圖G中，兩個頂點間，至少存在一條路徑，稱兩個頂點強(qiáng)連通。簡單圖G中最短圈的長度稱為圖G的圍長(girth)，最長圈的長度稱為圖G的周長(perimeter)。對任意，從x到y(tǒng)的具有最小長度的路稱為x到y(tǒng)的最短路(shortest path)，其長度稱為x到y(tǒng)的距離(distance)，記為。途徑（閉途徑）、跡（閉跡）、路（圈）上所含的邊的個數(shù)稱為它的長度(length)。閉跡(closed trail)：起點和終點相同的跡，也稱為回路(circuit)。若，稱閉的(closed)；反之，稱為開的(open)。路(path)：頂點不重復(fù)的跡。. 路徑與回路 Path and Cycle途徑(walk)：圖G中一個點邊交替出現(xiàn)的序列，滿足。若，則完全二分圖G記作。二分圖（bipartite graph）：若圖G的頂點集可劃分為兩個非空子集X和Y，即且，且每一條邊都有一個頂點在X中，而另一個頂點在Y中，那么這樣的圖稱作二分圖。有向無環(huán)圖(directed acyclic graph(DAG))：有向的無環(huán)的圖。平凡圖(trivial graph)：一階零圖。特殊的圖：零圖(null graph)：，即只有孤立點的圖。圖的補(bǔ)圖(plement)：設(shè)G是一個圖，以為頂點集，以為邊集的圖稱為G的補(bǔ)圖，記為。點導(dǎo)出子圖(induced subgraph)：設(shè)，以為頂點集，以兩端點均在中的邊的全體為邊集所組成的子圖，稱為G的由頂點集導(dǎo)出的子圖，簡稱為G的點導(dǎo)出子圖，記為。生成樹(spanning tree)：設(shè)T是圖G的一個子圖，如果T是一棵樹，且，則稱T是G的一個生成樹。稱作圖G的子圖如果以及。偶點(even vertex)：度為偶數(shù)的點。匯(sink)：有向圖中，=0的點。葉(leaf)：度為1的點。出度(outdegree)：在有向圖中，一個頂點的出度是指與該邊相關(guān)聯(lián)的出邊(即邊的頭是v)的條數(shù)，記作。握手定理：無向圖：；有向圖：。鄰域(neighborhood)：在圖中與u相鄰的點的集合，稱為u的鄰域，記為。逆圖：把一個有向圖的每條邊都反向由此得到的有向圖。定向圖：對無向圖G的每條無向邊指定一個方向得到的有向圖。環(huán)(loop)：若一條邊的兩個頂點為同一頂點，則此邊稱作環(huán)。滿足的圖，稱為稀疏(sparse)圖；反之，稱為稠密(dense)圖。用三元組G(V,E,W)表示網(wǎng)絡(luò)。反之，若邊的點對無序則稱為無向(undirected)邊，所形成的圖稱無向圖(undirected graph)。所形成的圖稱有向圖(directed graph)。點對稱為邊(edge)或稱弧(arc)，其中，稱是相鄰的(adjacent)，稱u,v與邊相關(guān)聯(lián)(incident)或相鄰。為結(jié)點(node)或頂點(vertex)集。faster.1. 圖論 Graph Theory. 定義與術(shù)語 Definition and Glossary. 圖與網(wǎng)絡(luò) Graph and Network. 圖的術(shù)語 Glossary of Graph. 路徑與回路 Path and Cycle. 連通性 Connectivity. 圖論中特殊的集合 Sets in graph. 匹配 Matching. 樹 Tree. 組合優(yōu)化 Combinatorial optimization. 圖的表示 Expressions of graph. 鄰接矩陣 Adjacency matrix. 關(guān)聯(lián)矩陣 Incidence matrix. 鄰接表 Adjacency list. 弧表 Arc list. 星形表示 Star. 圖的遍歷 Traveling in graph. 深度優(yōu)先搜索 Depth first search (DFS). 概念. 求無向連通圖中的橋 Finding bridges in undirected graph. 廣度優(yōu)先搜索 Breadth first search (BFS). 拓?fù)渑判?Topological sort. 路徑與回路 Paths and circuits. 歐拉路徑或回路 Eulerian path. 無向圖. 有向圖. 混合圖. 無權(quán)圖 Unweighted. 有權(quán)圖 Weighed — 中國郵路問題The Chinese post problem. Hamiltonian Cycle 哈氏路徑與回路. 無權(quán)圖 Unweighted. 有權(quán)圖 Weighed — 旅行商問題The travelling salesman problem. 網(wǎng)絡(luò)優(yōu)化 Network optimization. 最小生成樹 Minimum spanning trees. 基本算法 Basic algorithms. Prim. Kruskal. Sollin（Boruvka）. 擴(kuò)展模型 Extended models. 度限制生成樹 Minimum degreebounded spanning trees. k小生成樹 The k minimum spanning tree problem(kMST). 最短路Shortest paths. 單源最短路 Singlesource shortest paths. 基本算法 Basic algorithms. Dijkstra. BellmanFord. Shortestpathalgorithm(SPFA). 應(yīng)用Applications. 差分約束系統(tǒng) System of difference constraints. 有向無環(huán)圖上的最短路 Shortest paths in DAG. 所有頂點對間最短路 Allpairs shortest paths. 基本算法 Basic algorithms. FloydWarshall. Johnson. 網(wǎng)絡(luò)流 Flow network. 最大流 Maximum flow. 基本算法 Basic algorithms. FordFulkerson method. EdmondsKarp algorithm. Minimum length path. Maximum capability path. 預(yù)流推進(jìn)算法 Preflow push method. Pushrelabel. Relabeltofront. Dinic method. 擴(kuò)展模型 Extended models. 有上下界的流問題. 最小費用流 Minimum cost flow. 找最小費用路 Finding minimum cost path. 找負(fù)權(quán)圈 Finding negative circle. 網(wǎng)絡(luò)單純形 Network simplex algorithm. 匹配 Matching. 二分圖 Bipartite Graph. 無權(quán)圖匈牙利算法 Unweighted Hopcroft and Karp algorithm. 帶權(quán)圖KM算法 Weighted –KuhnMunkres(KM) algorithm. 一般圖General Graph. 無權(quán)圖帶花樹算法 Unweighted Blossom (Edmonds)1. 圖論 Graph Theory. 定義與術(shù)語 Definition and Glossary. 圖與網(wǎng)絡(luò) Graph and Network二元組稱為圖(graph)。為中結(jié)點之間的邊的集合。若邊的點對有序則稱為有向(directed)邊，其中u稱為頭(head)，v稱為尾(tail)。為對于u來說是出邊(outgoing arc)；對于v來說是入邊(ining arc)。若圖的邊有一個權(quán)值(weight)，則稱為賦權(quán)邊，所形成的圖稱賦權(quán)圖(weighted graph)或網(wǎng)絡(luò)(network)。其中W表示權(quán)集，它的元素與邊集E一一對應(yīng)。. 圖的術(shù)語 Glossary of Graph階(order)：圖G中頂點集V的大小稱作圖G的階。簡單圖(simple graph)：沒有環(huán)、且沒有多重弧的圖稱作簡單圖。底圖：把一個有向圖的每一條有向邊的方向都去掉得到的無向圖。競賽圖(tournament)：有向圖的底圖是無向完全圖，則此有向圖是競賽圖。度：度(degree)：一個頂點的度是指與該邊相關(guān)聯(lián)的邊的條數(shù)，頂點v的度記作deg(v)。入度(indegree)：在有向圖中，一個頂點v的入度是指與該邊相關(guān)聯(lián)的入邊(即邊的尾是v)的條數(shù)，記作。孤立點(isolated vertex)：度為0的點。源(source)：有向圖中，=0 的點。奇點(odd vertex)：度為奇數(shù)的點。子圖：子圖(subgraph)：G39。生成子圖(spanning subgraph)：即包含G 的所有頂點的連通子圖，即滿足條件的G的子圖G’。即G的生成子圖，且子圖為樹。邊導(dǎo)出子圖(edgeinduced subgraph)：設(shè)，以為頂點集，以兩端點均在中的邊的全體為邊集所組成的子圖，稱為G的由邊集導(dǎo)出的子圖，簡稱為G的邊導(dǎo)出子圖，記為。點集的補(bǔ)集：記 為點集的補(bǔ)集。n階零圖記為。空圖(empty graph)：的圖。完全圖(plete graph)：完全圖是指每一對不同頂點間都有邊相連的的無向圖，n階完全圖常記作。完全二分圖(plete bipartite graph)：二分圖G中若任意兩個X和Y中的頂點都有邊相連，則這樣的圖稱作完全二分圖。正則圖(regular graph)：如果圖中所有頂點的度皆相等，則此圖稱為正則圖。跡(trail)：邊不重復(fù)的途徑。簡單圖中的路可以完全用頂點來表示。閉途徑(closed walk)：起點和終點相同的途徑。圈(cycle)：起點和終點相同的路。