第1章图论简介

1.图论问题的起源、发展及应用

18世纪东普鲁士哥尼斯堡被普列戈尔河分为四块,它们通过七座桥相互连接,如下图.当时该城的市民热衷于这样一个游戏:“一个散步者怎样才能从某块陆地出发，经每座桥一次且仅一次回到出发点？”

七桥问题的分析

七桥问题看起来不难，很多人都想试一试，但没有人找到答案.后来有人写信告诉了当时的著名数学家欧拉.千百人的失败使欧拉猜想,也许那样的走法根本不可能.1876年,他证明了自己的猜想.Euler把南北两岸和四个岛抽象成四个点,将连接这些陆地的桥用连接相应两点的一条线来表示,就得到如下一个简图:欧拉的结论欧拉指出:一个线图中存在通过每边一次仅一次回到出发点的路线的充要条件是:1)图是连通的,即任意两点可由图中的一些边连接起来;2)与图中每一顶点相连的边必须是偶数.由此得出结论:七桥问题无解.欧拉由七桥问题所引发的研究论文是图论的开篇之作,因此称欧拉为图论之父.4.图的作用

图是一种表示工具.改变问题的描述方式,往往是创造性的启发式解决问题的手段.一种描述方式就好比我们站在一个位置和角度观察目标,有的东西被遮挡住了,但如果换一个位置和角度,原来隐藏着的东西就可能被发现.采用一种新的描述方式,可能会产生新思想.图论中的图提供了一种直观,清晰表达已知信息的方式.它有时就像小学数学应用题中的线段图一样,能使我们用语言描述时未显示的或不易观察到的特征、关系,直观地呈现在我们面前,帮助我们分析和思考问题,激发我们的灵感.5.图的广泛应用图的应用是非常广泛的,在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络,如河道网、灌溉网、管道网、公路网、铁路网、电话线网、计算机通讯网、输电线网等等.还有许多看不见的网络,如各种关系网,像状态转移关系、事物的相互冲突关系、工序的时间先后次序关系等等,这些网络都可以归结为图论的研究对象----图.其中存在大量的网络优化问题需要我们解决.还有象生产计划、投资计划、设备更新等问题也可以转化为网络优化的问题.6.基本的网络优化问题基本的网络优化问题有:最短路径问题、最小生成树问题、最大流问题和最小费用问题.图论作为数学的一个分支,已经有有效的算法来解决这些问题.当然这当中的有些问题也可以建立线性规划的模型,但有时若变量特别多,约束也特别多,用线性规划的方法求解效率不高甚至不能在可忍受的时间内解决.而根据这些问题的特点,采用网络分析的方法去求解可能会非常有效.例如,在1978年,美国财政部的税务分析部门在对卡特尔税制改革做评估的过程中,就有一个100,000个约束以上,25,000,000个变量的问题,若用普通的线性规划求解,预计要花7个月的时间.他们利用网络分析的方法,将其分解成6个子问题,利用特殊的网络计算机程序,花了大约7个小时问题就得到了解决.图论中的经典算法与现代智能算法结合解决NP难题

TSP是一个典型的NP问题，针对该问题很多情况下的求解，目前有很多智能算法，如遗传算法、神经网络、蚁群算法、免疫算法和粒子群算法等。在利用这些算法求解TSP时，有时为了降低时间复杂度和提高精确度，会同时使用图论中的一些经典算法，如迪克斯曲拉算法、Floy算法等。此外，在路由器的选址问题上，也常常利用图论中的一些经典算法。本学期主要内容第一章至第五章平时成绩要求:写一篇3000字左右关于图论的文章,主要是用图论知识解决一个实际问题.文章包括以下几个部分1.文题2.摘要3.关键词(3-5个)4.正文5.结论(一般要有运行结果及对结果的分析)6.参考文献(需在文中标出,5-8个)文章用A4打印,并加盖封面(上面有姓名,学号).

由于后续学习的需要,我们补充离散数学中的一些基本内容:关系与函数.预备知识二元关系本章学习目标：这一章主要学习集合内元素间的关系，这就是“关系”。关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数据库、情报检索、算法分析等都有很多应用。本章主要讨论二元关系理论。通过本章学习，同学们应掌握以下内容：

