精华内容
下载资源
问答
  • 离散数学】偏序关系上界下界

    千次阅读 2021-01-19 10:46:10
    一直没搞懂这个上界下界的关系

    前提提要

    一直没搞懂这个上界和下界的关系

    在这里插入图片描述
    从上图可以发现,每个链上端都是分开的

    1. 所以该哈斯图没有最大值 最小值为1
    2. 但是极大值是每个链的最大值所以 存在 11、9、12、8、10、7 这几个极大值、极小值为1
    3. 上界为所有比 粉色的点还大的最大值。因为蓝色集合并没有最大值、所以无法确定2、3处的最大值。所以上界只有6 、12
    4. 下界很明显为1
    5. 上确界 为上界最小的 所以为6
    6. 下确接 为下界最大的 是1
    展开全文
  • 将挺好的:B站上可以找到资源,也是我想说的 https://blog.csdn.net/hpdlzu80100/article/details/102952763

    将挺好的:B站上可以找到资源,也是我想说的

    https://blog.csdn.net/hpdlzu80100/article/details/102952763

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

    设(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集合里面。。

    展开全文
  • 本文为离散数学的学习笔记,记录离散数学的知识框架以及相关概念,主要内容包括集合论、图论和近世代数(不含数理逻辑部分)。


    更新历史:

    • 2021年3月27日完成初稿
    • 本文为离散数学(Discrete Mathematics)的学习笔记,记录离散数学的知识框架以及相关概念,主要内容包括集合论图论近世代数(不含数理逻辑部分)。
    • 本文参考书为哈尔滨工业大学出版社出版、王义和编著的《离散数学引论(第3版)》1
    • 近世代数部分另外的参考书为高等教出版社出版的、屈婉玲编著的《离散数学(第2版)》2

    1. 集合论

      集合用来描述研究对象——具有某种性质的事物的全体,或者是感兴趣的一些事物。映射是描述事物之间的单值依赖关系的工具,通过这种联系,使得便于发现事物的运动规律,指导人们的生产生活实践。由于现实世界的复杂性,反映在事物之间的联系也是复杂的,而关系这个概念就可以描述事物之间的复杂联系。于是,集合、映射、关系等概念和理论就成为描述某些系统并为之建立数学模型的有力工具。

      在集合论中,应抓住各种集合与集合之间的关系,这是本章的重点。

    1.1 集合及其运算

      重要且难理解的概念为:

    1)集族:以集合为元素的集合(集合的集合);

    2)幂集:集合S的所有子集(包括空集和S本身)形成的集族,记为2S

      下面看一个例子:
    集合
      在学习过程中,注意这些特殊的集合是很有必要的。

    1.2 映射

    1.2.1 映射的定义和种类

      对于映射的定义也是应该熟稔于心的,在此不赘述,另外关于下面的定义,我们尽量给出通俗化的解释,而不是形式化定义。对于映射:
    映射
      有下面几种特殊的映射:

    1)单射:映射中,X中的任一元素的像不同;

    2)满射:映射中,Y中任一元素都有原像;

    3)双射:既是单射,又是满射。

      从X到Y的所有映射之集记作:

    从X到Y的所有映射之集

    1.2.2 特征函数

      下面介绍一个非常重要的概念:特征函数,下面先给出形式化定义,后用通俗的语言进行解释。

      特征函数:设X是一个集合,EX的子集,从X{0,1}的映射称为E的特征函数,其有
    特征函数

      可知E决定了E的特征函数,而全体特征函数的的集合为Ch(χ)

       Ch(χ) = {χ| χ: X → {0, 1}}

      因此对于X的子集而言,每个子集都有一个特征函数与之对应,可以证明:

    同构

    1.3 关系

    1.3.1 关系的定义

      关系这一概念,用通俗语言描述是简单的,可以定义为“联系”、“关联”等等,下面则是给出形式化的定义,并给出定义的过程:

      我们通常说它和它有联系,一般涉及到两个个体,我们不妨设这两个个体分别来自两个集合,设为集合A, B,则二元关系R可定义为映射A x B → {有,无},且有
    关系
      用1代表有,0代表无则有:
    关系
      因此二元关系R就是一个从A x B → {1,0}的映射,根据上述的特征函数的概念,则关系R是一个特征函数,又因为特征函数全集和集合的幂集一 一对应,故二元关系R可以认为是集合A x B的幂集中的一个集合,即A x B 的一个子集,则有下面形式化定义:

      AB是两个集合,A x B的任一子集R称为从AB的一个二元关系。如果A = B,则称RA上的一个二元关系。

    1.3.2 关系的性质和运算

      下面开始讨论关系及其性质,关系有如下性质:

    1. 自反性
    2. 对称性
    3. 传递性
    4. 反自反性
    5. 反对称性

      有以上性质的关系是一个“好”关系,那么我们如何构造好关系呢?则就是闭包运算了,我们在这里仅讨论关系的传递闭包运算:

      设R是X上的一个二元关系。X上的一切包含R的传递关系的交称为R的传递闭包。

      通过传递闭包运算,我们从一个简单的二元关系出发构造出一个包含R的具有传递关系的最小的关系,这也是闭包运算的关键所在。

    1.3.3 等价关系、集合的划分和商集

      接下来我们要来介绍几个重要的概念:等价关系、集合的划分和商集。

    【等价关系】:设关系RX上的一个二元关系,若关系R自反的、传递的和对称的,那么称关系RX上的一个等价关系,常用 来表示。

      对于一个集合而言,将其中所有元素按照等价关系进行分类,可以分成若干类,与x属于同一类的元素(包括x)所在的集合称为x的等价类,记作[x]。可以清楚地知道,如果将X中的元素全部归为若干个等价类,这几个等价类是不相交的,而且所有等价类包含了原来X中的所有元素,这就好像我们将集合X划分成了若干部分,因此有下面的重要结论:

      给定一个X上的二元关系R,若R是一个等价关系,那么由等价关系R推出的若干个等价类,等价类之间不相交且全体等价类之并构成集合X,使得一个个等价类就是对于集合X的划分,而且这个划分是唯一的,故等价关系R和集合的划分构成了一 一对应。 这就是等价关系和集合划分之间的关系,它们之间通过等价类这一概念联系起来。

      接下来,就可以定义商集了。商集是集合X对于等价关系R而言的,因此给定集合X和等级关系R,则商集是等价类[x]的集合,它形象地描述了等价类的性质,记作:X/R = {[x]|x属于X,[x]是X的等价类}

      至此就阐述清楚了等价关系、集合的划分和商集之间的关系。他们之间的关系是很重要的,在近世代数中常用等价关系来定义商集,从而有商群等的概念出现,现在的讲述或许是陌生的,但是到后面的讲解中对于商群的引出或许就可以理解等价关系的定义之重要了。

      最后下面留一个问题给读者解答:

    问:设A, B是两个集合,若A和B满足:{A ∩ B}A∪B的一个划分,则AB的关系是?

      欢迎在评论区进行讨论!

    1.3.4 偏序关系和偏序集

      偏序关系的定义和等价关系的定义是类似的:

      偏序关系:设关系RX上的一个二元关系,若关系R自反的、传递的和反对称的,那么称关系RX上的一个偏序关系,常用 来表示。

      当事物有偏序关系之后事物之间就有了一定的序结构,这是一类很重要的关系。

      在偏序关系上可以定义偏序集:设 X上的偏序关系,二元组(X,≤)便是偏序集。在后面的课程可以知道利用偏序集可以定义一些代数系统,如格等。现在我们讨论偏序集上的一些概念,设A上偏序集(X,≤)上的一个集合,那么有:

    1. 上界/下界
      上界是存在元素x属于集合X,使得A中的元素全都 xx组成的集合;下界同理。

    2. 最大元/最小元
      最大元是存在元素x属于集合A,使得A中的元素全都 x;最下元同理。(最大元和最下元可能不存在,存在必唯一)

    3. 上确界/下确界
      上确界是上界的最小值,下确界是下界的最大值。

    4. 极大元/极小元
      极大元是存在元素x属于集合A,使得x A中的元素(除去x)而组成的集合(偏序集中元素可能不可比较);极小元同理。(极大元/极小元若存在,可能不唯一)

      讲完这些概念,下面捎带介绍一下全序关系,全序关系是一种偏序关系,但全序关系中的所有元素均可比较,因此其Hasse是一条链。

      至此,关系这一概念就介绍完了,关系是集合论中十分重要的一个概念,有着广泛的应用(如关系数据库等),对于集合的各种关系及其性质应该深刻理解并掌握。

    1.4 无穷集合及其基数

      下面我们要来叙述一个很强大的工具/概念:无穷。我们需要揭示无穷集合和有穷集合的区别,以及无穷集合是怎么样的,有没有大小之分?无穷的本质是什么?下面就来介绍一下,首先需要知道集合分为有穷集合无穷集合无穷集合又分为可数集不可数集

    1.4.1 可数集

      就定义而言,可数集是一切能和自然数集N建立一 一对应的集合。对于可数集,有以下几种性质:

    1. 可数集中的全部元素可以排成无重复项的序列;

    2. 无穷集合中一定包含可数集;

    3. 可数集的任一无限子集也是可数集;

    4. 可数集A对有穷集M的差(A \ M)和两者之并(A U M)是可数集

    5. 可数个可数集的并也是可数的;

    6. 自然数集N、整数集Z和有理数集合Q是可数集;

    7. 设M是无限集,A是可数集/有限集合,那么M ~ M \ A,M ~ M U A。

      下面就可以讨论有穷集合和无穷集合之间的区别,之前叙述是有穷集合是有限的,无穷集合是无限的,那么具体说来,就上面的性质而言,我们发现当无穷集合去掉一些元素时还可以和自身对等(形成一 一对应),而有穷集合不是如此,故我们可以给出无穷的另一个定义,也是其本质特征:

      凡能与自身的一个真子集对等的集合称为无穷集合。

      或许现在可能很难理解如何对等,但知道它们实际上确实存在一 一对应是很重要的。下面我们介绍另一类无穷集合,它和不可无穷集合对等,这就是连续统。

    1.4.2 连续统

      就定义而言,区间[0,1]中的所有实数构成的集合是不可数无穷集合。而凡是与集合[0,1]对等的集合简称为连续统。下面简单介绍一下它的一些性质:

    1. 可数个两两不相交的连续统的并仍然是连续统;

    2. 无理数之集、全体实数之集R是连续统;

    3. 0、1的无穷序列所构成的集合是连续统;

    4. 若A是可数集,则2A是连续统;

    5. 数轴上的点、平面上的点和三维空间的点是一样多的。

    1.4.3 无穷集合的基数及其比较

      关于这一点,我们就简单介绍一下基数的比较:

      相等:集合A和集合B的基数称为是相等的(|A| = |B|),当且仅当 A ~ B。即两个对等的集合,其基数相等。

      小于:集合A与集合B的一个真子集对等,但不和B对等,则称|A| < |B|

      关于大于的定义是不必要的,因此不给出。关于集合的大小问题,康托曾给出下面一个定理:

      康托定理:对于任意一个集合M,|M| < |2M|

      这个定理给出一个很强大的工具,它可以创造很大很大的集合,因此尝试回答下面的问题:

    1. |N| = a|[0,1]| = c,是否在ac之间存在b使得a < bb < c

    2. 无穷集合里是否存在最大集合和最小集合?

      回答第一个问题是困难的,它是著名的连续统假设。而对于第二个问题,在朴素的集合论中,最大的集合是不存在的(由康托定理),而最小的集合则是可数集。

      至此,第一节介绍了集合论的一些知识,接下来我们将介绍图论,图论是研究一种特殊的二元关系的理论,它是集合论的一种应用。

    2. 图论

      图论源于欧拉对于哥尼斯堡七桥问题的解决,图论是一种特殊的二元关系,它大量使用集合论的语言来描述顶点和边之间的联系,顶点可以看成是顶点集合V的元素,而边可以看成顶点集合的笛卡尔乘积V x V的子集,也即在V上的一种二元关系,这是图论的实质。图论为任何一种包含了一种二元关系的有穷系统提供了一个数学模型。

      在集合论中,集合与集合之间的关系是受到关注的。而在图论中,各种图及图的性质是需要理解和掌握的,本节将描述各种图,给出图的定义(往往也是特征性质)和一些性质。

    2.1 无向图基本概念

    2.1.1 定义

      在图论中,图分为无向图和有向图,两种图的区别是不难理解的,因此不再赘述。这里首先给出无向图的定义:

      设非空有限集合V是顶点集合,而P(V)V中所有二元子集的集合,即P(V) = {A| A是V的子集, 且|A| = 2}EP(V)的子集,二元组(V, E)则称为无向图G,记作G = (V, E)

      在这里不将A定义V x V的子集是由于(u, v)(v, u)在无向图中是同一条边,而在V x V中是不一样的,而在二元子集中,集合元素的次序是无关紧要的。

      若定义二元关系E,任取顶点u, v属于集合V,若边uv在集合E中,则uv有关系(uEv),则可知二元关系E是一个反自反的、对称的二元关系,这也就说明了无向图的实质:

      无向图实际上就是一种非空有限集合V和定义在非空有限集合V上的反自反的、对称的二元关系的关系系统。

    2.1.2 子图、同构、自补图

      由无向图引出的基本概念还有无向图的子图、同构等概念。简单地说子图就是包含原无向图中的一些顶点和对应边的无向图,若一个子图包含所有的顶点,则该子图称为生成子图,这种概念是十分清晰的。这里主要叙述一些图的同构,下面是无向图同构的定义:
    在这里插入图片描述
      事实上,无向图的同构是寻找一个一 一 对应(双射),使得两个图在本质上是等价的,不过判断图的同构是困难的,掌握一些必要条件是关键的,两个同构的图应具备一下性质:

    1. 两个图的顶点数和边数要完全相同;

    2. 顶点按顶点的度依次排列,相应度数的顶点数应该相同,不同度数的顶点序列也应该相同(顶点的度应该对应相同)

      这里第一次谈到同构的概念,不仅在数学上,在其他领域也会有同构的概念或者其相反的概念(比如化学上的同分异构体)。在近世代数中,描述代数系统时也经常提到同构的概念,它表示两个代数系统时相同的,只是取的名字不一样而已。

      最后介绍一下自补图,自补图是指图本身和补图同构的图,而补图则是一种生成子图(包含所有顶点的图),其形式化定义如下:

      设G = (V, E)是一个图,则图Gc = (V, P(V) \ E)称为其补图。其中P(V)V中所有二元子集的集合,即P(V) = {A| A是V的子集, 且|A| = 2}

      判断自补图实际上就是判断图与其补图同构,利用同构的知识即可,不过利用图与补图中的所有边构成了原图对应的完全图的边,故对应完全图的边必须是偶数,这样才可能平均分配给图和其补图,这样才可能使之同构。

    2.1.3 无向图的连通性

      描述无向图的连通性和连通程度是一个大的话题,首先一一列举出无向图连通的一些概念,这里尽可能用通俗的语句去描述,形式化的定义可以查看相关的参考资料。
    1)通道:顶点和边的交替序列,闭通道是首尾顶点相同的通道;

    2)(闭)迹:边不相同的(闭)通道。包含所有顶点和所有边的(闭)迹称为欧拉(闭)迹;

    3)路、圈:路是顶点互不相同的通道,圈是顶点互不相同的闭通道。包含所有顶点的路(圈)称为哈密顿路(圈);

    4)连通:图中任意两个顶点之间有一条路联结。图G中的一个极大连通子图称为G的一个支。

      连通的判定是一个复杂的问题,在算法层面可以利用深度优先搜索算法(DFS)和广度优先搜索算法(BFS)来解决,不过在这里介绍一些必要条件(否定条件)是有必要的,设有一个图G = {V,E},是一个(p, q)图,下面的说法彼此是等价的:

    1. 图是连通的;

    2. 图中任两个不领接的顶点uv有:degu +degv >= p - 1 ;

    3. 图中任意一个顶点u有:degu >= [p/2](向上取整) ;

    4. q > 1/2(p - 1)(p - 2)

    5. min(degu) >= [p/2] (向上取整)

    6. 图G的补图 Gc 不连通

    2.1.4 欧拉图和哈密顿图

      在无向图中有两种特别重要的图,它们就是欧拉图和哈密顿图。

      欧拉图是存在欧拉闭迹的图,欧拉闭迹是包含所有顶点和所有边的闭迹。哈密顿图是存在哈密顿圈的图,哈密顿圈是指包含所有顶点的圈。在历史上,两种图的判定是研究工作者的重点课题。

    1.欧拉图的判定

      幸运地,判断一个图是否是欧拉图有充分必要条件:若图是连通的且每个顶点的度是偶数,那么该图是欧拉图。这是一个非常漂亮的结论,因为它足够简单。欧拉图的判定问题证明了哥尼斯堡七桥问题无解,也揭示了下面的两个一笔画问题:

    1. 从图的一个顶点出发一笔画完所有顶点和所有边,且每条边只画一次且仅画一次,最后回到原点:要求图连通,且所有顶点的度数为偶数(欧拉闭迹问题)

    2. 从图的一个顶点出发一笔画完所有顶点和所有边,且每条边只画一次且仅画一次,不要求回到原点:要求图连通,且只有两个奇度顶点,其他顶点为偶数(欧拉迹问题)

      从第二个问题开始延伸,可以扩展出一个图至少可以几笔画成的问题,看看下面的例题:问在下面几幅图(A,B,C,D)中分别可以用几笔画成?

    在这里插入图片描述

    1. 图A需要三笔画成,因为有6个顶点的度为奇数;
    2. 图B需要一笔便可画成,因为其所有顶点的度均为正偶数,故存在欧拉闭迹,是一个欧拉图;
    3. 图C需要两笔便可画成,因为有4个顶点的度为奇数;
    4. 图D需要一笔便可画成,因为有2个顶点的度为奇数,存在欧拉开迹。

      由上题可以总结一个定理:

      设G是连通图,G恰有2n个奇度顶点(n ≥ 1),则G的全部边可以排出n条开迹,而且至少有n条开迹。

    2.哈密顿图的判定

      不过,哈密顿图就没有那样的充分必要条件去判定了,这使得哈密顿图的判定成了一个难题,原因就在于哈密顿圈的条件更加严格,这也导致很多图无法直接判定是否有哈密顿圈,从而使得哈密顿图的判定没有很好的条件去使用。

      下面介绍一些判定哈密顿图的方法:

    1.染色法

      如果一个图能够用两种颜色染色,而且一种色顶点数不等于另一种色点数,那么这个图就不是哈密顿图。这个条件只能作为否定条件;

    2.找圈法

      尝试在图中找到一些圈,其原则是:度为2的顶点所连的两条边一定在哈密顿圈上,度为3的顶点所连的三条边一定有两条边在哈密顿圈上…依次类推,最终查看是否有哈密顿圈,还是有小圈(不经过所有顶点的圈),若有小圈,则不是哈密顿图;

    3.条件法

      设G = {V,E},是一个(p,q)图,那么

      — 若p >= 3,且min{degV} >= p/2,那么G是一个哈密顿图 ;

      — 若p >= 3,且对于G中的任一对不邻接的顶点uv均有:degu + degv >= p,那么G是一个哈密顿图;

      — 若图中有割点和桥,那么该图不是哈密顿图;

      — 完全偶图Km,n为哈密顿图的充分必要条件是m = n;

      — 若q = 1/2*(p-1)(p-2) + 2,则该图是哈密顿图;

      — 若G是哈密顿图,那么对于V的每个非空子集S均有图G - S的支数w(G - S) <= |S|

      无向图的基本概念已经介绍清楚了,下面要介绍一下无向图的应用或是拓展,这些都是基于上述的图的概念。

    2.2 树

      图已经是一种很好的模型/数据结构,有很多很好的算法,而树作为一种很简单的图,这种图具有很好的层次结构。

    2.2.1 树及其性质

      树是一种具有层次结构的图,就其定义而言:

    连通且无圈的无向图称为无向树,简称树。一个没有圈的无向图称为无向森林,简称森林。

      树有很多很好的性质:设树中有p个顶点和q条边,那么树

    1. 连通且无圈(定义)

    2. p = q + 1

    3. 去掉任一条边则不连通,加上任一条边则形成圈(每条边都是割边)

    4. 非平凡树是偶图

    5. 具有p(p>=3)个结点的非哈密顿图的边数最多有(p-1)(p-2)/2+1条。

      不是任一个图都是树,但是任一个连通图中都有一个子图,该子图是一棵树,而且这棵树可以包含所有的顶点,这就是生成树,生成树是原图的一个生成子图。下面来看一个问题:

    G是一个连通的(p,q)图,其有生成树T,除生成树T以外的边称为弦,问图G中至少多少条弦?
    答:生成树T中有p个顶点和p-1条边,故有q-p+1条弦。(这样说明了图G连通,则q >= p-1

      在算法上,有一类最小生成树问题是研究的热点,如今已经有Prim算法和kruskal算法可以解决这类问题,不过这就不是近世代数的任务了,而是数据结构与算法的任务了。

    2.2.2 割点和桥

      割点是一种特殊的顶点,去掉该顶点后,图的支数将增加,因此一个连通图的割点去掉之后就会变得不连通。桥是一种特殊的边,去掉该边之后图的支数将增加,因此一个连通图的桥去掉之后就会变得不连通。在变得不连通这个层面上,割点与桥是类似的。不过有桥,则必有割点,桥的两端就是割点,而有割点不一定有桥,这也是他们的区别和联系。

      正如前述一样,有割点的图可能是欧拉图,但有割边的图不是欧拉图,有割点和桥的图不是哈密顿图,这也是割点和桥的一些性质。下面来介绍另一个重要的概念:割集

      在图G = (V, E)中,割集S就是一个E的子集,当从G中去掉所有边后的图(G-S)的支数增加,而去掉S的任一真子集中的边所得到的图的支数不会增加,故通俗地说,割集就是使得图的支数增加的去掉的最少边的数量,在这一点上,割集和边连通度有着很紧密的联系。

      下面就可以介绍图的连通度,它是图和树连通的扩展,是值得研究的。

    2.3 连通度和匹配

    2.3.1 连通度

      在图中,顶点和边的关系是紧密的,但在连通度上,它们又是有所区别的,一个图的连通程度分顶点连通度、边连通度来描述。下面用通俗的语言来叙述几个概念:

    1) 顶点连通度是使得一个图变成不连通图或平凡图所去掉的最少顶点的数目

    2) 边连通度是使得一个图变成不连通图或平凡图所去掉的最少边的数目

    3) n-顶点连通(n-连通):一个图的顶点连通度大于等于n,则该图是n-顶点连通(n-连通);

    4) n-边连通:一个图的边连通度大于等于n,则该图是n-边连通。
    在这里插入图片描述
      关于连通的概念,大致就介绍这么多,下面来介绍匹配的概念,这个概念比较难以理解,其引出的相异代表系也是一个重要的概念。

    2.3.2 匹配

      在现实生活中,结婚问题、找工作问题都是常见的匹配问题,这些问题是有着比较深的数学内涵的,能用数学语言描述这类事物则需要引入匹配的概念,正如匹配这个概念的表面意思一样,匹配在一定意义上是对于顶点的划分和组合。首先介绍一系列概念:

      设G = (V,E)是一个图,图中任两条不邻接的边被称为是相互独立的,取出E的一个子集Y,如果Y中任意两条边是相互独立的,那么称YG的一个匹配最大匹配是指E中的边尽可能多地在Y中,使得Y中的边是最大的。

      不过最值得讨论的是偶图的匹配问题,设G = (V, E)是一个偶图,其顶点集合V可划分为V1V2,使得任一条边一端在V1中,一端在V2中,除此之外没有其他的可能。若可以找到一个匹配Y,使得Y = min{V1, V2},则称Y是偶图G的完全匹配。可以看出,偶图G的完全匹配是G的最大匹配,偶图的最大匹配未必是完全匹配(若有顶点是孤立的,没有任何边联结,那么就不存在完全匹配)。

      匹配问题是有实际意义的,若结婚问题、工作安排问题。下面叙述求解匹配问题的有解的充分必要条件:

    1.通俗化描述
    在这里插入图片描述
    2.格式化描述
    在这里插入图片描述
      读到这里,或许这些描述都过于抽象,数学上抽象是形式化的结果,而最初问题的产生是具体的,因此我们也还是用具体化的语言来描述这样抽象的事物:

      就拿结婚问题来说,这里的结婚问题不具有实际意义,只是用于通俗化描述的一个例子:结婚问题是指尽可能把小姑娘嫁出去,因此m个小姑娘,需要m个小伙子(n>=m)进行婚配,如果小姑娘们中意的小伙子很多,对于其中任意一位小伙子都可以接受,那么小姑娘是一定嫁得出去的。当然小姑娘可能中意的小伙子不多,那么就要为每位小姑娘仔细匹配,因此有下面几种情况

    • 对于任一位小姑娘而言,小姑娘中意的小伙子至少有1位,这也是通俗化描述中k = 1的情况;

    • 对于任k位小姑娘,这k位小姑娘中意的小伙子的集合的并中的元素个数应大于等于k,即问题的内部要有解,若小于k,问题肯定是没有解的,这也是通俗化描述中k = k的情况。

      有了上面两点,或许对于匹配问题已经有了一定的了解,那么对于相异代表系的问题,或许对于上面的描述是不理解的,但对于其求解应该有所了解了,下面看一道例题:

      设集合X={1, 2, 3, 4, 5, 6},则{1,2}{2,3}{3,4}{4,5}{5,6}{6,1},问X是否有相异代表系?

      答:有,可以把X={1, 2, 3, 4, 5, 6}看成小伙子集合,共有6个小伙子,而{1,2}{2,3}{3,4}{4,5}{5,6}{6,1}6个集合,可以看成是6个姑娘中意的小伙子名单,那么可以有下面的分配,这里的匹配是最大的完全的匹配:

    第一种分配方法第二种分配方法
    姑娘匹配的小伙子姑娘匹配的小伙子
    1112
    2223
    3334
    4445
    5556
    6661

      下面要开始介绍无向图的另一个重要的应用——平面图,平面图在图论的理论研究和实际应用中都占有很重要的地位。

    2.4 平面图和图的着色

    2.4.1 平面图

      无论是在印刷电路的布线中,还是地下管道的安排中,都需要解决一个问题,是否线路/管道能否不交叉?归结起来,就是确定一个图是否能够在一个平面中画出来而使得任何边都不交叉(除顶点相交外)?这也就是平面图应该考虑的问题了。

      平面图的定义是简单明了的,一个图的图解不交叉地画在平面上,则称其为图嵌入平面,那么已经嵌入平面的图称为平面图,可以嵌入平面的图称为可平面图。平面图的概念已经知道了,那么平面图的判定则是一个待解决的问题。不过了解解决这个问题之前得去了解一下平面图的性质:

      对于一个连通平面图而言,图的某个圈所围成的单连通区域称为内部面,而无界的那个连通区域称为外部面。内部面和外部面统称为面,对于一个图来说,图的顶点、边和面之间或许有一些联系:

    欧拉公式:设平面连通图有p个顶点q条边,且有f个面,那么有:p - q + f = 2

      虽然欧拉公式不是平面图的特征性质(充分必要条件),但是由此可以得到一些简单的否定条件:设平面连通图G(p,q)图,且每个面都是有长为n的圈围成的,则有

    • q = n(p - 2) / (n - 2),随着n的增大,q不断减小(p不变时),故q <= n(p - 2) / (n - 2)

    • n = 3, q = 3p - 6,由于圈的长度最少为3,那么对于所有平面连通图而言有q <= 3p - 6,当q = 3p - 6时边数最多,再加入边就会破坏图的可平面性,此时称其为最大平面图;

    • n = 4, q = 2p - 4,对于没有三角形的图而言,有q <= 2p - 4,当q = 2p - 4时边数最多。

      由此可以推出一些简单的结论:

    • K5和K3,3不是可平面图,这两个图时非常重要的图,需要牢记

    • 每个平面图中的顶点度的最小值不超过5

      通过这些条件可以判断一些图不是平面图:
    在这里插入图片描述

      对于图(A)而言,其有11个顶点,28条边,且有三角形,根据【对于所有平面连通图而言有q <= 3p - 6】可以判断图(A)不是平面图。
      对于图(B)而言,其有14个顶点,21条边,且圈长至少为6,则根据【q <= n(p - 2) / (n - 2)】,其中n取6,那么则有【q <= (3p-6)/2】,由此可以判断图(B)不是平面图。

      另外,Grinberg发现了平面图是哈密顿图的一个必要条件,因此导致了很多非哈密顿平面图的出现,在此不详述。下面来介绍一下平面图的充分必要条件:

    平面图的判定条件:一个图是可平面的,当且仅当它没有同胚于或者收缩到K5或K3,3的子图

      或许这个结论是令人有点失望的,因为它不够简单,以至于需要人们作出边加细/边收缩之后再去判断图的可平面性,这显然是具有一定工作量的。来看看下面两个例子:
    在这里插入图片描述
      图C和D是平面图,欢迎大家在评论区讨论它们的证明方法!

    2.4.2 图的着色

      图的着色问题起初来自于人们绘制地图时希望用最少的颜色给不同的国家上色,但却保证相邻国家的颜色不同。图的着色问题有顶点着色和边着色问题,在此仅简单讨论一下顶点着色。

      若能用n种颜色给图的顶点上色,而使得相邻顶点具有不同的颜色,那么称图是n–可着色的,而图的色数n的最小值,显然平凡图的色数是1,树的色数是2,偶图的色数也是2等。

      判断图是n–可着色的问题是NPC问题,是尚未求解的问题,在目前已经证明每一个平面图都是5–可着色的,而还没有通过数学证明的是四色猜想:每一个平面图都是4–可着色的

      图的着色问题在一定前提条件下是有解的,而且是简单的:

    • G是一个没有三角形的平面图,那么G是3–着色的。

    • 每个哈密顿平面图都是4–可着色

    2.5 有向图

      无向图为任何一种包含一个对称二元关系的有穷系统提供了数学模型,现在结束无向图的讨论,对于有向图而言,大部分结论是和无向图相同的,而本节将关注与无向图不同的性质。

    有向图:设V是一个有限非空集合,AV x V \ {(v, v) | v ∈V}的子集,则称二元组D = (V, A)为一个有向图。

      从定义可以看出,有向图实际上是一个反自反的非空有穷系统,其未必满足对称关系,它的很多性质和反自反的对称的非空有穷系统——无向图十分类似,如子图、同构等,下面主要介绍一下图的连通性问题,这是有向图和无向图的一个区别所在:

      定义通道、迹、路是很无向图类似的,而新的概念是半通道/弱通道、半路/弱路,它们是指有向图中不考虑方向时所形成的通道和路,也即把有向图当成无向图理解时,无向图中的通道和路是有向图中的半通道/弱通道、半路/弱路,针对这一情况,对于连通性有以下三种情况:

    1. 顶点uv互达:从u可以到达v,从v可以到达u
      – 若图中任两个顶点之间是互达的,那么称该图是强连通的,可以证明其充分必要条件是图中有一闭生成通道

    2. 顶点uv可达:从u可以到达v或者从v可以到达u
      – 若图中任两个顶点之间是可达的,那么称该图是单向连通的,其充分必要条件是图中有一生成通道

    3. 顶点u和v之间有一条弱路连接:顶点u和v之间有若干条不考虑方向的边相连接
      – 若图中任两个顶点之间是有一条弱路,那么称该图是弱连通的,其充分必要条件是图中有一条弱生成通道,直观地说则是略去图中的方向后得到的图是连通的。

      最后,介绍一下一类很重要的有向图,它们就是有向树、有根树、有序树的概念:

    • 有向树:一个没有弱圈的弱连通的有向图称为有向树;

    • 有根树:若有向树中恰有一个顶点的入度为0,而其余每个顶点的入度均为1,那么称这种有向树为有根树,入度为0的顶点即为根;

    • 有序树:若有根树的每个顶点的节点都有一定的次序,那么该有根树就是有序树。

      有序树就是数据结构中一类很重要的树结构,从它上面衍生出许许多多好的算法。

    2.6 重要性质总结

    1. 所有顶点的度数之和等于边的2倍(握手定理);

    2. 奇度顶点的个数是偶数个(握手定理的推论,对于无向图和有向图均适用);

    3. 树的顶点p和边数q有:p = q + 1

    4. p - q + f = 2(欧拉公式)

    5. 二叉树中 n0 = n2 + 1

    3. 近世代数

      近世代数是研究代数系统的理论。所谓代数系统,就是由一个非空集合S及定义在S上的若干个代数运算组成的一个系统,其中的代数运算可以是零元运算、一元运算、二元运算、…、n元运算,最常用的是二元运算。下面就开始介绍一些经典的代数系统,如半群、群、环和域、格等。

    3.1 代数系统

      可以认为代数系统就是集合、运算和运算规律之和,这里的集合一般是非空集合,而下面要讨论的是二元运算,比如常用的就是X * X → X,称为X上的二元运算,而运算律有以下几种:

    算律解释
    涉及一个二元运算
    结合律a * (b * c) = (a * b) * c
    交换律a * b = b * a
    消去律a * b = a * c → b = c
    幂等律a * a = a
    涉及两个不同的二元运算
    分配律a * (b + c) = (a * b) + (a * c)
    吸收律a * (b ○ c) = a

      正如看到的一样,不是所有的代数系统都满足所有的规律,也不是所有的代数系统都自动地满足其中几种规律,而且其中的*, +, ○不是通常意义上的运算符号,它们都只是示意符号。另外在代数系统中有一些特异元素。(从集合X中任取元素a

    特异元素解释
    单位元 ee * a = a
    零元 θθ * a = θ
    逆元 x和可逆元 yx * y = y * x = e
    幂等元aa * a = a

      对于代数系统而言,其基本的结构如下图所示,所有的代数系统都需要讨论下面的几个方面并有着其特征性质。

    在这里插入图片描述

    3.2 半群和群

    3.2.1 定义

    • 半群:具有满足结合律的二元代数运算的代数系;
    • 幺半群:有单位元的半群;
    • :有逆元的幺半群;
      • 交换群:满足交换律的群;
      • 中心C:所有可交换元素的集合;
      • M生成子群:由M生成的子群 <M>,包含M的所有子群的交,即包含M的最小的子群;
      • a生成子群:由元素a生成的子群<a>
      • 对称群:由Sym(S)对映射的合成构成的群,其中Sym(S)是从SS的所有一一对应之集,若S = {1, 2, 3, ..., n},那么Sym(S) = Sn(n次对称群);
      • 变换群Sym(S)的任一子群;
      • 置换群Sn的任一子群;
      • 循环群:若群G是由其中的某个元素a生成的,那么该群称为循环群,即G = <a>
      • 左/右陪集:设H是群G的一个子群,aG的任一元素。集合aH称为子群H的一个左陪集,集合Ha称为子群H的一个右陪集;H的左陪集和右陪集的个数相等;
      • 正规子群:设H是群G的子群,若对任意G中的元素aaH = Ha,则称HG的正规子群;交换群的任意子群都是正规子群,群的中心C也是正规子群,对于任一群G{e}G的正规子群;
      • 商群:群G的正规子群H的所有左陪集构成的集族,对群子集乘法构成的群称为GH的商群,即为G/H

    3.2.1 群的性质

    1. 有限群的元素均为有限阶,为群的阶的因子;

    2. 阶数小于6的群为交换群;

    3. (群的Caley同构定理) 任何一个群都同构于某个变换群,任一n阶有限群同构于n次对称群Sn的一个n阶子群,即有限群同构于某个置换群;

    4. 循环群必是交换群,循环群的子群也是循环群;

    5. 循环群G若是无限阶的,则G的生成元为aa^-1G的子群除{e}以外也是无限阶的;

    6. Gn阶的,则Gφ(n)个生成元(φ(n)是指小于等于n的且与n互质的数的个数),G的子群的阶是n的因子,且对于n的每个正因子d,在G中有且仅有一个d阶子群;

    7. 循环群G若是无限阶的,则;若Gn阶的,则G的子群的阶是n的因子;

    8. H是群G的子群,则H的所有左陪集构成的集族是G的一个划分;

    9. lagrange定理:|G| = |H| [G:H] → 素数阶群一定是循环群。

    3.3 环和域

      环和域是具有两个代数运算的代数系。

    3.3.1 环

      设R是一个非空集合,R中有两个代数运算,一个叫做加法并用"+"表示,另一个叫做乘法并用"*"表示,若:

    • < R, + >是一个Abel
    • < R, * >是一个半群
    • 乘法对加法满足左右分配律

      则称代数系< R, +, * >是一个环。

      例如整数集合Z在整数加法+和整数乘法*下为交换环,称为整数环< Z, +, *, 0, 1 >,简称整数环Z

    • < Z, +, 0 >是交换群
    • < Z, *, 1 >是有单位元的交换半群
    • 乘法对加法具有分配律

      在环中,若a ≠ 0b ≠ 0,但a * b = 0,那么称ab为零因子。下面介绍几个环的概念:

    1. 交换环:乘法满足交换律的环;

    2. 无零因子环:没有非零的左零因子,也没有非零的右零因子的环称为无零因子环,体和域中就没有零因子;

    3. 整环:可换的无零因子环。

    3.3.2 域

      若一个环满足以下两个条件:

    1. 它至少含有一个非零元素;

    2. 非零元素的全体对乘法构成一个群

      那么它被称为可换体即为

      例如有理数集合Q在有理数加法+和有理数乘法*下为域,称为有理数域< Q, +, *, 0, 1 >,简称域Q

    • < Q, +, 0 >是交换群
    • < Q, *, 1 >是有单位元的交换半群
    • < Q*, *, 1 >是有交换群(Q* = Q\{0}
    • 乘法对加法具有分配律

      如果< F, +, * >是一个体,则它由两部分组成:加法Abel< F, + >、乘法群< F\{0}, * >,它们之间由乘法对加法的左、右分配律联系起来,因此在体和域中,乘法有单位元素,非零元素对乘法有逆元。显然,在体和域中没有零因子。

    3.4 格与布尔代数

      格也是一种具有两个二元代数运算的代数系统,在这里,格的定义时颇费力气的。本节先把格定义为某种特殊的偏序集,然后再把格定义为一种具有两种代数运算的代数系。

    3.4.1 格

    1.格的偏序集定义

      偏序集(L, ≤)称为格,如果对L的任两个元素ab,上确界sup{a, b}和下确界inf{a, b}都存在。同时将上确界sup{a, b}记为a ∨ b,并称为ab的并;下确界inf{a, b}记为a ∧ b,并称为ab的交。

    2.格的代数定义

      <L,∨, ∧>是一个具有两个二元代数运算的代数系统,其中∨, ∧满足交换律、结合律、吸收律和幂等律,则<L,∨, ∧>是格。

    3.几种特殊的格

    1. 完备格:格中任一非空子集均有上确界和下确界的格;
    2. 有界格:格(L, ≤)L有零元素和单位元素;
      有限格是完备格,某些无限格也可以是完备格;完备格均是有界格。
    3. 有补格:设<L,∨, ∧, 0, 1>为有界格,若L中任一元素至少有一个补元素,则称其为有补格;
    4. 分配格:若格<L,∨, ∧>中∨对∧满足分配律,∧对∨满足分配律,则称该格为分配格;
    5. 有补分配格:有补分配格即为布尔代数;
    6. 模格:若格<L,∨, ∧>中对任意的a, b, c ∈ L有:如果a ≤ c,则a∨(b ∧ c) = (a ∨ b) ∧ c,则称该格为模格。

    3.4.2 布尔代数

      一个有补分配格称为布尔代数,记为<B,∨, ∧, ', 0, 1>。布尔代数是一个具有两个二元运算和一个一元运算的代数系统。


    1. 王义和. 离散数学引论-第3版[M]. 哈尔滨工业大学出版社, 2007 ↩︎

    2. 屈婉玲, 耿素云, 王捍贫.等离散数学[M].高等教育出版社, 2015 ↩︎

    展开全文
  • 2014年10月高等教育自学考试全国统一命题考试离散数学 试卷(课程代码02324)本试卷共4页。满分l00分,考试时间l50分钟。考生答题注意事项:1.本卷所有试题必须在答题卡上作答。答在试卷上无效。试卷空白处和背面均可...
  • 离散数学

    千次阅读 2019-08-20 22:25:56
    ∑符号表示求和 ∑读音为sigma,英文意思为Sum,Summation,就是和 其中i表示下界,n表示上界, k从i开始取数,一直取到n,全部加起来。 π表示求积 一,逻辑与证明 p v q ==> p or q p ∧ q ===> p and q p加...
  • 离散数学基础理论归纳
  • 离散数学 笔记整理

    千次阅读 2020-06-22 19:06:24
    离散数学 内容大纲 ╭1> 命题与命题公式 |2> 命题逻辑的推理理论 |3> 谓词逻辑 |4> 集合 |5> 关系与函数 离散数学 < |6> 代数系统的一般概念 |7> 格与布尔代数 |8> 图 ...
  • 文章目录离散数学教程1. 命题逻辑1.1 命题符号化1.1.1 概念1.1.2 形式化1.1.3 联结词否定词合取词析取词蕴涵词双向蕴涵词1.2 命题公式和分类1.2.1 组成成分1.2.2 命题公式的定义1.2.3 优先级1.2.4 分类1.2.5 关系1.3...
  • 离散数学学习总结

    千次阅读 多人点赞 2017-03-05 18:00:12
    总结 离散数学知识点 http://blog.csdn.net/icepointline/article/details/37878441 第二章 命题逻辑 1.→,前键为真,后键为假才为假;,相同为真,不同为假; 2.主析取范式:极小项(m)之和;主合取范式...
  • 离散数学 持续更新中
  • 离散数学-集合-偏序关系-12

    千次阅读 2020-04-09 15:29:26
    离散数学 集合与关系: 偏序关系: 定义: 哈斯图: 极大元、极小元: 最小元、最大元: 上界下界: 上确界、下确界: 上确界:最小的上界。 下确界:最大的下界。 ...
  • 离散数学学习笔记【第三篇】

    千次阅读 多人点赞 2019-06-14 23:07:32
    离散数学学习笔记【第三篇】
  • 离散数学(二)之特殊关系(内容来自冯伟森《离散数学》教材+课件)等价关系等价关系与等价类等价类的性质划分偏序关系定义哈斯图偏序集的特殊元素全序集与良序集全序集良序集合偏序与全序的转化 等价关系 等价关系与...
  • 离散数学学习笔记【第二篇】

    千次阅读 2019-04-22 00:10:50
    离散数学学习笔记【第二篇】
  • 离散数学 偏序集

    2021-07-29 10:00:37
    maximal element 极小元 minimal element 最大元 greatest element 最小元 least element 上界 upper bound 下届 lower bound 最小上界/上确界 least upper bound GUB 最大下界/下确界 greatest lower bound GLB 良...
  • 离散数学偏序关系

    2020-12-29 20:33:20
    概念 例 可比与不可比 例 哈斯图 例 全序集 例 最小(大)元与极小(大)元 例 上界下界
  • 离散数学复习

    2021-01-11 08:15:47
    离散数学复习 求等价类 解题步骤 先画出关系图 关系图每一个连通分支的节点构成的集合是一个等价类 注意:每个连通分支必须是对称的。 例子 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接...
  • 离散数学期末复习总结

    千次阅读 多人点赞 2021-01-02 00:09:37
    数学中常见数集 6.1.2 集合与元素的关系 有限集:集合中的元素是有限个 有限集的基: 无限集:集合中的元素无限个 6.1.3 集合之间的关系 子集 集合相等 真子集 若 A 中至少有一个元素不属于 B 注意区别元素与集合...
  • 离散数学之格论

    2020-08-19 11:46:12
    离散数学之格论 1.相关概念 首先回忆一下偏序集的相关概念:满足自反性、反对称性、传递性的集合。 格是一种特殊的偏序集:任意两个元素都有最大下界与最小上界。 在这里插入图片描述 两个格同构时,其哈斯图...
  • 离散数学-二元关系

    千次阅读 2021-02-22 09:16:36
    上界下界 序偶与有序n元组 由两个对象x、y组成的序列称为有序n元组,也称之为序偶,记作,称x,y为其中的第一元素和第二元素。 序偶中的x,y有次序。 如果和两个序偶,如果x=u且y=v,则两个序偶相等。 有序三元组是一...
  • 离散数学 01.02 关系

    2018-01-15 19:13:09
    关系
  • 离散数学】格

    2021-02-28 08:32:30
    格的对偶原理与离散数学中普遍存在的对偶原理本质上是一致的,强调的点是 ≤≤≤换成 ≥≥≥、 ∨\vee∨换成 ∧\wedge∧、 ∧\wedge∧换成 ∨\vee∨,具体内容就不讲了。 格的性质 ,∨,∧>,∨,∧>是由格 ,≤>,≤>...
  • 离散数学知识点总结(详细)

    千次阅读 2021-01-08 18:23:35
    离散数学知识点总结 第二章 命题逻辑 1.→,前键为真,后键为假才为假; <— >,相同为真,不同为假; 2.主析取范式:极小项 (m) 之和;主合取范式:极大项 (M)之积; 3.求极小项时,命题变元的肯定为 1,...
  • 离散数学考前复习:(四)关系

    千次阅读 2019-05-26 15:30:07
    离散数学考前复习:(四)关系 4.1 关系及其基本概念 二元关系:由两个元素 x 和 y,按照一定的顺序组成的二元组称为有序对,记作<x,y> List item ...
  • 离散数学笔记

    2018-01-11 09:37:41
    谓词是一个有确切意思的命题。...下界=小于等于最小元的所有元素 上确界=上界中的最小元 下确界=下界中的最大元。 不论怎么画总有交叉点为平面图 若干不相容的集合的集合最终的等于总集合为集合划分。  
  • 离散数学:格与布尔代数

    千次阅读 多人点赞 2018-05-26 08:37:17
    偏序集里的所有子集都有最大下界和最小上界时,称&lt;P, ≤&gt;为格。其中有补分配格称为布尔代数(有补,分配,有界)。布尔代数初导逻辑代数实质是符号逻辑,德摩根与布尔算是逻辑代数的创始人,布尔代数...
  • 离散数学_笔记

    2020-07-28 09:06:11
    内容大纲 ╭1> 命题与命题公式 |2> 命题逻辑的推理理论 ...离散数学 < |6> 代数系统的一般概念 |7> 格与布尔代数 |8> 图 ╰9> 图的应用 第一章:命题与命题公式 ╭1.命题与命题连接词...
  • 总结 离散数学知识点

    万次阅读 多人点赞 2014-07-16 15:18:18
    总结 离散数学知识点 第二章 命题逻辑 1.→,前键为真,后键为假才为假;—>,相同为真,不同为假; 2.主析取范式:极小项(m)之和;主合取范式:极大项(M)之积; 3.求极小项时,命题变元的肯定为1,否定为0,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 765
精华内容 306
关键字:

离散数学上界下界