鏈接無向圖有向圖和樹

1、CHAPTER 6 GRAPHS, DIRECTED GRAPHS, AND TREESGlossarygraph：（無向）圖vertex set：頂點集edge set：邊集endpoint：端點incident on：關(guān)聯(lián)于adjacent：鄰接simple graph：簡單（無向）圖loop：自回路，環(huán)multigraph：多（重）圖 labeled graph：標號圖pseudograph：偽圖 utility：公用事業(yè)designing a chip：設(shè)計芯片planar graph：平面圖degree：度 isolated vertex：孤立結(jié)點subgraph：子圖 path：通

2、路，路徑 simple path：基本路徑 connected：連通的component：連通分支cycle：回路simple cycle：基本回路complete graph：完全圖bipartite graph：二部圖，偶圖complete bipartite graph：完全二部圖directed graph(digraph)：有向圖directed edge：有向邊initial vertex：起點terminal vertex：終點outdegree：出度indegree：入度source：源sink：匯directed multigraph：有向多重圖labeled directe

3、d graph：有向標記圖directed subgraph：有向子圖directed path：有向通路（路徑）underlying graph：底圖strongly connected：強連通tree：樹directed tree：有向樹asymmetric：非對稱的leaf：葉（結(jié)點）internal vertex：分支結(jié)點root：根結(jié)點rooted tree：（有）根樹level：級height：高度parent：父結(jié)點child：子結(jié)點siblings：兄弟結(jié)點ancestor：祖先descendant：后代binary tree：二元（叉）樹m-ary tree：m元（叉）樹sp

4、anning tree：生成樹，支撐樹Euler cycle：歐拉回路Euler path：歐拉通路incidence matrix：關(guān)聯(lián)矩陣adjacency matrix：鄰接矩陣representation matrix：表示矩陣Warshalls algorithm：Warshall算法adjacency list representation：鄰接鏈表表示本章內(nèi)容及教學(xué)要點：6.1Graphs教學(xué)內(nèi)容：graph，vertex，edge，adjacent，incident，endpoints，loop，multigraph，pseudograph，degree，isolated ve

5、rtex，subgraph，path，simple path，connected，component，cycle，simple cycle，complete graph，bipartite graph6.2Directed Graphs教學(xué)內(nèi)容：directed graph，directed edge，outdegree，indegree，directed path，underlying graph，strongly connected 6.3 Trees教學(xué)內(nèi)容：tree，directed tree，leaf，internal vertex，root，rooted tree，binary t

6、ree，m-ary tree，spanning tree6.4 Euler Paths and Cycles教學(xué)內(nèi)容：Euler cycle，Euler path6.5 Incidence and Adjacency Matrices教學(xué)內(nèi)容：adjacency matrix定理證明及例題解答Graph theory is an old subject with many modern applications. Its basic ideas were introduced in the eighteenth century by the great Swiss mathematician

7、Leonard Euler. He used graphs to solve the famous Konisberg bridge problem. Graphs are used to solve problems in many fields. For instance, graphs can be used to determine whether a circuit can be implemented on a planar board. Graphs can be used to study the structure of the WWW. We can determine w

8、hether two computers are connected by a communications link using graph models of computer networks. Weighted graphs can be used to solve problems such as finding the shortest path between two cities in a transportation network. We can also use graphs to schedule exams and assign channels to televis

9、ion stations.圖論是以圖為研究對象的數(shù)學(xué)分支. 圖論中的圖指的是一些點以及連接這些點的線的總體. 通常用點代表事物，用連接兩點的線代表事物間的關(guān)系. 圖論則是研究事物對象在上述表示法中具有的特征與性質(zhì)的學(xué)科. 在自然界和人類社會的實際生活中，用圖形來描述和表示某些事物之間的關(guān)系既方便又直觀. 例如，國家用點表示，有外交關(guān)系的國家用線連接代表這兩個國家的點，于是世界各國之間的外交關(guān)系就被一個圖形描述出來了. 另外我們常用工藝流程圖來描述某項工程中各工序之間的先后關(guān)系，用網(wǎng)絡(luò)圖來描述某通訊系統(tǒng)中各通訊站之間信息傳遞關(guān)系，用開關(guān)電路圖來描述IC中各元件電路導(dǎo)線連接關(guān)系(芯片設(shè)計)等等.