（1）关系的表示

（2）关系的性质和运算

（3）等价关系和集合的划分

（4）偏序关系复习集合中的几个定义幂集、集合的（对称）差、广义交与并等。1.1序偶与笛卡儿积1.2二元关系及其表示1.3关系的运算1.4关系的性质1.5关系的闭包1.6等价关系与集合的划分1.1.有序对与笛卡儿积定义1.1由两个固定次序的个体x，y组成的二元组称为一个有序对或序偶，记为<x，y>，其中x，y分别称为序偶的第一、二分量（或称第一、二元素）。定义1.2

两序偶<a，b>和<c，d>是相等的，当且仅当a=c，b=d；记作<a，b>=<c，d>。因此有序对<x,y>具有以下性质:1.当x≠y时,<x,y>≠<y,x>;2.<x,y>=<u,v>x=uy=v.例7.1.已知<x+2,4>=<5,2x+y>,求x和y.1.2笛卡儿积的概念定义1.3给定两个集合A和B，如果序偶的第一个分量是A中的一个元素，第二个分量是B中的一个元素，则所有这种序偶的集合称为集合A和B的笛卡儿积，简称为卡氏积，记为A×B，即A×B={<x，y>

x∈A∧y∈B}。1.3笛卡儿积的性质1.对任意集合A有:A=,A=;2.笛卡儿积运算一般不满足交换律:AB≠BA;3.一般也不满足交换律:(AB)C≠A(BC).4.笛卡儿积运算对并和交满足分配律,即设A，B，C为任意3个集合，则有（1）A×（B∪C）=（A×B）∪（A×C）（2）A×（B∩C）=（A×B）∩（A×C）（3）（A∪B）×C=（A×C）∪（B×C）（4）（A∩B）×C=（A×C）∩（B×C）5.ACBDA×BC×D.例1.3.设A={1,2},求P(A)A.例1.4.设A,B,C,D为任意集合,判断以下命题是否为真,并说明理由.(1)AB=ACB=C;(2)A-(BC)=(A-B)(A-C);(3)A=BC=DAC=BD.(4)存在集合A,使得A

AA.定义1.5设R是二元关系，由<x，y>

R的所有x组成的集合称为R的定义域，记作D（R），即D（R）={x׀

y（y

B∧<x，y>

R）}。由<x，y>

R的所有y组成的集合称为R的值域，记作R（R），即R（R）={y׀

x（x∈A∧<x，y>∈R）}。定义1.4.设A，B是两个集合，R是笛卡儿积A×B的任一子集，则称R为从A到B的一个二元关系，简称关系。特别当A=B时，则称R为A上的二元关系（或A上的关系）。

说明:集合A上的二元关系的数目依赖于A中的元素数.若∣A∣=n,则∣AA∣=n2,AA的子集就有个.每一个子集代表一个A上的二元关系,所以A上有个不同的二元关系.定义1.6.空关系,恒等关系和全关系.1.空关系:对于任何集合A,空集是AA的子集,叫做A上的空关系.2.恒等关系:设IA为集合A上的二元关系，且满足IA={<x，x>

x

A}，则称IA为集合A上的恒等关系。3.全关系EA定义为EA={<x,y>∣xAyA}=AA.例1.7.若A={1,2},求IA,EA.其他一些常见关系:LA={<x,y>∣x,yAx≤y},此处AR.DB={<x,y>∣x,yAx整除y},此处BZ*.R

={<x,y>∣x,yFxy},此处F是集合簇.例1.8.设A={1,2,3,4},下面定义的R都是A上的关系,试用列举法表示R.(1)R={<x,y>∣x是y的倍数};(2)R={<x,y>∣(x-y)2A};1.3.二元关系的表示方法:给出一个关系的方法有三种:集合表达式,关系矩阵和关系图.例1.5就是用集合表达式.

