《离散数学》

课程设计

学    院         计算机学院              

学生姓名                                

学    号                                

指导教师                                

评阅意见                                    

                                           

                                           

提交日期  2011  年 11  月 25  日

引言

《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。

实验一、  编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性）

一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之间存在的关系。

二、数学原理：自反、对称、传递关系

设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R就是A×B的一个合于R={(x,y)∈A×B|xRy}的子集合

设R是集合A上的二元关系：

自反关系：对任意的x∈A,都满足<x,x>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的Û("x)((x∈A)→(<x,x>∈R))=1

对称关系：对任意的x,y∈A，如果<x,y>∈R，那么<y,x>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的 Û ("x)("y)((x∈A)∧ (y∈A)∧(<x,y>∈R)→(<y,x>∈R))=1

传递关系：对任意的x,y,z∈A，如果<x,y>∈R且<y,z>∈R，那么<x,z>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的Û ("x)("y)("z)[(x∈A)∧(y∈A)∧(z∈A)∧((<x,y>∈R)∧(<y,z>∈R)→(<x,z>∈R))]=1

三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。

图示：

四、实验环境：Windows 7 Ultimate     DEV C++

五、实验语言：C 语言

六、程序源代码：

#include"stdio.h"

#define N 4

main()

{

  int i,j,k;

  int f,e,z;

  int M[N][N];

  printf("判断R是否为自反关系、对称关系、是否可传递？\n");

  printf("请输入一个4*4的矩阵。\n");

  for(i=0;i<N;i++) /*输入一个4*4的矩阵*/

      for(j=0;j<N;j++)

          scanf("%d",&M[i][j]);

      for(i=0;i<N;i++)

        {

          for(j=0;j<N;j++)

            printf("%4d",M[i][j]);

          printf("\n");

        }

  

   for(i=0;i<N;i++)

   {

     if(M[i][i]==1)//判断自反性

     { 

        if(i=N-1

          e=0;

         

          else

          ;

     }

       else if(M[i][i]==0)//判断反自反性

       {

          if(i=N-1)

          e=1;         

         

          else

          ;

       }

       else

       {

          e=2;

          break;

       }

   } 

      

   for(i=0;i<N;i++)

   {

       for(j=0;j<N;j++)

      

       if(M[i][j]!=M[j][i])//判断对称性

             {                                       

              f=1;          

              break;

              }

    }        

  

   for(i=0;i<N;i++)

   {

       for(j=0;j<N;j++)

            

       if(M[i][j]==1)//判断反对称性

             {

               if(M[j][i]==0)

               {

                  if(i==(N-1)&&j==N-1)

                  f=0;

                  else

                  break;

                  }

             }

              

          

   }

   if(f!=0&&f!=1)

             {

              f=2;

             

             }

      

     

   for(i=0;i<N;i++)//判断可传递性

       for(j=0;j<N;j++)

           if(M[i][j]==1)

              continue;

           else

              for(k=0;k<N;k++)

                  if(M[i][k]*M[k][i]==0)

                     continue;

                  else

                     z=0;

                     

   if(e==0)

      printf("关系R是自反关系\n");

   else if(e==1)

      printf("关系R是反自反关系\n");

   else if(e==2)

      printf("关系R是反自反关系\n");

   if(f==0)

      printf("关系R是反对称关系\n");

   else if(f==1)

      printf("关系R不是对称关系\n");

   else if(f==2)

      printf("关系R是对称关系\n");

   if(z==0)

      printf("关系R是不可传递关系\n");

   else

      printf("关系R是可传递关系\n");

      

                          

   system("PAUSE");

}

七、程序运行截图：

i、程序启动截图：

ii、程序输入截图：

iii、程序运行结果截图:

八、实验总结：实验简洁高效地判断二元关系的性质。

实验二、编程求一个二元关系的自反闭包、对称闭包、传递闭包

一、前言引语

一个二元关系可能具有某种性质，也可能不具有这种性质。现在讨论怎样使一个二元关系变成具有指定性质的新关系，并且还要满足最小性条件。

二、数学原理

    自反闭包、对称闭包、传递闭包

设R是定义在A上的二元关系，若存在A上的关系R′满足：

1)      R′是自反的(或对称的、或可传递的)，

2)      RÍ R′，

3)      对A上任何其它满足 1）和 2）的关系R〞，都有： R′Í R〞。           则称R′为R的自反闭包(或对称闭包、或传递闭包)，分别记为r(R)、(s(R)和t(R))。

三、实验原理

    Warshall算法的基本思想

