等价关系与序关系

等价关系与序关系 笛卡尔积 集合A与集合B的笛卡儿积为一个集合 记为A BA B x y x A且y B x y 是有序对 关系 集合A到集合B的关系是笛卡儿积A B的一个子集如果R是集合A到集合B的一个关系 且 x y 是R的一个元素 那么称x关于R与y关联 有关系 一般记作xRy集合S到其自身的关系称为集合S上的关系 例 S 草 树 猪 牛 LYC T 植物 动物 人 定义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为A B 空集 显然 R有自反性和对称性 但没传递性定义R为 只要两个人x和y的姓相同 xRy就为真 这是一个等价关系 等价类 如果R是S上的等价关系 x S 则S中与x相关联的元素的集合称为包含x的等价类 记为 x 所以 x y S yRx 自反性保证了x x 等价类的性质 1 如果x和y是集合S的元素 那么x与y相关联 当且仅当 x y 2 关系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 array 1 8 oflongint f 2 5 5 5 0 2 4 3 查找代表 Functionfind u longint longint 寻找u所在等价类代表Beginif f u 0 thenfind uelsebeginf u find f u 路径压缩find f u end End 合并两个等价类 ProcedureUnion u v longint Varfu fv longint Beginfu find u fv find v if fufv thenf fu fv End 例题1 等式矛盾 给定一系列等式 判断最早在第几个等式处出现矛盾 等式形如 x y 其中x和y可以是任意整数或一个符号 例 x yy 1x zz 0 矛盾0 1 分析 这是一个等于关系 两个不同的常数不能在同一个等价类中 一旦两个相同的常数在同一个等价类中就出现矛盾 维护并查集时 如果某个等价类有常数 就让这个常数做代表 这是不难办到的 同余关系 对于给定的m 整数数集上的同余关系 modm 是等价关系 自反性 x x modm 对称性 x y modm 那么显然y x modm 传递性 x y modm 且y z modm 那么x z modm 例题2 朋友敌人 N个人分成了两大阵营 同一阵营的两人为朋友 不同阵营的两人为敌人 开始时什么都不知道 不断告诉你两个人之间的关系 判断是否有矛盾 分析 设两大阵营分别为 和 我们把n个人看做n个0或10表示该人处于阵营X 1表示该人处于阵营Y设两个人A和B的对应数字为a和b那么他们是朋友当且仅当a b 0 mod2 他们是敌人当且仅当a b 1 mod2 人之间的关系 我们定义人与人之间的关系 ARB当且仅当a b r mod2 0 r 2 已知 即我们可以确定a b mod2 的最小剩余R是一个等价关系 自反性 a a 0 mod2 对称性 a b r mod2 那么b a 2 r mod2 传递性 a b r mod2 b c s mod2 那么a c t mod2 其中t为r s mod2 的最小剩余 并查集 该等价关系体现了两个人之间的关系 可以使用并查集来处理这个关系在并查集中的每个点记录它与它父亲的关系 即a b mod2 的最小剩余为0还是1对于在同一个等价类中的集合 可以通过它们和代表的关系计算它们之间的关系即r u 表示k u k f u r u mod2 查找代表 Functionfind u longint longint Varfu longint Beginif f u 0 thenfind uelsebeginfu find u r u r u r fu mod2 r u xorr fu f u fu find fu end End 合并等价类 ProcedureUnion u v x longint k v k u x mod2 Varfu fv longint Beginfu find u fv find v if fufv thenbeginf fu fv r fu r v r u x 16 mod2 r v xorr u xorxend End 例题3 现在有n种动物 动物分成A B C三类 食物链呈现为A吃B B吃C C吃A的情况 给定一些某动物吃某动物的关系 问第几个关系出现矛盾 A 0 B 1 C 2 X吃Y相当于 x y 1 mod3 进一步推广 食物链是长度为M的环怎么做 0 1 X吃Y相当于 x y 1 modm m 2 2 m 1 偏序关系 集合S上的关系R是一个偏序关系当且仅当R满足以下三个性质 1 自反性 即对S中的每个元素x xRx2 反对称性 当xRy且yRx 就有x y3 传递性 当xRy且yRz 则xRz偏序关系简称偏序 偏序关系实例 实数集上的等于关系实数集上的小于等于关系集合族上的包含关系正整数集上的整除关系多元组集合上的字典序关系同余关系不是偏序关系 二元组的字典序 设R1是S1的偏序 R2是S2上的偏序 可以用R1和R2在S1 S2上定义一个关系R 可以定义R为 a1 a2 R b1 b2 当且仅当下列条件之一为真 1 a1b1并且a1R1b12 a1 b1并且a2R2b2可以证明 R是S1 S2上的偏序 多元组的字典序 设n元组集合S S1 S2 Sn R1 R2 Rn分别是S1 S2 Sn上的偏序关系 设S S1 S2 Sn 1 只要我们能用R1 R2 Rn定义出S 上的偏序关系 根据上面二元组的讨论可得到S上的偏序关系 那么定义n元组的偏序关系就降低为定义n 1元组的偏序关系 对称性与反对称性 既对称又反对称 等于关系对称但不反对称 同余关系不对称但反对称 小于等于关系既不对称又不反对称 随便定义 把序关系看成无环有向图 如果把S看成点集 关系R看成边集 那么序关系就是一张有向无环图 回想 等价关系可以看成无向图 当然 无环是在忽略每个点的自环前提下的 这是由反对称性决定的 根据传递性 图中若u到v有边 v到w有边 那么u到w有边 全序 如果S的每对元素都是可比较的 即对任何x y S 总有xRy或yRx 则称集合S上的一个偏序关系R为S上的全序或线性序 小于等于是全序 但整除不是 有序排列 对于集合S的排列p1p2 pn 如果只有i j 才能有piRpj 那么就称该排列为S关于R关系的一个有序排列 S上的偏序R是全序当且仅当S关于R关系只有一个有序排列 拓扑序相当于一个有序排列当有全序时就意味着只有一个拓扑序 或者说 是可排序的 例题1 奶牛排序 有n头奶牛 他们有严格的大小关系 没有相等 现在 已经对他们进行了m次比较 问还要对它们进行几次比较 才一定能够确定奶牛之间的顺序 输入 n和m n不大于1000 m不大于10000 以及m对数a和b 表示a大于b 输出 一个数 只要还要比几次 分析 n头奶牛没有同样的大小 这说明n头奶牛组成的集合S不是可重集合 构造一个比较图 点集是S u到v有边当且仅当有一个比较u v我们可以由比较图得知n个数之间已知的大于等于关系R 即u 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且ai bi 输出只有一行 为结束试验的最早时间 样例1 原料数目 2原料编号 12放射时间 35加热时间 43最早结束 11 样例2 原料数目 5原料编号 12345放射时间 89463加热时间 521085最早结束 33 分析 我们称放射试验为A试验 加热试验为B试验 称第i种原料为原料i 我们设n种原料的A试验顺序为1 n的排列p 1 p 2 p n 即先对原料p 1 进行A试验 然后p 2 显然一旦有一个原料进行完A试验 就把该原料放到进行B试验的等待队列的尾部 这样是不会影响最优性的 所以进行B试验的顺序也为p 1 p 2 p n 于是一个1 n的排列就对应一种试验顺序的方案了 分析 对于执行顺序p 1 p 2 p n 设原料p i 的A试验结束时间为ta i B试验结束时间为tb i 则 ta i ta i 1 a p i tb i max tb i 1 ta i b p i tb n 就是最终结束时间 容易发现 tb n max sa i sb i 1 i n sa i a p 1 a p 2 a p i sb i b p i b p i 1 b p n 分析 我们考虑是否可以给所有原料一个统一标准 使得每个原料都有自己的权值 按这个权值从小到大的执行序列必然是最优的 找到了这种标准相当于找到了一个全序 为了找到这么一个标准 我们考虑 对于执行顺序p 1 p 2 p n 能否将其中某两个相邻试验p i 和p i 1 交换 而最终的结束时间不更迟 即解不更差 分析 我们令w a p i x b p i y a p i 1 z b p i 1 执行前a p 1 a p 2 wy a p n b p 1 b p 2 xz b p n 执行后a p 1 a p 2 yw a p n b p 1 b p 2 zx b p n 根据tb n max sa i sb i 容易发现只要max y w x y z x max w x z w y z 那么结束时间就不会变迟 分析 考虑3种可交换的情况 1 当y x 则y w xb i 的原料前 2 当y z w x z x 则y w xb i 的原料中 必然是b i 越大的排越前面 分析 由此 我们就找到了所有原料的统一标准 即将a i b i 的原料之前 对a i b i 的原料按b i 从大到小排序 这样的执行顺序必然是最优的 因为如果这不是最优顺序的 那么