链接无向图有向图和树

1、CHAPTER 6 GRAPHS, DIRECTED GRAPHS, AND TREESGlossarygraph：（无向）图vertex set：顶点集edge set：边集endpoint：端点incident on：关联于adjacent：邻接simple graph：简单（无向）图loop：自回路，环multigraph：多（重）图 labeled graph：标号图pseudograph：伪图 utility：公用事业designing a chip：设计芯片planar graph：平面图degree：度 isolated vertex：孤立结点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：叶（结点）internal vertex：分支结点root：根结点rooted tree：（有）根树level：级height：高度parent：父结点child：子结点siblings：兄弟结点ancestor：祖先descendant：后代binary tree：二元（叉）树m-ary tree：m元（叉）树sp

4、anning tree：生成树，支撑树Euler cycle：欧拉回路Euler path：欧拉通路incidence matrix：关联矩阵adjacency matrix：邻接矩阵representation matrix：表示矩阵Warshalls algorithm：Warshall算法adjacency list representation：邻接链表表示本章内容及教学要点：6.1Graphs教学内容：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教学内容：directed graph，directed edge，outdegree，indegree，directed path，underlying graph，strongly connected 6.3 Trees教学内容：tree，directed tree，leaf，internal vertex，root，rooted tree，binary t

6、ree，m-ary tree，spanning tree6.4 Euler Paths and Cycles教学内容：Euler cycle，Euler path6.5 Incidence and Adjacency Matrices教学内容：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.图论是以图为研究对象的数学分支. 图论中的图指的是一些点以及连接这些点的线的总体. 通常用点代表事物，用连接两点的线代表事物间的关系. 图论则是研究事物对象在上述表示法中具有的特征与性质的学科. 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观. 例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了. 另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC中各元件电路导线连接关系(芯片设计)等等.

10、事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟. 由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要. 由此经数学抽象产生了图的概念. 研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容. 计算机中数据结构离不开数组、串、链表、树和图. 图是计算机中数据表示、存储和运算的基础.图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶. 当时的图论问题是盛行的迷宫问题和游戏问题. 最有代表性的工作是著名数学家Euler于1736年解决的哥尼斯堡七桥问题(Konigsberg

11、Seven Bridges Problem). 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被这条河、它的分支和岛分成了四个部分，各部分通过7座桥彼此相通. 该城的居民喜欢在星期日绕城散步. 久而久之就产生了这样一个问题：能不能设计一条散步的路线，使得一个人从家里（或从四部分陆地任一块）出发，经过每座桥恰好一次再回到家里？这就是有名的哥尼斯堡七桥问题. 哥尼斯堡七桥问题看起来并不复杂，因此立刻吸引所有人的注意，但是实际上很难解决. 瑞士数学家(Leonhard Euler)注意到了这个问题，并在1736年发表的“哥

12、尼斯堡七桥问题”的文章中解决了这个问题. 这篇论文被公认为是图论历史上的第一篇论文，Euler也因此被誉为图论之父. 欧拉把七桥问题抽象成数学问题一笔画问题，并给出一笔画问题的判别准则，从而判定七桥问题不存在解. Euler是这样解决这个问题的：将四块陆地表示成四个点，桥看成是对应结点之间的连线，则哥尼斯堡七桥问题就变成了：从A，B，C，D任一点出发，通过每边一次且仅一次返回原出发点的路线(回路)是否存在？Euler证明这样的回路是不存在的. 第二阶段是从19世纪中叶到1936年. 一开始，图论的理论价值似乎不大，因为图论主要研究一些娱乐性的游戏问题：迷宫问题、博弈问题、棋盘上马的行走线路问题

13、. 但是随着一些图论中的著名问题如四色问题(1852年)和Hamilton环游世界问题(1856年)的出现，出现了以图为工具去解决其它领域中一些问题的成果. 1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络研究. 1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物分子结构（C2H2n+2的同分异构物数目）的研究中. 1936年匈牙利的数学家哥尼格(D.Konig)写出了第一本图论专著有限图与无限图的理论(Theory of directed and Undirected Graphs). 标志着图论成为一门独立学科. 第

14、三阶段是1936年以后. 由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展. 特别是电子计算机的大量应用，使大规模问题的求解成为可能. 实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决. 目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用. 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(关联于) the vertices a and b. Conversely, the vertices a and b are said to be incident on(关联于) the edge a,b. Two vertices

17、a and b are adjacent(邻接结点) 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(自回路，环). 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(度数) 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为端点的边数称为v的度数，记为deg(v), 度数为0的顶点称为孤立结点.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.一个图的所有结点的度数之和是边数的两倍，从而是偶数. 定理6.1.2 In any graph, there is an even number of vertices whose degree is odd.在任何图中，度数为奇数的结点为偶数个. 证明 定理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)中，设v0,v1,vkV，e1,e2,ekE，其中vi-1，vi是边ei的端点(i=1,2,k). 称v0e1v1e2v2e3v3vk-1ekvk为从顶点v0到vk的通路(路径)，v0和vm分别称为该通路的起点和终点；称通路上的边数k为该通路的长度.若通路经过的顶点各不相同，则称该通路为基本通路. 例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、机科学中应用很广泛，是一种基本的数据结构和表示方法. 1847年德国的克希霍夫(G.R.Kirchoff)将树的概念和理论应用于工程技术的电网络研究. 1857年英国的凯莱(A.Cayley)也独立地提出了树的概念，并应用于有机化合物分子结构（C2H2n+2的同分异构物数目）的研究中.定义6.3.1 A tree(无向树，树) is a connected graph that has no cycles. The vertices of degree 1 are called leaves(叶结点) and other vertices are called internal vertice

37、s(分支结点).树是一个没有回路的连通无向图. 若一个不连通的无向图的所有连通分支都是树，则称该无向图为森林.定义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(从一棵根树导出的有向根树).定义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(父结点) of v and v is the child(子结点) of u. If u is the parent of v and v, then v and v are called siblings(兄弟结点). If there is a directed path from vertex u to vertex v, then u is called an ancestor(祖先结点) of v and v is called a descendant(后

41、代结点) 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连通且所有结点的度数都是偶数.证明 定理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恰好只有两个结点的度数是奇数.定义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.邻接矩阵的一个重要应用是寻图中固定长度的通路.例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