对每个结点（从第一列开始），找出所有具有到此结点的有向边的结点（即该列中元素为1的所在行的结点），再将这些结点所在行同该结点所在行进行逻辑加后作为这些结点所在的新行（添加新的有向边）（反映了如果这些结点没有到其它结点的有向边，但有到该结点的有向边，再通过该结点间接到达其它结点，根据传递闭包的定义，这些结点就必然有一条有向边到达其它结点）。

• 设R是集合上的二元关系,Mr是R的关系矩阵
• (1)置新矩阵A:=Mr
• (2)置(列)  j:=1
• (3) 对所有的i(1≤i≤n)

      如A(i,j)=1,则对k=1,2,…,n

        A(i,k):=A(i,k) Ú A(j,k)

• (即将A的第i行与A的第j行进行逻辑加后送回A的第i行)
• (4)j:=j+1
• (5)如j≤n转(3),否则停止。

四、实验环境：Windows 7 Ultimate    DEV C++

五、实验编程语言： C语言

六、实验程序源代码

//source file: War.cpp

#include<stdio.h>

void War(int m,int n)

{

int i,j,k;设置临时变量

int a = 0, b = 0;设置临时变量

int arr[10][10];

for(a = 0; a < m; ++a)

{

printf("请输入矩阵第%d行元素:",a);

for(b = 0; b < n; ++b)

{

scanf("%d",&arr[a][b]);

}

printf("\n");

}

for(i = 0; i < m; i++)

{

for( j= 0; j < m; j++)

{

if(arr[j][i] == 1)

{

for(k = 0;k < n; k++)

{

arr[j][k]=arr[i][k] || arr[j][k];

}

}

}

}

printf("所得的可传递闭包关系矩阵是：\n");

for(i = 0;i < m; ++i)

{

for(j = 0;j < n; ++j)

{

printf("%d ",arr[i][j]);

}

printf("\n");

}

}

//file: test.cpp

#include<stdio.h>

void main()

{

   printf("利用Warshall算法求二元关系的可传递闭包\n");

void War(int , int);

int m, n;

printf("请输入矩阵的行数(必须小于10）：");

scanf("%d", &m);

printf("请输入矩阵的列数(必须小于10）：");

scanf("%d", &n);

War(m, n);

system ( “PAUSE”);

return 0;

}

七、实验截图

i.程序启动画面：

ii.输入关系矩阵的行数和列数以及关系矩阵的各个元素。

 

iii.得出结果，并打印在屏幕上。

八、实验总结

如果当一个集合的元素的个数n很大时，求在该集合上的二元关系的可传递闭包是非常复杂的。幸好Warshall算法给我们提供了一个求二元关系的可传递闭包的高效方法。结合计算机程序技术，利用warshall算法我们可以轻松的求出一个二元关系的可传递闭包。本次实验便捷高效地达到了实验的目的。

实验三、编程求一个二元关系的复合运算

一、实验引语：关系作为集合，除了具有一般的运算功能外，还具有自身独特的复合运算。

二、数学原理

设R是集合A到B的二元关系，S是集合B到C的二元关系，则

R。S = ｛（x，z） A  C|(y B)[(x，y)  R ∧ （y，z）S]｝称为R和S的复合关系。

三、实验原理：矩阵的运算

四、实验环境：Windows 7 Ultimate     DEV C++

五、实验语言：C语言

六、实验程序源代码

#include"stdio.h"

#include"string.h"

#define M 3

#define N 3

#define P 3

main()

{

  int i,j,k,x;

  char p;

  int A[N][M],B[M][P],C[N][P];

  printf("关系的复合运算\n");

  printf(“请输入一个3*3的矩阵”);

  printf("A:\n");

  for(i=1;i<=N;i++)

  {

    for(j=1;j<=M;j++)

      scanf("%4d",&A[i][j]);

    printf("\n");

  }

  printf(“请输入一个3*3的矩阵”);

  printf("B:\n");

  for(i=1;i<=M;i++)

  {

    for(j=1;j<=P;j++)

      scanf("%4d",&B[i][j]);

    printf("\n");

  }

  printf("经过复合运算后得到C:\n");

  for(i=1;i<=N;i++)

  {

    for(j=1;j<=P;j++)

    {

      x=0;

      for(k=1;k<=M;k++)

        x=x+A[i][k]*B[k][j];

       

      if(x>0)

        C[i][j]=1;

      else

        C[i][j]=0;

      printf("%4d",C[i][j]);

    }

    printf("\n");

  }

 

  system("PAUSE");

  return 0;

}

七、程序运行截图：

i、程序启动截图：

ii、程序输入截图:

iii、程序运行结果截图：

八、实验总结：本实验利用计算机技术，快速便捷地实现了关系的运算，极大提高了效率。

实验四：编程实现拓扑排序算法