10、事實上，任何一個包含了某種二元關(guān)系的系統(tǒng)都可以用圖形來模擬. 由于我們感興趣的是兩對象之間是否有某種特定關(guān)系，所以圖形中兩點之間連接與否最重要，而連接線的曲直長短則無關(guān)緊要. 由此經(jīng)數(shù)學(xué)抽象產(chǎn)生了圖的概念. 研究圖的基本概念和性質(zhì)、圖的理論及其應(yīng)用構(gòu)成了圖論的主要內(nèi)容. 計算機中數(shù)據(jù)結(jié)構(gòu)離不開數(shù)組、串、鏈表、樹和圖. 圖是計算機中數(shù)據(jù)表示、存儲和運算的基礎(chǔ).圖論的產(chǎn)生和發(fā)展經(jīng)歷了二百多年的歷史，大體上可分為三個階段：第一階段是從1736年到19世紀中葉. 當時的圖論問題是盛行的迷宮問題和游戲問題. 最有代表性的工作是著名數(shù)學(xué)家Euler于1736年解決的哥尼斯堡七橋問題(Konigsberg

11、Seven Bridges Problem). 東普魯士的哥尼斯堡城(現(xiàn)今是俄羅斯的加里寧格勒，在波羅的海南岸）位于普雷格爾(Pregel)河的兩岸，河中有一個島，于是城市被這條河、它的分支和島分成了四個部分，各部分通過7座橋彼此相通. 該城的居民喜歡在星期日繞城散步. 久而久之就產(chǎn)生了這樣一個問題：能不能設(shè)計一條散步的路線，使得一個人從家里（或從四部分陸地任一塊）出發(fā)，經(jīng)過每座橋恰好一次再回到家里？這就是有名的哥尼斯堡七橋問題. 哥尼斯堡七橋問題看起來并不復(fù)雜，因此立刻吸引所有人的注意，但是實際上很難解決. 瑞士數(shù)學(xué)家(Leonhard Euler)注意到了這個問題，并在1736年發(fā)表的“哥

12、尼斯堡七橋問題”的文章中解決了這個問題. 這篇論文被公認為是圖論歷史上的第一篇論文，Euler也因此被譽為圖論之父. 歐拉把七橋問題抽象成數(shù)學(xué)問題一筆畫問題，并給出一筆畫問題的判別準則，從而判定七橋問題不存在解. Euler是這樣解決這個問題的：將四塊陸地表示成四個點，橋看成是對應(yīng)結(jié)點之間的連線，則哥尼斯堡七橋問題就變成了：從A，B，C，D任一點出發(fā)，通過每邊一次且僅一次返回原出發(fā)點的路線(回路)是否存在？Euler證明這樣的回路是不存在的. 第二階段是從19世紀中葉到1936年. 一開始，圖論的理論價值似乎不大，因為圖論主要研究一些娛樂性的游戲問題：迷宮問題、博弈問題、棋盤上馬的行走線路問題

13、. 但是隨著一些圖論中的著名問題如四色問題(1852年)和Hamilton環(huán)游世界問題(1856年)的出現(xiàn)，出現(xiàn)了以圖為工具去解決其它領(lǐng)域中一些問題的成果. 1847年德國的克?；舴?G.R.Kirchoff)將樹的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)研究. 1857年英國的凱萊(A.Cayley)也獨立地提出了樹的概念，并應(yīng)用于有機化合物分子結(jié)構(gòu)（C2H2n+2的同分異構(gòu)物數(shù)目）的研究中. 1936年匈牙利的數(shù)學(xué)家哥尼格(D.Konig)寫出了第一本圖論專著有限圖與無限圖的理論(Theory of directed and Undirected Graphs). 標志著圖論成為一門獨立學(xué)科. 第

