离散数学形成性考核作业4

离散数学形成性考核作业4一、集合论部分

（一）集合的基本概念1.集合的定义：具有某种特定性质的事物的总体称为集合。集合中的事物称为元素。例如，全体自然数构成一个集合，每个自然数就是这个集合的元素。2.集合的表示方法列举法：将集合中的元素一一列举出来，写在大括号内。例如，集合\(A=\{1,2,3,4\}\)。描述法：用谓词\(P(x)\)表示\(x\)具有性质\(P\)，集合\(A=\{x|P(x)\}\)。例如，集合\(B=\{x|x\)是偶数\(\}\)。

（二）集合的运算1.并集：设\(A\)、\(B\)是两个集合，则它们的并集\(A\cupB=\{x|x\inA\)或\(x\inB\}\)。例如，\(A=\{1,2,3\}\)，\(B=\{3,4,5\}\)，则\(A\cupB=\{1,2,3,4,5\}\)。2.交集：\(A\capB=\{x|x\inA\)且\(x\inB\}\)。对于上述例子，\(A\capB=\{3\}\)。3.差集：\(AB=\{x|x\inA\)且\(x\notinB\}\)。这里\(AB=\{1,2\}\)。4.补集：设\(U\)是全集，\(A\subseteqU\)，则\(A\)的补集\(\overline{A}=UA=\{x|x\inU\)且\(x\notinA\}\)。

（三）集合的关系1.包含关系：若集合\(A\)的每一个元素都是集合\(B\)的元素，则称\(A\)包含于\(B\)，记作\(A\subseteqB\)。例如，\(\{1,2\}\subseteq\{1,2,3\}\)。2.相等关系：若\(A\subseteqB\)且\(B\subseteqA\)，则称\(A\)与\(B\)相等，记作\(A=B\)。

（四）集合运算的性质1.交换律：\(A\cupB=B\cupA\)，\(A\capB=B\capA\)。2.结合律：\((A\cupB)\cupC=A\cup(B\cupC)\)，\((A\capB)\capC=A\cap(B\capC)\)。3.分配律：\(A\cap(B\cupC)=(A\capB)\cup(A\capC)\)，\(A\cup(B\capC)=(A\cupB)\cap(A\cupC)\)。4.德摩根律：\(\overline{A\cupB}=\overline{A}\cap\overline{B}\)，\(\overline{A\capB}=\overline{A}\cup\overline{B}\)。

（五）集合的基数1.有限集与无限集：集合中元素的个数称为集合的基数。如果集合的基数是有限的，则称为有限集；否则称为无限集。例如，集合\(\{1,2,3\}\)是有限集，自然数集\(N\)是无限集。2.计算有限集的基数：对于有限集\(A\)，其基数记作\(|A|\)。例如，\(|\{1,2,3,4\}|=4\)。

二、二元关系部分

（一）二元关系的定义1.有序对：由两个元素\(x\)和\(y\)按一定顺序组成的二元组称为有序对，记作\((x,y)\)。例如，\((1,2)\)与\((2,1)\)是不同的有序对。2.二元关系：设\(A\)、\(B\)是两个集合，\(A\timesB=\{(x,y)|x\inA\)且\(y\inB\}\)的任何子集\(R\)称为从\(A\)到\(B\)的二元关系。特别地，当\(A=B\)时，\(R\)称为\(A\)上的二元关系。例如，\(A=\{1,2\}\)，\(B=\{a,b\}\)，\(A\timesB=\{(1,a),(1,b),(2,a),(2,b)\}\)，若\(R=\{(1,a),(2,b)\}\)，则\(R\)是从\(A\)到\(B\)的二元关系。

（二）二元关系的表示方法1.集合表示法：如上述\(R=\{(1,a),(2,b)\}\)就是用集合表示二元关系。2.关系矩阵：设\(A=\{x_1,x_2,\cdots,x_m\}\)，\(B=\{y_1,y_2,\cdots,y_n\}\)，\(R\)是从\(A\)到\(B\)的二元关系，则\(R\)的关系矩阵\(M_R=(r_{ij})_{m\timesn}\)，其中\(r_{ij}=\begin{cases}1,&(x_i,y_j)\inR\\0,&(x_i,y_j)\notinR\end{cases}\)。例如，\(A=\{1,2\}\)，\(B=\{a,b\}\)，\(R=\{(1,a),(2,b)\}\)，则关系矩阵\(M_R=\begin{pmatrix}1&0\\0&1\end{pmatrix}\)。3.关系图：以集合\(A\)和\(B\)中的元素为顶点，若\((x,y)\inR\)，则从顶点\(x\)到顶点\(y\)画一条有向边，这样得到的图就是关系图。

（三）二元关系的运算1.复合关系：设\(R\)是从\(A\)到\(B\)的二元关系，\(S\)是从\(B\)到\(C\)的二元关系，则\(R\)与\(S\)的复合关系\(R\circS=\{(x,z)|\existsy\inB\)，使得\((x,y)\inR\)且\((y,z)\inS\}\)。例如，\(A=\{1,2\}\)，\(B=\{a,b\}\)，\(C=\{c,d\}\)，\(R=\{(1,a),(2,b)\}\)，\(S=\{(a,c),(b,d)\}\)，则\(R\circS=\{(1,c),(2,d)\}\)。2.逆关系：设\(R\)是从\(A\)到\(B\)的二元关系，则\(R\)的逆关系\(R^{1}=\{(y,x)|(x,y)\inR\}\)。例如，\(R=\{(1,a),(2,b)\}\)，则\(R^{1}=\{(a,1),(b,2)\}\)。