1.关系矩阵表示法:设给定集合A={a1，a2，…，an}，集合B={b1，b2，…，bm}，R为从A到B的一个二元关系，构造一个n×m矩阵。用集合A的元素标注矩阵的行，用集合B的元素标注矩阵的列，对于a∈A和b∈B，若<a，b>∈R，则在行a和列b交叉处标1，否则标0。这样得到的矩阵称为R的关系矩阵。2.关系图表示法:有限集的二元关系可以用有向图来表示，设集合A={a1，a2，…，an}，集合B={b1，b2，…，bm}，R为从A到B的一个二元关系，首先在平面上作出n个结点分别记作a1，a2，…，an，然后另外作出m个结点分别记作b1，b2，…，bm，如果a∈A、b∈B且<a，b>

R，则自结点a到结点b作出一条有向弧，其箭头指向b。如果<a，b>

R，则结点a和结点b之间没有线段联结。用这种方法得到的图称为R的关系图。解R的关系图，如图所示：例1.9A={1，2，3，4}，B={5，6，7}，R={<1，7>，<2，5>，<3，6>，<4，7>}，写出R的关系矩阵和作出R的关系图。解A上的关系图如下图所示。例1.9设A={1，2，3，4}，R={<1，2>，<2，2>，<3，3>，<4，1>}。写出R在A上的关系矩阵和画出R在A上的关系图。1.3.关系的运算

关系的基本运算有七种,分别定义如下:定义1.7.设R为二元关系(1)R中所有的有序对的第一元素构成的集合成为R的定义域,记作domR,形式化为dom(R)={x∣y(<x,y>R)}(2)R中所有的有序对的第二元素构成的集合成为R的值域,记作ranR,形式化为ran(R)={y∣x(<x,y>R)}(3)R的定义域和值域的并集称为R的域,记作fldR,形式化表示为:fldR=domRranR例1.10.设R={<1,2>,<1,3>,<2,4>},求domR,ranR,fldR.定义1.8.设R为二元关系,R的逆关系,简称R的逆,记作R-1,R-1={<x,y>∣<y,x>R}.关系的右复合运算定义1.9.设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，则R◦S称为R和S的复合关系，表示为R◦S={<x，z>

x∈A∧z∈C∧

y（y∈B∧<x，y>∈R∧<y，z>∈S}说明:上面这种定义方式称为右复合,类似可定义左复合:R◦S={<x，z>

x∈Z∧z∈A∧

y（y∈B∧<x，y>∈S∧<y，z>∈R}上面两种定义都是合理的,正如在交通规则中有的国家规定右行,有的国家规定左行一样,本书采用右复合的定义,请同学们注意两者的区别.思考一下:设R为A上的关系,则R◦IA,IA◦R及R之间有何关系?例1.10（1）A={1，2，3，4}，B={3，5，7}，C={1，2，3}，R={<2，7>，<3，5>，<4，3>}，S={<3，3>，<7，2>}，R◦S={<2，2>，<4，3>}。如图所示：（2）设R，S都是A上的关系，A={1，2，3，4}。R={<1，2>，<1，3>，<3，4>}，S={<1，1>，<2，2>，<3，3>，<4，4>}，即S为A上的恒等关系，则R◦S=S◦R=R。如图所示：（3）设R是A上的关系，S为A上的空关系，即S=

，则R◦S=S◦R=

。定理1.5设R是从集合A到集合B上的二元关系，S是从集合B到集合C上的二元关系，T是从集合C到集合D上的二元关系，则有：（1）R◦（S∪T）=R◦S∪R◦T（2）R◦（S∩T）

R◦S∩R◦T（3）（R∪S）◦T=R◦T∪S◦T（4）（R∩S）◦T

R◦T∩S◦T定理1.6设R是从A到B的关系，S是从B到C的关系，T是从C到D的关系，则有R◦（S◦T）=（R◦S）◦T。定义1.8设R是从A上的关系，n为整数，关系R的n次幂定义如下：（1）R0={<x，x>︱x∈A}=IA；（2）Rn+1=Rn◦R。从关系R的n次幂定义，可得出下面的结论：（1）Rn+m=Rn◦Rm；（2）（Rn）m=Rnm。定理1.7设R是从A到B的二元关系，S是从B到C的二元关系，则下面的式子成立：（R◦S）─1=S─1◦R─1证明<z，x>∈（R◦S）─1