一、实验引言

一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成,，任务之间具有先后关系，任务的先后顺序可用有向图表示。

二、数学原理：拓扑排序

   i）定义：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

   ii）实现方法：

      ①从有向图中选择一个没有前驱的顶点并输出它。

      ②从网中删去该顶点并删去从该顶点发出的全部有向边。

      ③重复上述两步直到剩余的网中不存在没有前驱的顶点。

三、实验原理

首先对有向图，我们采取邻接表作为数据结构。且将表头指针改为头结点，其数据域存放该结点的入度，入度设为零的结点即没有前趋。

在建立邻接表输入之前，表头向量的每个结点的初始状态为数据域VEX（入度）为零，指针域NXET为空，每输入一条弧< J, K > 建立链表的一个结点，同时令k 的入度加1，因此在输入结束时，表头的两个域分别表示顶点的入度和指向链表的第一个结点指针。

在拓扑排序的过程之中，输入入度为零（即没有前趋）的顶点，同时将该顶点的直接后继的入度减1。

（1）、查邻接表中入度为零的顶点，并进栈。

（2）、当栈为空时，进行拓扑排序。

（a）、退栈，输出栈顶元素V。

（b）、在邻接表中查找Vj的直接后继Vk，将Vk的入度减一，并令入度减至零的顶点进栈。

（3）、若栈空时输出的顶点数不是N个则说明有向回路，否则拓扑排序结束。为建立存放入度为零的顶点的栈，不需要另分配存储单元，即可借入入度为零的数据域。一方面，入度为零的顶点序号即为表头结点的序号，另一方面，借用入度为零的数据域存放带链栈的指针域（下一个入度的顶点号）。

四、实验环境：Windows 7 Ultimate   DEV C++

五、实验语言：C++

六、程序源代码

#include<iostream>

#include<cmath>

#include<cstdio>

#include<algorithm>

#include<stack>

using namespace std;

#define MAX 9999

stack<int>mystack;

int indegree[MAX];

struct node

{

    int adjvex;

    node* next;

}adj[MAX];

int Create(node adj[],int n,int m)//邻接表建表函数，n代表定点数，m代表边数

{

    int i;

    node *p;

    for(i=0;i<=n-1;i++)

    {

        adj[i].adjvex=i;

        adj[i].next=NULL;

    }

    for(i=0;i<=m-1;i++)

    {

        cout<<"请输入第"<<i<<"条边:";

        int u,v;

        cin>>u>>v;

        p=new node;

        p->adjvex=v;

        p->next=adj[u].next;

        adj[u].next=p;

    }

    return 1;

}

void print(int n)//邻接表打印函数

{

    int i;

    node *p;

    for(i=0;i<=n-1;i++)

    {

        p=&adj[i];

        while(p!=NULL)

        {

            cout<<p->adjvex<<' ';

            p=p->next;

        }

        cout<<endl;

    }

}

void topsort(node adj[],int n)

{

    int i;

    node *p;

    memset(indegree,0,sizeof(indegree));

    for(i=0;i<=n-1;i++)

    {

        p=adj[i].next;

        while(p!=NULL)

        {

            indegree[p->adjvex]++;

            p=p->next;

        }

    }

    for(i=0;i<=n-1;i++)

    {

        if(indegree[i]==0)

            mystack.push(i);

    }

    int count=0;

    while(mystack.size()!=0)

    {

        i=mystack.top();

        mystack.pop();

        cout<<i<<' ';

        count++;

        for(p=adj[i].next;p!=NULL;p=p->next)

        {

            int k=p->adjvex;

            indegree[k]--;

            if(indegree[k]==0)

                mystack.push(k);

        }

    }

    cout<<endl;

    if(count<n)cout<<"有回路"<<endl;

}

int main()

{

    int n;

    int m;

    cout<<"拓扑排序算法"<<endl;

    cout<<"请输入顶点数及边数:";

    cin>>n>>m;

    Create(adj,n,m);

    cout<<"输入的邻接表为:"<<endl;

    print(n);

    cout<<"拓扑排序结果为:"<<endl;

    topsort(adj,n);

    system("pause");

    return 0;

}

七、程序运行截图

以下图为例：

i、程序启动截图

ii、程序输入截图

   iii、程序运行结果截图

八、实验总结

  通过本次实验掌握拓扑排序的算法，了解拓扑排序的有向图的数据结构。

参考文献

1.《离散数学》 冯伟森、栾新成、石兵等编著           机械工业出版社

2.《C语言程序设计》 陈良银、游洪跃、李旭伟等编著   清华大学出版社

    3.《C++：面向对象程序设计》 李涛、游洪跃等编        高等教育出版社