（四）二元关系的性质1.自反性：设\(R\)是集合\(A\)上的二元关系，如果对于\(A\)中的每一个元素\(x\)，都有\((x,x)\inR\)，则称\(R\)是自反的。例如，\(A=\{1,2,3\}\)，\(R=\{(1,1),(2,2),(3,3),(1,2)\}\)，\(R\)是自反的。2.反自反性：如果对于\(A\)中的每一个元素\(x\)，都有\((x,x)\notinR\)，则称\(R\)是反自反的。例如，\(R=\{(1,2),(2,3)\}\)在\(A=\{1,2,3\}\)上是反自反的。3.对称性：设\(R\)是集合\(A\)上的二元关系，如果对于任意的\((x,y)\inR\)，都有\((y,x)\inR\)，则称\(R\)是对称的。例如，\(R=\{(1,2),(2,1)\}\)在\(A=\{1,2\}\)上是对称的。4.反对称性：如果对于任意的\((x,y)\inR\)且\((y,x)\inR\)，必有\(x=y\)，则称\(R\)是反对称的。例如，\(R=\{(1,2)\}\)在\(A=\{1,2\}\)上是反对称的。5.传递性：设\(R\)是集合\(A\)上的二元关系，如果对于任意的\((x,y)\inR\)，\((y,z)\inR\)，都有\((x,z)\inR\)，则称\(R\)是传递的。例如，\(R=\{(1,2),(2,3),(1,3)\}\)在\(A=\{1,2,3\}\)上是传递的。

（五）等价关系与偏序关系1.等价关系定义：设\(R\)是集合\(A\)上的二元关系，如果\(R\)是自反的、对称的和传递的，则称\(R\)是\(A\)上的等价关系。等价类：设\(R\)是\(A\)上的等价关系，对于任意的\(x\inA\)，称集合\([x]_R=\{y\inA|(x,y)\inR\}\)为\(x\)关于\(R\)的等价类。商集：集合\(A\)在等价关系\(R\)下的商集\(A/R=\{[x]_R|x\inA\}\)。例如，\(A=\{1,2,3,4\}\)，\(R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\}\)，\([1]_R=\{1,2\}\)，\([3]_R=\{3,4\}\)，\(A/R=\{[1]_R,[3]_R\}\)。2.偏序关系定义：设\(R\)是集合\(A\)上的二元关系，如果\(R\)是自反的、反对称的和传递的，则称\(R\)是\(A\)上的偏序关系，记作\(\preceq\)。偏序集：集合\(A\)与\(A\)上的偏序关系\(\preceq\)一起称为偏序集，记作\((A,\preceq)\)。例如，\(A=\{1,2,3\}\)，\(R=\{(1,1),(2,2),(3,3),(1,2)\}\)，\((A,R)\)是偏序集。哈斯图：用于表示偏序关系的一种图形，通过元素之间的位置关系直观地反映偏序关系。

三、图论部分

（一）图的基本概念1.图的定义：图\(G\)由顶点集\(V(G)\)和边集\(E(G)\)组成，记作\(G=(V,E)\)。例如，\(V=\{v_1,v_2,v_3\}\)，\(E=\{(v_1,v_2),(v_2,v_3)\}\)，则\(G=(V,E)\)是一个图。2.有向图与无向图：若图的边是有方向的，则称为有向图；若边是无方向的，则称为无向图。3.顶点的度数：对于无向图\(G\)，顶点\(v\)的度数\(d(v)\)是与\(v\)关联的边的条数。对于有向图，顶点\(v\)的入度\(d^(v)\)是进入\(v\)的边的条数，出度\(d^+(v)\)是从\(v\)出去的边的条数，顶点度数\(d(v)=d^+(v)+d^(v)\)。

（二）图的连通性1.通路与回路通路：在图\(G\)中，从顶点\(v_i\)到顶点\(v_j\)的顶点与边的交替序列\(v_ie_1v_{i_1}e_2\cdotse_kv_j\)称为通路。回路：若通路的起点与终点相同，则称为回路。2.连通图：若无向图\(G\)中任意两个顶点都是连通的，则称\(G\)是连通图。例如，一个无向图中任意两点之间都存在路径相连，则它是连通图。

（三）图的矩阵表示1.邻接矩阵：对于无向图\(G=(V,E)\)，\(V=\{v_1,v_2,\cdots,v_n\}\)，其邻接矩阵\(A=(a_{ij})_{n\timesn}\)，其中\(a_{ij}=\begin{cases}1,&(v_i,v_j)\inE\\0,&(v_i,v_j)\notinE\end{cases}\)。对于有向图，\(a_{ij}\)表示从\(v_i\)到\(v_j\)的边的条数。2.可达矩阵：设\(G=(V,E)\)是有向图，\(V=\{v_1,v_2,\cdots,v_n\}\)，其可达矩阵\(P=(p_{ij})_{n\timesn}\)，其中\(p_{ij}=\begin{cases}1,&从v_i到v_j存在通路\\0,&从v_i到v_j不存在通路\end{cases}\)。

（四）欧拉图与哈密顿图1.欧拉图定义：无向图\(G\)中，若存在一条经过每条边一次且仅一次的回路，则称\(G\)为欧拉图。判定定理：无向连通图\(G\)是欧拉图当且仅当\(G\)中所有顶点的度数都是偶数。2.哈密顿图定义：无向图\(G\)中，若存在一条经过每个顶点一次且仅一次的回路，则称\(G\)为哈密顿图。判定定理：设\(G\)是\(n(n\geq3)\)阶无向简单图，如果对于\(G\)中任意两个不相邻的顶点\(u\)和\(v\)，均有\(d(u)+d(v)\geqn\)，则\(G\)中存在哈密顿回路，即