<x，z>∈R◦S

y（y∈B∧<x，y>∈R∧<y，z>∈S）

y（y∈B∧<z，y>∈S─1∧<y，x>∈R─1）

<z，x>∈S─1◦R─1。所以，（R◦S）─1=S─1◦R─1。定义1.9.设R为二元关系,A是集合(1)R在A上的限制记为RA,其中RA={<x,y>∣xRyxA}(2)A在R下的像记作R[A],其中R[A]=ran(RA).显然有:RAR,R[A]ranR.例1.11.设R={<1,2>,<1,3>,<2,2>,<2,4>,<3,2>},则R{1}=R=R{2,3}=R[{1}]=R[]=R[{3}]=1.4.1关系的自反性和反自反性定义1.10设R是集合A上的二元关系，如果对于每个x

A，都有<x，x>

R，则称二元关系R是自反的。R在A上是自反的

x（x∈A

<x，x>∈R）定义1.11设R是集合A上的二元关系，如果对于每个x

A，都有<x，x>

R，则称二元关系R是反自反的。R在A上是反自反的

x（x∈A

<x，x>

R）1.4.2对称性和反对称性定义1.12设R是集合A上的二元关系，如果对于每个x，y∈A，当<x，y>∈R，就有<y，x>∈R，则称二元关系R是对称的。R在A上是对称的

x

y（x∈A∧y∈A∧<x，y>∈R

<y，x>∈R）

定义1.13

设R是集合A上的二元关系，如果对于每个x，y∈A，当<x，y>∈R和<y，x>∈R时，必有x=y，则称二元关系R是反对称的。

1.4.3.传递性定义1.14设R是集合A上的二元关系，如果对于任意x，y，z∈A，当<x，y>∈R，<y，z>∈R，就有<x，z>∈R，则称二元关系R在A上是传递的。R在A上是传递的

x

y

z（x∈A∧y∈A∧z∈A∧<x，y>∈R∧<y，z>∈R

<x，z>∈R）1.4.3.传递性

例1.13设A={a，b，c}，R，S，T是A上的二元关系，其中R={<a，a>，<b，b>，<a，c>}，S={<a，b>，<b，c>，<c，c>}，T={<a，b>}说明R，S，T是否为A上的传递关系。解根据传递性的定义知，R和T是A上的传递关系，S不是A上的传递关系，因为<a，b>∈R，<b，c>∈R，但<a，c>

R。1.4.4.关系性质的判定1．自反性的判定方法

定理1.9

设R是A上的二元关系，则R在A上是自反的当且仅当IA

R。

证明先证必要性。任取<x，y>，由于R在A上是自反的，则有<x，y>∈IA

x，y

A∧x=y

<x，y>∈R从而证明了IA

R。再证充分性。任取x

A，有x∈A

<x，x>∈IA

<x，x>∈R因此，R在A上是自反的。

1.4.4.关系性质的判定1．自反性的判定方法例设R={<a,a>,<a,b>,<b,b>,<b,c>,<c,a>,<c,c>,<c,d>,<d,d>}则R的关系矩阵如下，请问R有没有自反性？1．自反性的判定方法上例R的关系图为：3．对称性的判定方法R的关系图为：1.5关系的闭包

定义1.15

设R是集合A上的二元关系，如果有另一个关系R’满足：（1）R’是自反的（对称的、传递的）；（2）R’R；（3）对于A上任何包含R的自反的（对称的、传递的）关系R’’，有R’’R.则称关系为R的自反（对称、传递）闭包。

定理1.15设是集合A上的二元关系，则r（R）=R∪IA，定理1.16

设是集合A上的二元关系，则s（R）=R∪R–1定理1.17设R是集合A上的二元关系，则t（R）==R∪R2∪R3∪…定理1.18设A={a1，a2，…，an}，R是集合A上的二元关系，则存在一个正整数k≤n，使得t（R）=R∪R2∪R3∪…∪Rk1.6.等价关系与集合的划分

1.6.1.等价关系