14、三階段是1936年以后. 由于生產(chǎn)管理、軍事、交通運輸、計算機和通訊網(wǎng)絡(luò)等方面的大量問題的出現(xiàn)，大大促進了圖論的發(fā)展. 特別是電子計算機的大量應(yīng)用，使大規(guī)模問題的求解成為可能. 實際問題如電網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、電路設(shè)計、數(shù)據(jù)結(jié)構(gòu)以及社會科學(xué)中的問題所涉及到的圖形都是很復(fù)雜的，需要計算機的幫助才有可能進行分析和解決. 目前圖論在物理、化學(xué)、運籌學(xué)、計算機科學(xué)、電子學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、社會科學(xué)及經(jīng)濟管理等幾乎所有學(xué)科領(lǐng)域都有應(yīng)用. 6.1 Graphs定義6.1.1 A graph(無向圖，圖) is a finite set V called the vertex set(頂點集) and

15、 a collection E of two-element subsets of V called the edge set(邊集). An element of E is called an edge(邊). A graph is denoted by G(V,E). The elements a and b of V are joined or connected(連接) by the edgea,b if a,bE.Graphs are usually represented by diagrams using dots for vertices and lines between t

16、heir dots for edges.定義6.1.2 If a,bE is an edge in a graph G(V,E), then the vertices a and b are called the endpoints(終點) of the edgea,b. The edge a,b is also said to be incident on(關(guān)聯(lián)于) the vertices a and b. Conversely, the vertices a and b are said to be incident on(關(guān)聯(lián)于) the edge a,b. Two vertices

17、a and b are adjacent(鄰接結(jié)點) if they are endpoints of an edge. Two edges are adjacent(鄰接邊) if they are incident on a common vertex.例6.1.1The graph G with V=a,b,c and E=a,b,b,c.例6.1.2The graph G with V=a,b,c,d,e and E=a,b,a,e,b,e,b,d,b,c,c,d).定義6.1.3 The graph G(V,E) is called a simple graph(簡單圖) if th

18、ere is at most one edge between any two vertices and no edge from a vertex to itself. An edge from a vertex to itself is called a loop(自回路，環(huán)). Edges between two vertices are called parallel edges(平行邊，多重邊). In a multigrpah(多重圖，多圖), there may be parallel edges between two vertices. In a pseudograph(偽圖

19、), there may include parallel edges between two vertices and loops. 定義6.1.4 The degree(度數(shù)) of a vertex v, denoted by deg(v), is the number of edges that are incident on the vertex. A vertex with degree 0 is called isolated(孤立的).在一個圖中，以v為端點的邊數(shù)稱為v的度數(shù)，記為deg(v), 度數(shù)為0的頂點稱為孤立結(jié)點.Euler握手定理定理6.1.1 (The Hands

20、haking Theorem) Let G(V,E) be a graph. Thendeg(v)=2|E|.That is, the sum of the degrees of the vertices of a graph is always even.一個圖的所有結(jié)點的度數(shù)之和是邊數(shù)的兩倍，從而是偶數(shù). 定理6.1.2 In any graph, there is an even number of vertices whose degree is odd.在任何圖中，度數(shù)為奇數(shù)的結(jié)點為偶數(shù)個. 證明 定理6.1.2 定義6.1.5 A graph G(V,E) is a subgrap

21、h(子圖) of a graph G(V,E), denoted by G(V,E)G(V,E), if VV and EE. 定義6.1.6 Let G(V,E) be a graph with vertices v0,vkV. A path (通路，路徑) of length k from v0 to vk or between v0 and vk is a sequence v0e1v1e2v2e3v3vk-1ekvk such that v0,v1,vkV, e1,e2,ekE and ei=vi-1,vi. For simplicity, we denote this path as

