【离散数学】最大元素、最小元素、极大元素、极小元素、上界、下界、最小上界(上确界)、最大下界(下确界)

设(A, ≤)是一偏序集合,B是A的子集。

最大元素、最小元素:
(1)元素b∈B是B的最大元素,如果对每一元素x∈B,x≤b
(2)元素b∈B是B的最小元素,如果对每一元素x∈B,b≤x
即:对于每一个元素,都能满足这样的偏序关系。
定理:如果B存在最大(最小)元素,那么它是唯一的。
例:如果B = {2, 3},偏序关系为“整除”,因为2和3互相不能整除,那么B没有最小元素和最大元素。

极大元素、极小元素:
(1)如果b∈B,且B中不存在元素x,使b≠x且b≤x,那么元素b∈B叫做B的极大元素。
(2)如果b∈B,且B中不存在元素x,使b≠x且x≤b,那么元素b∈B叫做B的极小元素。
即:对于极大元素,不存在元素在它偏序关系之上。对于极小元素,不存在元素在它偏序关系之下。

注意:B的最大(小)元素和极大(小)元素都必须是子集B的元素,而B的上界(下界)和最小上界(最大下界)可以是也可以不是B的元素。在定义中并没有保证这些元素的存在。在许多情况下他们是不存在的。

上界、下界:
(1)如果对每一b∈B,b≤a,那么元素a∈A叫做B的上界;
(2)如果对于如果对每一b∈B,a≤b,那么元素a∈A叫做B的上界;
上界、下界是A集合里的,可以存在很多个,也可以不存在
也就是说求上界的时候,对于每一个B里面的元素,都要和它上界们满足偏序关系,所以在集合B里面的不能有两个及以上,因为同事选择两个的话,就不满足B里面任何元素都要满足偏序关系了。

上确界、下确界:
(1)如果a是一上界并且对每一B的上界a’有a≤a’,那么元素a∈A叫做B的最小上界,记作lub;
(2)如果a是一下界并且对每一B的下界a’有a≤a’,那么元素a∈A叫做B的最大下界,记作glb
最大下界和最小上界可能存在也可能不存在,如果它们存在,则是唯一的。

如果最大值/最小值/上确界/下确界存在,那么一定是唯一的
求极大值/极小值的时候,因为只要是所有元素没有不满足的就可以,所以可以选择两个以上,其中可以有不和元素连线的。。
求上界/下界,因为是和最大最小值一样是所有的必须满足条件,所以所有元素都是要求有连线的,所以不可能存在两个及以上的元素在B集合里面。。

【离散数学】搜集、并搜集、交搜集、求A = {{Φ, 2}, {2}}的并搜集和交搜集

做题的时候发现一个叫“搜集”的名词……
不知道是什么意思……
后来才在书上找到……
集合的概念:集合在某些场合又称为类、族或搜集
【手动再见- -||】

并搜集和交搜集的概念:
Snip20160622_10

简而言之,A的并搜集就是:A的所有子集里面包含的元素的并
A的交搜集就是:A的所有子集里面包含的元素的交

举个栗子~:
求A = {{Φ, 2}, {2}}的并搜集和交搜集:
先把A的子集都写出来:Φ、{{Φ, 2}}、{{2}}、{{Φ, 2}, {2}}
然后它有的所有元素是:{Φ, 2}、{2}
然后并搜集就是这两个元素的并:【这两个元素明显是两个集合嘛,所以就是求两个集合的并】——结果是{Φ, 2}
同理,交搜集就是求这两个元素的交:——结果是{2}

【离散数学】单向连通和弱连通的区别

Snip20160622_1

单向连通一定是弱连通的。
but,弱连通不一定是单向连通~~

举个栗子~
Snip20160622_3

是弱连通~但不是单向连通~因为a和b结点,a不能到b,b不能到a~~

概念:
单向连通图
如果有向图中,对于任意节点v1和v2,至少存在从v1到v2和从v2到v1的路径中的一条,则原图为单向连通图。
即设G=<V,E>是有向图,如果u->v意味着图G至多包含一条从u到v的简单路径,则图G为单连通图。
强连通图、连通图、单向连通图三者之间的关系是,强连通图必然是单向连通的,单向连通图必然是弱连通图。
弱连通图
将有向图的所有的有向边替换为无向边,所得到的图称为原图的基图。如果一个有向图的基图是连通图,则有向图是弱连通图。