定义1.16设R是非空集合A上的二元关系，如果有R是自反的、对称的和传递的，则称R是集合A上的等价关系.例1.23设集合A={a，b，c，d，}，R={<a，a>，<a，d>，<d，a>，<d，d>，<b，b>，<b，c>，<c，b>，<c，c>}。验证R是A上的等价关系。证明

写出R的关系矩阵1.6.等价关系与集合的划分

1.6.1.等价关系从关系矩阵主对角线元素都是1，可知R是自反的。关系矩阵是对称的，故R是对称的。从R的序偶表达式中，可以看出R是传递的，逐个检查序偶，如<a，a>，<a，d>∈R，有<a，d>∈R。<a，d>，<d，a>∈R，有<a，a>∈R，<d，a>，<a，d>∈R，有<d，d>∈R，…。故R是A上的等价关系。1.6.2.等价类定义1.17设R是非空集合A上的等价关系，对于任何a∈A，集合[a]R={x

x∈A且<a，x>∈R}称为元素a形成的R等价类。。定理1.22.设R是非空集合A上的等价关系，对于a，b

R，有<a，b>∈R当且仅当[a]R=[b]R。1.6.2.等价类

定义1.18

设R是集合A上的等价关系，等价类集合{[a]R

a∈A}称作A关于R的商集，记作A/R。定理1.22设R是非空集合A上的等价关系，对于a，b

R，有<a，b>∈R当且仅当[a]R=[b]R。定义1.19设A是一个集合，A1，A2，…，Am是它的子集，如果它满足下列条件：（1）所有Ai间均是分离的，亦即对所有i，j（i=1，2，…，m，j=1，2，…，m），如果i

j，则Ai∩Aj=

。（2）A1∪A2∪…∪Am=A则称A={A1，A2，…，Am}为集合A的一个划分，而A1，A2，…，Am称为这个划分的块。1.6.2.等价类定理1.23设R是非空集合A上的等价关系，确定了A的一个划分，该划分就是商集A/R。定理1.24

集合A的一个划分确定A上的一个等价关系。

定理1.25

设R1和R2是非空集合A上的等价关系，则R1=R2当且仅当A/R1=A/R2。1.6.2.等价类

例1.28设集合A={1，2，3，4，5}上的关系R为R={<1，1>，<1，2>，<2，1>，<1，3>，<3，1>，<2，2>，<2，3>，<3，2>，<3，3>，<4，4>，<4，5>，<5，4>，<5，5>}。解先写出相应的关系图：由此图可以看出关系R是等价关系，并且它的等价类分别为[1]R=[2]R=[3]R[4]R=[5]R由等价关系所构成的等价类在图中即是等价关系图中的完全图，所谓完全图是指图形中每个结点与其它结点有边联结的图形。