22、 v0v1v2v3vk-1vk. A simple path(基本路徑) from v0 to vk is a path in which no vertex is repeated.在圖G(V,E)中，設(shè)v0,v1,vkV，e1,e2,ekE，其中vi-1，vi是邊ei的端點(i=1,2,k). 稱v0e1v1e2v2e3v3vk-1ekvk為從頂點v0到vk的通路(路徑)，v0和vm分別稱為該通路的起點和終點；稱通路上的邊數(shù)k為該通路的長度.若通路經(jīng)過的頂點各不相同，則稱該通路為基本通路. 例6.1.3求下圖的通路、基本通路. 解 例6.1.3定義6.1.7 A graph G is ca

23、lled connected(連通的) if there is a path from any vertex to any other vertex in the graph. Otherwise, the graph is disconnected(不連通的). 給定無向圖G(V,E)且u,vV. 若存在從u到v的通路，則稱從u到v是可達的或稱u可達v. 若G的任何兩個頂點是相互可達的，則稱G是連通圖，否則稱G是不連通圖.定理6.1.3 Let G(V,E) be a graph. If there is a path from a vertex u to a vertex v, then

24、there is a simple path from u to v.證明 定理6.1.3 事實上，在一個具有n 個頂點的無向圖中，任何基本通路的長度均不大于n-1.推論 A graph G is connected if and only if there is a simple path between any two vertices in G.定義6.1.8 Let G(V,E) be a graph. A subgraph G of G is a component (連通分支) of G if (1) G is a nonempty connected graph and(2) i

25、f G” is a connected subgraph of G and GG” then G=G”. 當G是一個非連通圖時，它的獨立的不同連通部分稱為它的連通分支.定義6.1.9 Let G(V,E) be a graph. A cycle(回路) is a path of length greater than zero from a vertex to itself with no repeated edges. A simple cycle(基本回路) is a cycle from a vertex v to itself such that v is the only verte

26、x that is repeated.例6.1.4求下圖的回路、基本回路. 解 例6.1.4定義6.1.10 A graph is a complete graph(無向完全圖) if there is an edge between every two distinct vertices. A complete graph with n vertices is denoted by Kn. 例6.1.5K2，K3，K4，K5. 解 例6.1.5.定義6.1.11 Let G(V,E) be a graph. G is called a bipartite graph (二部圖，偶圖) if

27、its vertex set V can be partitioned into two disjoint sets A and B such that every edge in the graph connects a vertex in A and a vertex in B(so that no edge in G connects either two vertices in A or two vertices in B).A bipartite graph is called a complete bipartite graph(完全二部圖) Km,n if A contain m

28、 vertices, B contains n vertices, and for every aA,bB, a,bE. Thus, for every aA and bB, there is an edge connecting them.給定簡單無向圖G(V，E)，V= AB，AB=. 若G中任一條邊的兩個端點，一個屬于A，另一個屬于B，則稱G為二部圖(偶圖) . 若|A|=m，|B|=n，且對任意uA，vB，u與v有邊相連，則稱G為完全二部圖，記為Km,n.ASSIGNMENTS：PP140：2，4，6，8，10，12，18，20，24，26，28，306.2Directed Graph

29、s定義6.2.1 A directed graph or digraph(有向圖) G(V,E), consists of a set V of vertices, together with a set E of ordered pairs of V called the set of directed edges(有向邊). If (a,b) E, then a is called the initial vertex(起點) of (a,b) and b is called the terminal vertex(終點).The edge (a,b) of a digraph is de

30、noted on the diagram by an arrow from a to b.例6.2.1 The digraph G with V=a,b,c and E=(a,b),(b,c),(c,b),(c,a).例6.2.2 The digraph G with V=a,b,c,d and E=(a,b),(b,c),(c,c),(b,d),(d,b),(c,d),(d,a).定義6.2.2 The outdegree(出度) of a vertex v, denoted by outdeg(v), is the number of edges for which v is the in

31、itial vertex. The indegree(入度) of a vertex v, denoted by indeg(v), is the number of edges for which v is the terminal vertex. If indeg(v)=0, then v is called a source(源). If outdeg(v)=0, then v is called a sink(匯).例6.2.3 The digraph G with V=a,b,c,d,e and E=(a,b),(a,b),(a,c),(b,c),(b,e),(c,d),(c,e),

