离散数学之图论.doc

《离散数学之图论.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第四篇图论自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题。如迷宫问题、匿门博奕问题、棋盘上马的路线问题、四色问题和哈密顿环球旅行问题等，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。1847年克希霍夫（Kirchhoff）第一次把图论用于电路网络的拓扑分析，开创了图论面向实际应用的成功先例。此后，随着实际的需要和科学技术的发展，在近半个世纪内，图论得到了迅猛的发展，已经成了数学领域中最繁茂的分支学科之一。尤其

2、在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。图论研究的课题和包含的内容十分广泛，专门著作很多，很难在一本教科书中概括它的全貌。作为离散数学的一个重要内容，本书主要围绕与计算机科学有关的图论知识介绍一些基本的图论概论、定理和研究内容，同时也介绍一些与实际应用有关的基本图类和算法，为应用、研究和进一步学习提供基础。71第4-1章无向图和有向图学习要求：仔细领会和掌握图论的基本概论

3、、术语和符号，对于图论研究的一些最基本的课题，如道路问题、连通性问题和着色的问题等，应掌握主要的定理内容和证明方法以及基本的构造方法，以便为下一章研究提供理论工具。学习本章要用到集合和线性代数矩阵运算的知识，特别是集合数和矩阵秩的概念。§4-1-1图的基本概念图是用于描述现实世界中离散客体之间关系的有用工具。在集合论中采用过以图形来表示二元关系的办法，在那里，用点来代表客体，用一条由点a指向点b的有向线段来代表客体a和b之间的二元关系aRb，这样，集合上的二元关系就可以用点的集合V和有向线的集合E构成的二元组（V，E）来描述。同样的方法也可以用来描述其它的问题。当我们考察全球航运

4、时，可以用点来代表城市，用线来表示两城市间有航线通达；当研究计算机网络时，可以用点来表示计算机及终端，用线表示它们之间的信息传输通道；当研究物质的化学结构时，可以用点来表示其中的化学元素，而用线来表示元素之间的化学键。在这种表示法中，点的位置及线的长短和形状都是无关紧要的，重要的是两点之间是否有线相连。从图形的这种表示方式中可以抽象出图的数学概念来。一、图定义4-1-1.1一个（无向）图G是一个二元组（V（G），E（G）），其中V（G）是一个有限的非空集合，其元素称为结点；E（G）是一个以不同结点的无序对为元素，并且不含重复元素的集合，其元素称为边。我们称V（G）和E（G）分别是

5、G的结点集和边集。在不致引起混淆的地方，常常把V（G）和E（G）分别简记为V和E。我们约定，由结点u和结点v构成的无序对用uv（或vu）表示。根据图的这种定义，很容易利用图形来表示图。图形的表示方法具有直观性，可以帮助我们了解图的性质。在图的图形表示中，每个结点用一个小圆点表示，每条边uv用一条分别以结点v和u为端点的联线表示。图4-1-1.1中，（a）是图的图形表示；（b）是图H=71的图形表示。在某些情况下，图的图形表示中，可以不标记每个结点的名称。v1v2v3v4u1u2u3u4u5u6(a)(b)图4-1-1.1须注意，一个图的图形表示法可能不是唯一的。表示结点的圆点和表

6、示边的线，它们的相对位置是没有实际意义的。因此，对于同一个图，可能画出很多表面不一致的图形来。例如图4-1-1.1的（a）图还可以有图9—1.2中的两种图形表示。v4v3v1v2v2v3v4v1图4-1-1.2图G的结点数称为G的阶，用字母n的表示。G的边数用m表示，也可以表示成。一个边数为m的n阶图可简称为（n，m）—图。如图4-1-1.1的（a）和（b）分别表示一个（4，6）—图和一个（6，4）—图。若是图G的一条边，则称结点u和v是相互邻接的，并且说边e分别与u和v相互关联。若G的两条边和都与同一个结点关联时，称和是相互邻接的。二、图的变体若在定义4-1-1.1中去掉边集E

7、中“不含重复元素”的限制条件，则得到多重图的定义。在多重图中，允许两条或两条以上的边与同一对结点关联，这些边称为平行边。由于可能有多条边与同一个结点对相关联，为区别起见，有时也对各边加以编号。图4-1-1.3是多重图的一个例子。若在多重图的基础上，进一步去掉边是由不同结点的无序对表示的条件，即允许形如的边（称为环）存在，则得到广义图或伪图的定义。图4-1-1.4是伪图的一个例子。71v3v1v2v4v1v2v3v4v5图4-1-1.3图4-1-1.4为了区别于多重图和伪图，以后称