赞
踩
题目 : 偏序关系 特殊元素 ;
解答 :
① 问题
1
1
1 :
B
1
=
{
a
,
c
,
d
,
e
}
B_1 = \{a,c,d,e\}
B1={a,c,d,e} 是一条 长为 4 的 链 ;
这四个元素互相之间是可比的 ; 并且也是覆盖的 ,
e
e
e 覆盖
d
d
d ,
d
d
d 覆盖
c
c
c ,
c
c
c 覆盖
a
a
a ;
② 问题
2
2
2 :
B
2
=
{
a
,
e
,
h
}
B_2 = \{a,e,h\}
B2={a,e,h} 是一条 长为 3 的链 ;
a
,
e
,
h
a,e,h
a,e,h 之间都是可比的 , 但没有覆盖关系 , 即他们之间都有其它元素相隔 , 这也是链 ;
集合中有
n
n
n 个元素 , 且这些元素可比 , 那么这个集合就是一个长为
n
n
n 的链 , 中间可以隔着其它元素 ;
③ 问题
3
3
3 :
B
3
=
{
b
,
g
}
B_3 = \{b,g\}
B3={b,g} 是一条 长为 2 的链 ;
b
,
g
b,g
b,g 之间隔着 4 个元素 , 但这个集合中元素是可比的 , 也是链, 长度为集合的元素个数 ;
④ 问题
4
4
4 :
B
4
=
{
g
,
h
,
k
}
B_4 = \{g,h,k\}
B4={g,h,k} 是一条 长为 3 的 反链 ;
集合中的元素 , 都不可比 , 那这个集合就是反链 ;
如果一部分可比 , 另一部分不可比 , 那这个集合什么都不是 , 既不是链 , 也不是反链 ;
⑤ 问题
5
5
5 :
B
5
=
{
a
}
B_5 = \{a\}
B5={a} 是一条 长为 1 的 链 , 同时也是一条长为 1 的反链 ;
如果集合中只有一个元素 , 那么该集合 既是 链 , 又是 反链 , 长度为
1
1
1 ;
⑥ 问题
6
6
6 :
B
6
=
{
a
,
b
,
g
,
h
}
B_6 = \{a, b, g, h\}
B6={a,b,g,h} 既不是链 , 也不是反链 ;
g
,
a
g,a
g,a 是可比的,
h
,
a
h,a
h,a 是可比的 ,
g
,
b
g,b
g,b 是可比的 ,
h
,
b
h,b
h,b 是可比的 ,
g
,
h
g,h
g,h 不可比 ,
a
,
b
a,b
a,b 不可比 , 因此其 既不是链 , 也不是反链 ;
⑦ 问题 7 7 7 :
上界问题 :
注意 :
上界 是一个元素 , 一个集合的上界 可能有很多个, 上界集合 是 上界元素 的集合 ;
上界集合中的最小元 是 上确界 或 最小上界 ;
集合不一定有上界 ( 有可能上面有两个极大元, 互不可比 ) , 有上界 不一定有 上确界 ;
下界问题 :
注意 :
下界 是一个元素 , 一个集合的下界 可能有很多个, 下界集合 是 下界元素 的集合 ;
下界集合中的最大元 是 下确界 或 最大下界 ;
集合不一定有下界 ( 有可能下面有两个极小元, 互不可比 ) , 有下界 不一定有 下确界 ( 最大下界 ) ;
求 一个 集合 的 下界和上界 , 注意从集合的 最小元 ( 下界 ) 和 最大元 ( 上界 ) 开始算 , 不要忽略这两个元素 ;
⑧ 问题
8
8
8 :
B
4
=
{
g
,
h
,
k
}
B_4 = \{g,h,k\}
B4={g,h,k} 是反链 , 其没有 上界 和 下界 , 自然 也 不存在 上确界 和 下确界 ;
反链 是 没有 上界 和 下界的 , 元素之间都不可比 ;
题目 :
解答 :
问题 1 : 偏序关系证明 :
① 写出
120
120
120 的因子集合 : 先列出其素因子 , 然后使用素因子组合即可 ;
( 注意
x
x
x 整除
y
y
y ,
x
x
x 是较小的数 , 是除数 ,
y
y
y 是较大的数 , 是被除数 ,
除
数
∣
被
除
数
除数 | 被除数
除数∣被除数 是整除关系的表示 )
A
=
{
1
,
2
,
3
,
4
,
5
,
6
,
8
,
10
,
12
,
15
,
20
,
24
,
30
,
40
,
60
,
120
}
A=\{1, 2,3,4,5,6,8,10,12,15,20,24,30, 40,60,120\}
A={1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120}
② 证明偏序关系 需要证明其 三个性质 自反 反对称 传递 ;
问题 2 : 画哈斯图 : 先画出 1 1 1 , 从底下向上画, 画完后 逐个检查 是否有遗漏 ;
问题 3 : 确定最长链 并 找出最长链 :
① 逐个寻找 , 最长链为 6 , 从底部到上面 从左到右 逐个分支进行遍历 写出 长度为 6 的链 ;
从底部
1
1
1 开始写 , 最左侧的链 为 :
{
1
,
2
,
4
,
8
,
24
,
120
}
\{1,2,4,8,24,120\}
{1,2,4,8,24,120}
这个最左侧链从顶部向下走 , 从
8
8
8 开始有个分支 , 写下这个链
{
1
,
2
,
4
,
8
,
40
,
120
}
\{1,2,4,8,40,120\}
{1,2,4,8,40,120}
继续往下走 ,
4
4
4 的位置有个分支 , 其下对应着
3
3
3 个分支 分别是 :
{
1
,
2
,
4
,
12
,
24
,
120
}
\{1,2,4,12,24,120\}
{1,2,4,12,24,120}
{
1
,
2
,
4
,
12
,
60
,
120
}
\{1,2,4,12,60,120\}
{1,2,4,12,60,120}
{
1
,
2
,
4
,
20
,
60
,
120
}
\{1,2,4,20,60,120\}
{1,2,4,20,60,120}
继续往下走 , 2 2 2 的位置有分支 , 对应
给出参考答案 , 不在详细列出 :
1→2→4→8→24→120 1→2→4→8→40→120 1→2→4→12→24→120 1→2→4→12→60→120 1→2→6→12→60→120 1→2→6→30→60→120 1→3→6→12→24→120 1→3→6→12→60→120 1→3→6→30→60→120 1→3→15→30→60→120 1→5→10→20→40→120 1→5→10→30→60→120 1→5→15→30→60→120
问题 4 : 集合 A A A 至少划分成 多少 互不相交的反链 , 完整写出这些反链 :
分析 : 将集合
A
A
A 划分成最多的反链个数 是
16
16
16 个 , 即每个元素都划分成一个单独的反链 ;
{
{
1
}
,
{
2
}
,
{
3
}
,
{
4
}
,
{
5
}
,
{
6
}
,
{
8
}
,
{
10
}
,
{
12
}
,
{
15
}
,
{
20
}
,
{
24
}
,
{
30
}
,
{
40
}
,
{
60
}
,
{
120
}
}
\{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{8\}, \{10\}, \{12\}, \{15\}, \{20\}, \{24\}, \{30\}, \{ 40\}, \{60\}, \{120\}\}
{{1},{2},{3},{4},{5},{6},{8},{10},{12},{15},{20},{24},{30},{40},{60},{120}}
现在需要将其尽可能多的将上述集合进行合并 , 每个集合必须是反链 :
{
{
1
}
,
{
120
}
,
{
2
,
3
,
5
}
,
{
4
,
6
,
15
,
10
}
,
{
8
,
12
,
30
,
20
}
,
,
{
24
,
60
,
40
}
}
\{ \{ 1 \}, \{ 120 \}, \{2,3,5\} , \{ 4,6,15,10 \} , \{ 8, 12 , 30, 20 \} , , \{ 24, 60 , 40 \} \}
{{1},{120},{2,3,5},{4,6,15,10},{8,12,30,20},,{24,60,40}}
结果 : 至少能划分成 6 个互不相交的反链 ;
技巧 : 哈斯图 横向 没有关联的一条线 可以组成一条反链 ;
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。