32、(d,e).indeg(a)=0, indeg(b)=1, indeg(c)=2, indeg(d)=2, indeg(e)=3outdeg(a)=3, outdeg(b)=2, outdeg(c)=2, outdeg(d)=1, outdeg(e)=0a is a source and e is a sink. Similar to graphs, directed multigraphs, labeled digraphs and directed subgraphs can be defined.定義6.2.3 A directed path(有向通路) of length k from

33、 a to b is described by a sequence of vertices v0v1v2v3vk-1vk where v0=a and vk=b, and (vi-1,vi) is a directed edge for 1ik. 例6.2.4 The digraph G with V=a,b,c,d,e and E=(a,b),(a,b),(a,c),(b,c),(b,e),(c,d),(c,e),(d,e).定義6.2.4 Let G(V,E) be a digraph and G(V,E) be a directed subdigraph of G with the l

34、oops removed,i.e. E=E-(v,v): vV. Let E” be the symmetric closure of E and Es be the set of edges representing the relation E”. Then the graph Gs(V,Es) is called the underlying graph(底圖) of G.定義6.2.5 A digraph G(V,E) is connected(弱連通的) if its underlying graph is connected. A digraph G(V,E) is strongl

35、y connected(強連通的) if for every pair of vertices a,bV, there is a directed path from a to b.例6.2.5 PP144-145: 19, 21,27,29.定理6.2.1 (The Handshaking Theorem) Let G(V,E) be a digraph. Thendeg(v)=2|E|,outdeg(v)=|E|,indeg(v)=|E|.ASSIGNMENTS：PP143-145：4，6，8，20，22，24，26，28，346.3 Trees樹是圖論中一個既簡單又非常重要的概念，在計算

36、機科學(xué)中應(yīng)用很廣泛，是一種基本的數(shù)據(jù)結(jié)構(gòu)和表示方法. 1847年德國的克?；舴?G.R.Kirchoff)將樹的概念和理論應(yīng)用于工程技術(shù)的電網(wǎng)絡(luò)研究. 1857年英國的凱萊(A.Cayley)也獨立地提出了樹的概念，并應(yīng)用于有機化合物分子結(jié)構(gòu)（C2H2n+2的同分異構(gòu)物數(shù)目）的研究中.定義6.3.1 A tree(無向樹，樹) is a connected graph that has no cycles. The vertices of degree 1 are called leaves(葉結(jié)點) and other vertices are called internal vertice

37、s(分支結(jié)點).樹是一個沒有回路的連通無向圖. 若一個不連通的無向圖的所有連通分支都是樹，則稱該無向圖為森林.定義6.3.2 A directed tree(有向樹) is a loop-free digraph, whose underlying graph is a tree.In a directed tree, if there is a path from a vertex a to a vertex b, it is unique. 例6.3.1 無向樹.解 例6.3.1定理6.3.1 For any two vertices a and b of a tree T, there

38、is a unique simple path from a to b.定理6.3.2 If for any two vertices a and b in a graph G there is a unique simple path from a to b, then G is a tree.We can select a vertex as the root(根) of the tree. Then the tree has become a rooted tree(根樹). We can also change a rooted tree to a directed tree, cal

39、led the rooted directed tree derived from the rooted tree(從一棵根樹導(dǎo)出的有向根樹).定義6.3.3 In a rooted tree T, the level(級) of a vertex v is the length of the unique path from the root to v. The height(樹高) of a tree is the length of the longest path from the root to a leaf. In a rooted directed tree, if there

40、is a directed edge from u to v, then the vertex u is the parent(父結(jié)點) of v and v is the child(子結(jié)點) of u. If u is the parent of v and v, then v and v are called siblings(兄弟結(jié)點). If there is a directed path from vertex u to vertex v, then u is called an ancestor(祖先結(jié)點) of v and v is called a descendant(后

41、代結(jié)點) of u. If the largest outdegree for any vertex of the tree is m, then the tree is called an m-ary tree(m叉樹). In particular, if m=2, then the tree is called a binary tree(二叉樹).定理6.3.3 A tree with v vertices has v-1 edges.定理6.3.4 If a connected graph G has e edges and v vertices and v=e+1, then G

