图论自学指导书

《图论自学指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、图论自学指导书图论是一门应用十分广泛其内容非常丰富的数学分支，在物理、化学、牛物、计算机科学、工程技术和经济管理等各个领域都可以找到图论的足迹。它起源很早，瑞土数学家欧拉在1736年解决了当时颇为有名的一个实际问题，哥尼斯堡七桥问题，从而使他成为图论的创始人。由于基础的图论不需要高深的数学知识，具有一定的初等性，而且图论的思想对于提高分析、解决问题的能力是I-分有益的，所以深受数学竟赛命题者的青睐。在数学竟赛屮，经常出现一些以图论为背景的试题，这些试题题型新颖，内容生动诱人。fl•在新课标中也已将图论列入中学数学选修课Z内。图论研究的対象是图，但这里所讨

2、论的图并不是儿何学中的图，而是客观世界中某些貝体事物间某种二元关系的一个数学抽彖，用顶点代表事物，用边表示各事物间的二元关系，如果所讨论的某两个事物之间有相应的二元关系，我们就在相应的两个顶点之间连一条边,这种山顶点及连接这些顶点的边所组成的图就是我们图论中所研究的图。根据图的构造，图论方法來解决数学竟赛题的范围和基本思路是：若问题小所给的条件和结论是讨论关于某些対象之间的二元关系，那我们基本上可以用图的方法來解决该问题。其方法是用图的顶点表示问题中的对彖，某两个事物Z间冇问题中所关注的二元关系，我们就在相应的两个顶点Z间连一条边。这样，就把一个具体问题

3、抽彖成为图论问题，我们就可以用图论的理论和方法进行探讨。但是对于中学数学竞赛，-•般并不要求学牛直接用图论的定理去解题，而是运用图论中常见的处理方法(如反证法、数学归纳法、极端原理、抽屉原理、分类讨论、优化假设等)去分析图中的逻辑关系与数量关系，最终找出问题的答案。用图论思想求解问题冇两个较为明显的优点：其一nJ将实际问题转化为一个数学问题；其二可将抽彖的内在关系转化为图的外显关系。第一章图论的基本概念通常用G二(V,E)表示图，其屮V(G)={vbv2,表示顶点集合，E(G)={ei,e2,,eq}表示边的集合。若边e连接顶点u与v,则记e=uv=vu

4、,且称u与v相邻和e与u(v)关联，与同一•个顶点关联的若T•条边称为是相邻的，两个端点重合为一个顶点的边称为是环，若两个顶点ZI'可有k(k$2)条边连接，就称这些边为重边。没有环也没有重边的图称为简单图。

5、V(G)

6、称为图G的顶点数或阶，记为p(G),

7、E(G)

8、称为图G的边数，记为q(G)op(G)和q(G)都是有限的图称为有限图，这里仅讨论有限图。为了方便，记Ng(v)={u:ugV(G),u与v相邻}称为顶点v的邻域。在图G中，与顶点v关联的边的条数(环算2次)称为v的度数，记为血(v)或d(v)分别用5(G)和4(G)表示图G的最大度和最小度

9、。当j(G)=A(G)时，称G为正则图。上述所讨论的图实质上给出了顶点Z间的一种二元关系。因而在客观世界中，一些事物间若带有某种二元关系，就可以用上血所讨论的一个图来描述这些事物间的相互关系。像人与人之朋友关系、同学关系、相互认识关系等。但上血所讨论的这种关系只能是貝有对称性的二元关系。而在现实生活屮，有许多关系是非对称的，如认识关系，甲认识乙并不意味看乙认识甲。在处理交通流问题时，会碰到单行道路。像这些就不能简单地用前血•所讨论的图来表示，为此需引进冇向图的概念。每条边带有方向的图称为有向图。有向图用D=(V,A)表示，若有向边(也称为弧)2连接U到V

10、,则记为a=(u,v),u称为a的起点，v称为a的终点。在有向图D'

11、l以u为起点的弧的数目称为u的出度，记为d+(u)；以u为终点的弧的数目称为u的入度，记为d_(u)o称cT(u)+旷(u)二d(u)为顶点11的度数。我们不难得到关于度数与弧数的一个关系式本章主要的定理是定理1.3.1任何一个n阶图G,均有7?)=2q(G)1=1推论1.3.2任何一个图G的奇点个数均为偶数。重点是度与边数间的关系。定理1.3.5对每个有向图D=(V,A),有Xd*(u)=£d(u)=m(D)这里对D中所有的顶点求和。若对于图G二(V,E)和H二(V】,EJ,有V.o

12、V,E.oE,就称H是G的子图，记为HgG。若HoG且V(H)二V(G),就称H为G的生成子图。每一对顶点都有边连接的简单图称为完全图，记为KI1O重点是度与边数间的关系和了图、生成了图概念。一般来说，只要相应的问题讨论的是度数与边数间的关系，就可以用定理1.3.1来考虑。若是有向图，则用定理1.3.5来考虑。由于图论中关心的是集合中元素间的二元关系，因此対于一个图G,G的顶点的位置和边的形状都是无关紧要的。如卜•面两个外形完全不同的图，在图论屮看成是相同的两个图。利用上述这些非常简单的棊木概念，可以帮助我们思考和解决一些问题。下面就是其中的几个例题。例

13、1.(1996年全国数学联赛)有/7(/7>6)个人聚会，已知每个人至少认识其屮