摘要:离散数学是高等学校计算机和数学等专业的基本课程之一。该文主要就教学过程中发现图论部分图的矩阵表示中的一些定义和例题的不一致性进行探讨,并提出一些改进的意见和建议。
关键词:图;出度;入度;关联矩阵;邻接矩阵
中图分类号:O158文献标识码:A文章编号:1009-3044(2011)08-1853-02
离散数学是研究离散量的结构及其相互关系的数学学科,是现代数学的一个重要分支。它在各学科领域,特别在计算机科学技术领域有着广泛的应用,同时离散数学也是计算机专业的许多专业课程,如程序设计、数据结构操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习,不但可以掌握处理离散结构的描述工具和方法,为后续课程的学习创造条件,而且可以提高抽象思维和严格的逻辑推理能力,为将来参与创新性的研究和开发工作打下坚实的基础。
高等教育出版社出版的离散数学教材,是面向21世纪课程教材,是普通高等教育“十一五”国家级规划教材。该教材相比其修订版及其他教材具有明显优点:语言组织简练易懂,内容中心突出,知识体系清晰,知识点分布更加合理等。
下面是笔者在教学过程中发现的一个小问题,在这里提出来和大家一起探讨。本书第五部分图论中第275页有如下定义:
定义14.4:设G=
而在第288-289页图的矩阵表示中有如下定义:
定义14.24:设有向图D=
(1)
则称(mij)n×m为D的关联矩阵,记作M(D)。
作为例题,书中给出了图:
的关联矩阵:
(2)
并得到矩阵M(D)具有如下的性质:
1)每一列恰好有一个+1和一个-1。
2)-1的个数等于+1个数,都等于边数m,这正是有向图握手定理的内容。
3)第i行中,+1的个数等于d+(νi),-1的个数等于d-D(νi)。
4)平行边所对应的列相同。
由定义14.4和定义14.24,我们发现结论和定义出现了矛盾。如结论3为:+1的个数等于d+(νi),-1的个数等于d-D(νi)。按照定义14.24中1和-1的定义,该结论可解释为:νi作为边ei的始点的次数之和等于d+(νi),νi作为边ei的终点的次数之和等于d-(νi)。而这与定义14.4中,称ν作为边的始点的次数之和为 的出度,简记为d-(ν)。称ν作为边的终点的次数之和为ν的人度,简记为d+(ν)相矛盾。另外,我们再看如下定义:
定义14.25:有向图D=
作为例题,书中给出了图:
邻接矩阵:
并且得到矩阵A具有如下的性质:
(3)
(4)
于是,,即A(D)中所有元素之和等于边数,这也正是有向图握手定理的内容。
事实上,因为a(1)ij为顶点νi邻接到顶点νj边的条数,则有 表示顶点νi作为边的始点的个数,即顶点νi的出度,由定义14.4,即为d-(ν),因此(1)矛盾。类似的,定义14.4也与(2)矛盾。
修改的方法很多,比如:我们可以修改定义14.4,但这不是很明智的。该文的修改主要是针对定义14.24中mij的取法以及上述两个例题及相关结论的修改。
定义14.24:设有向图D=
(5)
则称(mij)n×m为D的关联矩阵,记作M(D)。
则图的关联矩阵改为:
(6)
此时其性质3仍然可以保持不变。
对于定义14.25:我们只需将性质(1)和(2)作如下修改:
(7)
(8)
这样一来,我们的定义14.4、14,24、14.25和相应的例题及结论则能保持一直,既增加了本书的可读性,同时,读者在理解时也能轻松许多。
参考文献:
[1] 屈婉玲,耿素云,张立昂.离散数学[M].北京:高等教育出版社,2008.
[2] 左孝凌,李为鑑,刘永才.离散数学[M].上海:上海科学技术文献出版社,1982.
[3] Rosen K H.Discrete Mathematics and its Applications:影印版[M].北京:机械工业出版社,2004.