42、is a tree.定理6.3.5 A tree with at least one edge has at least two vertices with degree 1.定義6.3.4 A tree T is a spanning tree for a graph G, if T is a subgraph of G, if every vertex in G is a vertex in T.定理6.3.6 Every connected graph has a spanning tree. ASSIGNMENTS：PP148-150：2，4，10，12，18，20，22，24，26，

43、28，30，42，44，466.4 Euler Paths and Cycles 定義6.4.1 Let G(V,E) be a graph. A cycle that includes all of the edges and the vertices of G is called an Euler cycle(歐拉回路). When this occurs, we say that the graph G has an Euler cycle.給定無向圖G(V,E)，通過G中的所有邊和頂點的回路稱為歐拉回路. 存在歐拉回路的圖稱為歐拉圖.例6.4.1哥尼斯堡七橋問題: 這是否是一個歐拉圖?

44、例6.4.2一筆畫問題. 定理6.4.1 A graph with more than one vertex has an Euler cycle if and only if it is connected and every vertex has even degree.至少有兩個頂點的無向圖G是歐拉圖G連通且所有結(jié)點的度數(shù)都是偶數(shù).證明 定理6.4.1例6.4.3這些圖是否是歐拉圖?解 例6.4.3例6.4.4下列圖形是否可以一筆畫成. 解 例6.4.4定義6.4.2 Let G(V,E) be a graph. A path that includes each of the edge

45、s of G exactly once is called an Euler path(歐拉通路). When this occurs, we say that the graph G has an Euler path.給定無向圖G(V,E)，通過G中的所有邊恰好一次的通路稱為歐拉通路. 我們稱該圖存在歐拉通路.定理6.4.2 A connected graph has an Euler path if and only if exactly two vertices have odd degree.無向連通圖G有歐拉通路G恰好只有兩個結(jié)點的度數(shù)是奇數(shù).定義6.4.3 Let G(V,E)

46、be a digraph. A directed cycle that includes all of the edges and the vertices of G is called an Euler cycle(歐拉回路). When this occurs, we say that the graph G has an Euler cycle.給定有向圖G(V,E)，通過G中的所有邊和頂點的有向回路稱為歐拉回路. 存在歐拉回路的圖稱為歐拉圖.定理6.4.3 A digraph has an Euler cycle if and only if it is strongly connec

47、ted and the indegree of every vertex is equal to its outdegree.有向圖G是歐拉圖G強連通且所有頂點的出度等于入度.定理6.4.4 A strongly connected digraph has an Euler path if and only if there is a vertex whose indegree is equal to its outdegree+1, and there is a vertex whose indegree is equal to its outdegree-1, and the indegr

48、ee of all other vertices is equal to its outdegree.強連通的有向圖G有歐拉通路G恰有一個頂點其出度比入度多1，另一個頂點其出度比入度少1，且所有其他頂點的出度等于入度.ASSIGNMENTS：PP148-150：2，6，10，126.5 Incidence and Adjacency MatricesHow to represent a graph in a computer?定義6.5.1 Let G(V,E) be a graph(digraph). Let B be a matrix whose rows are labeled by t

49、he vertices of G and whose columns are labeled by the same vertices in the same order. Bij=1 or 0 whether there is an edge from the ith vertex to the jth vertex. The matrix B is called the adjacency matrix(鄰接矩陣) of G.鄰接矩陣的一個重要應(yīng)用是尋圖中固定長度的通路.例6.5.1求下列圖的鄰接矩陣.解 例6.5.1Boolean matrix operations(布爾矩陣運算)A Boolean matrix is an m×n matrix whose entries are either zero or one. Let A=a and B=b be m×n Boolean matrices. We define AB=C=c, the join of A and B(布爾矩陣的并), by and AB=C=d, the meet of A and B(布爾矩陣的交), by 例6.5.2 Let A= and B=. We haveAB= , AB=Let A=aij is an m×p Boolea