第一章图的基本概念(1)定义1图图G是一个三元组,记作其中(1)V(G)={v1,v2,…,vn},称为图G的结点集.(2)E(G)={e1,e2,…,em}是G的边集合,其中ei为{vj,vt}或<vj,vt>.若ei为{vj,vt},称ei为vj和vt为端点的无向边;若ei为<vj,vt>,称ei为vj为起点,vt为终点的有向边;(3)称为关联函数.第一章图的基本概念(2)定义2.邻接结点:关联于同一条边的两个结点.孤立结点:不与任何结点相连接的结点.邻接边:关联于同一顶点的两条边.环:两端点相同的边称为环或自回路.平行边:两个结点间方向相同的若干条边称为平行边或重边对称边:两端点相同但方向相反的两条有向边.第一章图的基本概念(3)定义3无向图:每条边都是无向边的图.有向图:每条边都是有向边的图.混合图:图中不全是有向边,也不全是无向边的图.平凡图:只有一个孤立结点的图.定义4.多重图:含有平行边的图.简单图:无环且无平行边的图.完全图:任何不同结点之间都有边相连的简单无向图.第一章图的基本概念(4)说明:(1)在简单图中,以x为起点y为终点的边至多有一条,因此,图中的边可直接用顶点对表示,而关联函数就可以直接表示在其边集中,故可简记为G=<V(G),E(G)>.(2)对无向图G,将G中的每条边用两条与e有相同端点对称边e和e’来代替后得到一个有向图D,这样得到的有向图D称为G的对称有向图.由此可见,无向图可视为特殊的有向图.(3)n个结点的完全图记为Kn,完全图Kn有条边.完全图的对称有向图称为完全有向图,记作.第一章图的基本概念(5)(4)图G的顶点个数还称为图G的阶.(5)对于有向图D,去掉边上的方向得到的无向图G称为D的基础图.反之,任一个无向图G,将G的边指定一个方向得到一个有向图D,称D为G的一个定向图.例证明:在任意六个人的聚会上,要么三个曾相识,要么三个不曾相识.证明:用A,B,C,D,E,F代表这六个人,若两人曾相识,则在代表该两人的顶点间连一条红边;否则连一条蓝边.于是,原问题等价于证明所得图中必含有同色三角形.考察某一顶点,设为F.与F关联的边中必有三条同色,不妨设它们是三条红边FA,FB,FC.再看三角形ABC.若它有一条红边,设为AB,则FAB是红边三角形;若三角形ABC没有红边,则其本身就是蓝边三角形.第二节图的顶点度和图的同构(1)定义1设G是任意图,x为G的任意结点,与结点x关联的边数(一条环计算两次)称为x的度数.记作deg(x)或d(x).定义2设G为无向图,对于G的每个结点x,若d(x)=K,则称G为K正则的无向图.设D为有向图,对于D的每个结点x,射入x的边数称为x的入度,记作deg+(x)或d+(x),射出x的边数称为x的出度,记作若deg-(x)或d-(x),d+(x)=d-(x),则称G为平衡有向图.在有向图G中,若则称G为K正则有向图.定理1每个图中,结点度数的总和等于边数的二倍,即定理2每个图中,度数为奇数的结点必定是偶数个.例1.在平面上有n个点S={x1,…,xn},其中任两个点之间的距离至少是1.证明在这n个点中,距离为1的点对数不超过3n.例2.在一个化学实验室里,有n个药箱,其中每两个不同的药箱恰有一种相同的化学品,而且每种化学品恰好在两个药箱中出现,问:(1)每个药箱有几种化学品?(2)这n个药箱中共有几种不同的化学品?第二节图的顶点度和图的同构(2)定理3在任何有向图中,所有结点入度之和等于所有结点出度之和.证明因为每条有向边必对应一个入度和出度,若一个结点具有一个入度或出度,则必关联一条有向边,因此,有向图中各结点的入度之和等于边数,各结点出度之和也等于边数.定义度序列,若V(G)={v1,v2,…,vp},称非负整数序列(d(v1),d(v2),…,d(vp))为图G的度序列.第二节图的顶点度和图的同构(3)推论1非负整数序列是某个图的度序列当且仅当是偶数.证明:由定理1知必要性成立.对于充分性取p各相异顶点v1,v2,…,vp,若di是偶数,就在vi处作di/2个环;若di是奇数,在vi处作(di-1)/2个环,由于是偶数,故中由偶数个奇数顶点,从而将所有与奇数di相对应的顶点vi两两配对并连上一条边.最后所得的序列就是.第二节图的顶点度和图的同构(4)图序列:简单图的度序列.定理4非负整数序列是图序列当且仅当是偶数,并且对一切整数k,有定义3设G1=<V1,E1>和G2=<V2,E2>是简单图,若存在一个从V1到V2的双射函数f,且f具有这样的性质,对V1中的所有x和y,x和y在G1中相邻,当且仅当f(x)和f(y)在G2中相邻,就说G1和G2是同构的,记作G1∽G2.例1画出所有不同构的具有5个结点,3条边的简单无向图.例2是否可以画一个简单无向图,使各点度数与下列的序列一致:(1)2,2,2,2,2,2(2)2,2,3,4,5,6(3)1,2,3,4,4,5第三节图的运算(一）定义1设与是任何两个图.若且是在上的限制,则称是G的子图,记作称G为G1的母图.若且,则称是G的生成子图或支撑子图.设,以V1为顶点,以两端点均在V1中的全体边为边集的G的子图,称为V1的导出子图,记作G[V1].设,以E1为边集,以E1中的边关联的全部顶点集的G的子图,称为E1的导出子图,记作G[E1].特别,若