等价关系与序关系

等价关系与序关系,笛卡尔积,集合A与集合B的笛卡儿积为一个集合,记为ABAB=(x,y)|xA且yB(x,y)是有序对,关系,集合A到集合B的关系是笛卡儿积AB的一个子集如果R是集合A到集合B的一个关系,且(x,y)是R的一个元素,那么称x关于R与y关联(有关系),一般记作xRy集合S到其自身的关系称为集合S上的关系,例,S=草,树,猪,牛,LYCT=植物,动物,人定义R为S到T的一个关系草R植物为真,草R动物为假猪R动物为真,猪R人为假LYCR人为真,LYCR植物假,等价关系,若集合S上的关系R具备以下三个性质：1、自反性：对S的任意元素x,xRx为真2、对称性：只要xRy为真，yRx就为真3、传递性：只要xRy为真，yRz为真，xRz就为真,等于关系,一个符号集合S定义S上的关系R：如果S中的两个符号x,y代表同一个事物的话，那么xRy就为真容易证明，R是等价关系。,整除关系,设S是正整数的集合，定义xRy为x|y。于是，3R6、7R35为真，但8R4,6R9为假。R是S上的一个关系。R有自反性，传递性，但没有对称性,其他例子,设S是一些集合组成的集合族，定义ARB为AB空集。显然，R有自反性和对称性，但没传递性定义R为：只要两个人x和y的姓相同，xRy就为真。这是一个等价关系,等价类,如果R是S上的等价关系，xS,则S中与x相关联的元素的集合称为包含x的等价类，记为x。所以x=yS:yRx自反性保证了xx,等价类的性质,1、如果x和y是集合S的元素，那么x与y相关联，当且仅当x=y2、关系R的两个等价类要么相等，要么互不相交,集合的划分,集合S的划分是一个子集族，它满足三个性质：1、没有一个子集是空的2、集合S的任何一个元素必然属于某个子集3、两个不同的子集互不相交,等价类与划分,1、一个等价关系R产生了一个划分P，其中P的成员就是R的等价类2、一个划分P导出一个等价关系R。其中，只要两个元素属于P的同一个成员，它们就关于R相关联。此外，这个关系的等价类就是P的成员,等价关系与并查集,并查集在英文中称为DisjointSet（不相交集合）划分就一系列不相交集合，而划分与等价类是互相对应的。因此并查集一般都是用来处理等价类。所以，用并查集处理一些问题的关键是洞察问题中所蕴藏的等价关系并查集可以动态维护等价关系,但只能加强关系,不能削弱关系,并查集存储结构,5,2,3,4,1,6,8,7,等价类代表,f:array1.8oflongint;f=2,5,5,5,0,2,4,3,查找代表,Functionfind(u:longint):longint;/寻找u所在等价类代表Beginif(fu=0)thenfind:=uelsebeginfu:=find(fu);/路径压缩find:=fu;end;End;,合并两个等价类,ProcedureUnion(u,v:longint);Varfu,fv:longint;Beginfu:=find(u);fv:=find(v);if(fufv)thenffu:=fv;End;,例题1:等式矛盾,给定一系列等式,判断最早在第几个等式处出现矛盾.等式形如:x=y，其中x和y可以是任意整数或一个符号.例:x=yy=1x=zz=0/矛盾0=1,分析,这是一个等于关系.两个不同的常数不能在同一个等价类中,一旦两个相同的常数在同一个等价类中就出现矛盾.维护并查集时,如果某个等价类有常数,就让这个常数做代表,这是不难办到的,同余关系,对于给定的m,整数数集上的同余关系(modm)是等价关系自反性：xx(modm)对称性：xy(modm)，那么显然yx(modm)传递性：xy(modm)且yz(modm)，那么xz(modm),例题2:朋友敌人,N个人分成了两大阵营，同一阵营的两人为朋友，不同阵营的两人为敌人开始时什么都不知道，不断告诉你两个人之间的关系，判断是否有矛盾,分析,设两大阵营分别为和，我们把n个人看做n个0或10表示该人处于阵营X,1表示该人处于阵营Y设两个人A和B的对应数字为a和b那么他们是朋友当且仅当a-b0(mod2)他们是敌人当且仅当a-b1(mod2),人之间的关系,我们定义人与人之间的关系：ARB当且仅当a-br(mod2)(0r=v当且仅当在比较图中u到v有路径。,分析,一定能够确定奶牛之间的顺序也就是说存在唯一一个有序排列。问题就转化为要把目前的关系R进行扩充，使R变成一个全序因此，如果uRv,vRu都为false，那么它们之间就要比较一次问题答案就是：C(n,2)已有关系对数,例题2,n个人到食堂吃饭，由于食堂只有一个窗口，n个人必须排成一队依次打饭。每个人有各自的打饭时间与吃饭时间。问如何安排n个人的打饭顺序，使得所有人都吃完饭的时刻尽量早。打饭时间：978吃饭时间：345结束时间：29,分析,吃得越慢越先打饭也就是按吃饭时间从大到小的顺序排队正确性：假设从大到小的方案T不是最优的必然存在另一个最优的方案S在S中不断交换两个人的顺序,这两个人中吃饭快的排在吃饭慢的前面,可以证明每次这样的交换不会使答案更差,最后交换的结果就是得到T,说明T不比S差上述证明有个小小的问题，T不是唯一的。,该问题中的序关系,n个人组成了集合S,S上的关系R可以这样定义:xRy为真当且仅当x吃饭比y慢。其实也就是定义在吃饭时间上的大于关系。这不是一个全序关系，因为吃饭时间有相同，但可以把吃饭时间相同的人看成一个人，这个人的打饭时间是合并前的人的打饭时间和。这一步是等价转化。这样关系R就是全序关系了，存在唯一一个有序排列，这就解决了上述证明中T可能不唯一的困难,全序与贪心,当我们可以找到问题中所隐含的某种全序关系，并且在该全序关系下，任何非有序排列都可以通过无损交换达到有序排列（所谓无损交换是指不会使答案更差），那么有序排列往往是最优解。,思考,假设打饭时间都在一个较小的范围内,若把一个窗口该成两个窗口该怎么做?,例题3,SZ采集了若干种化学原料。现在，他需要对每种原料进行精密的分析，以确定有效成分的含量。每种原料的分析都必须依次经过两个步骤：首先让原料接受一定时间一定量的粒子轰击（称放射试验）；然后在156.0973下与浓硫酸共热（称加热试验），两个试验都必须在特制的精密昂贵的仪器内进行。由于经费的问题，实验室里只有一台做放射试验的仪器及一台做加热试验的仪器。换句话说，同一时间内最多只能做一个放射试验和一个加热试验。而各种原料需做试验的时间是不尽相同的（幸而关于这些时间的数据SZ已经做了精确的预算）。现在请你预计一下阿扁能结束试验的最早时间。,例题3,输入第一行为原料的数目n（0=n=1000）以下n行每行各两整数ai，bi，表示第i种原料做放射试验的时间为ai，做加热试验的时间为bi。（0=ai,bi=100且aibi）输出只有一行，为结束试验的最早时间。,样例1,原料数目:2原料编号:12放射时间:35加热时间:43最早结束:11,样例2,原料数目:5原料编号:12345放射时间:89463加热时间:521085最早结束:33,分析,我们称放射试验为A试验,加热试验为B试验,称第i种原料为原料i。我们设n种原料的A试验顺序为1.n的排列p1,p2,pn，即先对原料p1进行A试验，然后p2显然一旦有一个原料进行完A试验，就把该原料放到进行B试验的等待队列的尾部，这样是不会影响最优性的。所以进行B试验的顺序也为p1,p2,pn。于是一个1.n的排列就对应一种试验顺序的方案了。,分析,对于执行顺序p1,p2,pn，设原料pi的A试验结束时间为tai,B试验结束时间为tbi,则：tai=tai-1+apitbi=max(tbi1,tai)+bpitbn就是最终结束时间。容易发现：tbn=maxsai+sbi(1=i=x,则y+w+xbi的原料中，必然是bi越大的排越前面。,分析,由此,我们就找到了所有原料的统一标准。即将aibi的原料之前，对aibi的原料按bi从大到小排序。这样的执行顺序必然是最优的，因为如果这不是最优顺序的，那么必然存在另一个最优顺序，从中可以找到上述的3种情况之一，可以进行交换，当不能交换时，也就是该顺序了。,分析,对每个原料设置第一关键字key1i,如果aibi,key1i=0,否则key1i=1，第二关键字