《链接版第六章无向图、有向图和树》由会员分享，可在线阅读，更多相关《链接版第六章无向图、有向图和树（24页珍藏版）》请在金锄头文库上搜索。
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：
2、孤立结点subgraph：子图 path：通路，路径 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 multigrap
3、h：有向多重图labeled directed 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：二元（
4、叉）树m-ary tree：m元（叉）树spanning 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，pseudogr
5、aph，degree，isolated vertex，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，roo
6、t，rooted tree，binary tree，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 grea
7、t Swiss mathematician 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 W
8、WW. We can determine whether 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 assi
9、gn channels to television stations.图论是以图为研究对象的数学分支. 图论中的图指的是一些点以及连接这些点的线的总体. 通常用点代表事物，用连接两点的线代表事物间的关系. 图论则是研究事物对象在上述表示法中具有的特征与性质的学科. 在自然界和人类社会的实际生活中，用图形来描述和表示某些事物之间的关系既方便又直观. 例如，国家用点表示，有外交关系的国家用线连接代表这两个国家的点，于是世界各国之间的外交关系就被一个图形描述出来了. 另外我们常用工艺流程图来描述某项工程中各工序之间的先后关系，用网络图来描述某通讯系统中各通讯站之间信息传递关系，用开关电路图来描述IC
10、中各元件电路导线连接关系(芯片设计)等等. 事实上，任何一个包含了某种二元关系的系统都可以用图形来模拟. 由于我们感兴趣的是两对象之间是否有某种特定关系，所以图形中两点之间连接与否最重要，而连接线的曲直长短则无关紧要. 由此经数学抽象产生了图的概念. 研究图的基本概念和性质、图的理论及其应用构成了图论的主要内容. 计算机中数据结构离不开数组、串、链表、树和图. 图是计算机中数据表示、存储和运算的基础.图论的产生和发展经历了二百多年的历史，大体上可分为三个阶段：第一阶段是从1736年到19世纪中叶. 当时的图论问题是盛行的迷宫问题和游戏问题. 最有代表性的工作是著名数学家Euler于1736年解
11、决的哥尼斯堡七桥问题(Konigsberg Seven Bridges Problem). 东普鲁士的哥尼斯堡城(现今是俄罗斯的加里宁格勒，在波罗的海南岸）位于普雷格尔(Pregel)河的两岸，河中有一个岛，于是城市被这条河、它的分支和岛分成了四个部分，各部分通过7座桥彼此相通. 该城的居民喜欢在星期日绕城散步. 久而久之就产生了这样一个问题：能不能设计一条散步的路线，使得一个人从家里（或从四部分陆地任一块）出发，经过每座桥恰好一次再回到家里？这就是有名的哥尼斯堡七桥问题. 哥尼斯堡七桥问题看起来并不复杂，因此立刻吸引所有人的注意，但是实际上很难解决. 瑞士数学家(Leonhard Euler
12、)注意到了这个问题，并在1736年发表的“哥尼斯堡七桥问题”的文章中解决了这个问题. 这篇论文被公认为是图论历史上的第一篇论文，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 Gra
14、phs). 标志着图论成为一门独立学科. 第三阶段是1936年以后. 由于生产管理、军事、交通运输、计算机和通讯网络等方面的大量问题的出现，大大促进了图论的发展. 特别是电子计算机的大量应用，使大规模问题的求解成为可能. 实际问题如电网络、交通网络、电路设计、数据结构以及社会科学中的问题所涉及到的图形都是很复杂的，需要计算机的帮助才有可能进行分析和解决. 目前图论在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域都有应用. 6.1 Graphs定义6.1.1 A graph(无向图，图) is a finite set V called t
15、he vertex set(顶点集) and 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 their 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(关联于)
