第1章图论简介.ppt

1.图论问题的起源、发展及应用;七桥问题的分析;欧拉的结论;4.图的作用;5.图的广泛应用;6.基本的网络优化问题;图论中的经典算法与现代智能算法结合解决NP难题;本学期主要内容; 由于后续学习的需要,我们补充离散数学 中的一些基本内容:关系与函数.;预备知识 二元关系;复习集合中的几个定义;1.1 序偶与笛卡儿积 1.2 二元关系及其表示 1.3 关系的运算 1.4 关系的性质 1.5 关系的闭包 1.6 等价关系与集合的划分;1.1.有序对与笛卡儿积;1.2 笛卡儿积的概念;1.3笛卡儿积的性质 1.对任意集合A有:A??=?,??A=?; 2.笛卡儿积运算一般不满足交换律:A?B≠B?A; 3.一般也不满足交换律:(A?B)?C ≠A?(B ?C).;例1.3.设A={1,2},求P(A)?A. 例1.4.设A,B,C,D为任意集合,判断以下命题是否为真,并说明理 由. (1)A?B=A?C?B=C; (2)A-(B?C)=(A-B)?(A-C); (3)A=B?C=D ? A?C=B?D. (4)存在集合A,使得A ? A???A.;定义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.6.空关系,恒等关系和全关系. 1.空关系:对于任何集合A,空集?是A?A的子集,叫做A上的空关系. 2.恒等关系:设IA为集合A上的二元关系，且满足IA={x，x?x?A} ，则称IA为集合A上的恒等关系。 3.全关系EA定义为 EA={x,y∣x?A?y?A}=A?A . 例1.7.若A={1,2},求IA,EA. 其他一些常见关系: LA={x,y∣x,y ?A?x≤y},此处A?R. DB={x,y∣x,y ?A?x整除y},此处B?Z*. R?= {x,y∣x,y ?F?x?y},此处F是集合簇.;例1.8.设A={1,2,3,4},下面定义的R都是A上的关系,试用列举法 表示R.(1)R={x,y∣x是y的倍数};(2)R={x,y∣(x-y)2?A}; 1.3.二元关系的表示方法:给出一个关系的方法有三种:集合表达 式,关系矩阵和关系图.例1.5就是用集合表达式. ;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的关系图，如图所示： ;解 A上的关系图如下图所示。;1.3.关系的运算 关系的基本运算有七种,分别定义如下:;关系的右复合运算;例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。 如图所示： ;定理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.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上的限制记为R?A,其中R?A={x,y∣xRy?x?A} (2)A在R下的像记作R[A],其中