离散数学课程论文

离散数学课程论文

——图论部分

姓名： XXX 学号：11281068 班系：计科1103

学院：计算机与信息技术学院 课程名：离散数学 指导老师：胡俊

摘要：图论属于数学的一个分支，它是一个年轻但却迅速成熟的学科，它主要是研究事

物之间的客观规律。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。

关键词：图；有向图；回路；最短路径；欧拉图；树；权

引言：对于网络的研究，最早是从数学家开始的，其基本的理论就是图论，它也是目前组

合数学领域最活跃的分支。我们在复杂网络的研究中将要遇到的各种类型的网络，无向的、有向的、加权的……这些都可以用图论的语言和符号精确简洁地描述。图论不仅为物理学家提供了描述网络的语言和研究的平台，而且其结论和技巧已经被广泛地移植到复杂网络的研究中。图论，尤其是随机图论已经与统计物理并驾齐驱地成为研究复杂网络的两大解析方法之一。

正文：

（一） 离散数学的知识体系总括

离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学

基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

离散数学的四大核心是：代数系统、集合论、数理逻辑、图论。可见图论占据着不可替代的作用。

离散数学结构图

（二） 图论的起源

哥尼斯堡桥问题

aCdcebfDgCcAdebaBfDgAB? 古普鲁士哥尼斯堡城的Pregel有七座桥将四块陆地相连。

? 从任一陆地出发走遍七座桥（而且只走一次）再回到原地是否可行？ ? 1736年Euler（欧拉：圣彼得堡大学的数学教授）证明无解。

? 连通图每点连接的边数为偶数才能有解。

这就是后来的欧拉路径和欧拉回路。这项工作使欧拉成为图论〔及拓扑学〕的创始人。

（三） 图论的基本概念和定理

图论是一个重要的数学分支。数学家欧拉1736年发表了关于图论的第一论文，解决了著名的哥尼斯堡七桥问题。克希霍夫对电路网络的研究、凯来在有机化学的计算中都应用了树和生成树的概念。随着科学技术的发展，图论在运筹学、网络理论、信息论、控制论和计算机科学等领域都得到广泛的应用。在这里，我将简单给出图、简单图、完全图、子图、路和图的同构等概念，接着研究一下连通图性质和规律，给出邻接矩阵、可达性矩阵、连通矩阵和完全关联矩阵的定义。最后我将介绍下欧拉图与哈密尔顿图、树、二部图、平面图和图的着色。

1. 一些常见的基本概念

（1） 图的定义

无向图 每一条边都是无向边的图称无向图 。 有向图 每一条边都是有向边的图称有向图 。 邻接边关联于同一顶点的两条边，被称为邻接边。

邻接点 若两个顶点由同一条边关联，则这两个顶点被称为是邻接点。 孤立顶点 不与任何顶点相邻接的顶点，被称为孤立顶点。 零图仅由若干孤立顶点组成的图，被称为零图 。 阶图G的顶点个数称为图G的阶

平凡图 仅由一个孤立顶点构成的图，被称为平凡图。

自回路或环 关联于同一顶点的一条边，被称为自回路或闭环。 平行边若有两条有向边，他们的起点和终点相同，称他们为有向平行边。

我们把联结于一对顶点间的多条边称为平行边。 简单图不含有任何平行边和自回路的图，被称为简单图。 多重图 任何含有平行边的图 ，被称为多重图。

完全图 简单图G=中，若每对顶点间都有边相连，则称该图为完全图。 无向完全图有n个顶点的无向完全图记作Kn。

Kn的边数n个顶点的无向完全图Kn的边数为 n ? (n-1)/2.

对称有向图对于无向图G，将G中的每条边用两条与e有相同端点的对称边e和e‘来代替后得到的一个有向图 。

有向完全图 对Kn中每条边任意确定一个方向，称该图为n顶点的有向完全图。 有向完全图的边数n个顶点的有向完全图边数也为n(n-1)/2 。

完全有向图完全图的对称有向图称为完全有向图(complete digraph），记作 * 。

Kn（2） 图的顶点度数

无向图

G?V,E，的度数记

d(vi)指与

vi相关联的边的条数。