《离散数学》7偏序关系ppt课件

上一课内容对等关系、对等关系对等类定义特性商集、集合分割对等关系和分割匹配、1，2/49，7.6部分顺序关系和网格、7.6.1部分顺序关系、部分顺序集7 . 6 . 2 hase(hase y)S图7.6.3链、半链、半链，4/49，子顺序关系，子顺序集，定义1集a为非空集，r为a的二进制关系，如果r具有磁反射性，反称，传递性，则r称为a的子顺序关系，这被记录为：(a，)是部分顺序集。如果(x，y)，示例1a=1，2，3，4 r=(1，1)，(2，2)，(3，3)，(4，4)，(1，)，5/49，设置示例2(p109)，z=NZ n0。换句话说，z是正整数的集合。对于任意x，yz (x，y)，在z中定义二进制关系r，如下所示：r仅适用于x|y。证明(z，r)具有部分顺序集，6/49，示例2(p109)证明(z，r)具有部分顺序集，(1)任何xz明显具有x|x，因此(x，x) r(2)对于所有x，yz，对于(x，y) r和(y，x) r，我们有x|y，即nZ，y=nx，还有y|x，即mZ，x(3)对于随机x，y，ZZ，为(x，y) r和(y，z)r；(x，y) r，x|y，因此，z=m0n0 x，即x|z，因此(x，z) r，即r具有传递性。总之，r是z上的偏序关系。也就是说，(z，r)是一组部分顺序。对于x，yz (x，y) r，仅x|y。7/49，示例3集A是任意集，(A)是A的幂集，(A)中创建二进制关系R:仅用于xy。不难证明(A)，r)也是偏序集。8/49，例如，实数集r中的二进制关系s，仅在任意x，yr，(x，y) s为x 荔y时定义。可以证明s是r的偏序关系。为实数集r定义二进制关系S ，为任意x定义yr，(x，y) s ，仅限xy。可以证明s 是r的部分顺序关系。a的恒等关系IA与a的偏序关系，9/49，在与符号相关的偏序关系中，经常用“”标记来表示。(a，b)写为ab，读为“a小于或等于b”。通常显示为符号(a，)的部分顺序集。10/49，请注意，部分顺序关系“a小于或等于b”并不意味着一般意义上的a小于b。您可以在一个集中定义另一个部分顺序关系，以获得另一个部分顺序集。还讨论了包含集a和集a的部分顺序关系的部分顺序集(a，)。不允许X (a，)，仅显示xa (x，y)。也就是说，元素来自a，关系来自。11/49，复盖，设置(A，)假定子集，A假定子集，|A|=n。对于任意x，ya和xy，假定(x，y)或xy。zA上的xz表示，zy上的x=z或y=z表示，y表示复盖x。r为非空集a的子顺序关系，如果x，y-72a，xy没有za，则y为x，12/49，a=1，2，3，4=(1，1)， |A|=n .如果有N个顶点，每个顶点都是A的元素，两个顶点x和y，y复盖x，则可以使用图(A，)，其中点x位于点y之下，表示在两点之间连接直线的部分顺序集。，哈斯图：具有反向、反向、传递性的简化关系，14/49，是，a=a，b，c，d，e=(a，a)，(b，)，15/49，16，哈斯图示例，17/49，示例a=1，2，3，4，1，2，18，a=a，b，c，d，e，f，g，h r=， 8746；ia，哈斯图示例，对于部分顺序已知的哈斯图，a和关系r的集合表达式，19，注意事项：1，没有三角形；2、水平段不出现；3、最小化相交线。20/49，可比较，不可比较，设置(a，)是任意x、ya、xy或yx的x和y比较的部分顺序集。否则，不会比较x和y。例如，提供图中所示的部分顺序集。2和1，2和4等比较，但2和3，3和4比较不了。21/49、3、链、反链、设置(a，)是子集，b是a的子集。如果b的两个元素都比较，则(b，)为链。(2)如果b无法比较两个元素，则(b，)为反链。22/49，例如图中所示的子集，(a，b，c，d，)链(a，d，e，)链(b，e，)半，示例a=a，b，c，d，e=(a，a)，(b，b)，(c，c)，(d，d)，(e)在1，2中，1是最小元，2是最大元1，2，3，1是最小元，2，3是最大元1，2，3，4，1是最小元，3和4是最大元。27/49，集(a，)是偏序集，ba，y/B。如果x (x/b yx)成立，则y称为b的最小圆。如果x (x/b xy)成立，则y有b的最大元，2，最大，最小值，28/49，有限部分顺序集，不一定有最大和最小元素，但不一定有最大和最小元素。例如，提供图中所示的部分顺序集。1是最小元，也是极愿望，3和4是最大元，没有最大值。29/49，例如图中所示的子集最小和最大元素，(a)没有最大元素，(c)没有显示的子集最小和最大元素，(b)和(d)显示的子集最小和最大元素，(a)(b)(c)绝对是极圈，也是极圈。如果地物中存在孤立点，则没有最大和最小元素。2、除孤立点外的其他最小元素是图中所有下路径的终点；其他最大元素是图中所有上方路径的终点。3、如果最小元素是唯一的最小元素；最大元素是唯一的最大元素。30/49，示例最大、最小和最大、最小、最小：1最大：5，6，7，8，9最小：1最大：1无，最小：最大：a，b，c如果设定了X (x/b xy)，则y称为b的上限，如果设定了x (x/b yx)，则y称为b的临界值，3，上限和临界值，33/49。此范例显示了图中所示的子集顺序。h，I，j，k都是f，g的上限，c，d，a是其阈值，34/49，设置(a，)是子集，ba，ya。c=y | y是b的上限，c的最小值是b的最小上限或上限。d=y | y是b的阈值，d的最大值是b的最大阈值或阈值。4，上下限和35/49，b，d的上限为h和f下限为a；上限为f，下限为a。，1，b的元素能一起上升是上限，上限的最大值是上限；2，b的元素一起向下，就可以到达下限，下限最小的元素是下限。36，是，部分顺序集a的最小、最小、最大、最大，如下图所示。设定b=b，c，d，然后设定b的下限、