图论在学习资源优化配置中的应用 毕业论文(11)

图论在学习资源优化配置中的应用 毕业论文

1 引言

高校扩招顺应了时代发展的需要，各高校都纷纷建立新校区以接纳扩招学生，只是高校建设不仅需要资源也需要时间，其发展不能与学生增长同步，从而高校教育环境、师资等问题日益突出。在校生规模扩大及新校区新增教学资源都使教育管理难度加大，管理事务增多，教师资源、管理人员等都在不同程度上存在与招生规模增长不适应的问题。这些都在对教育管理方面出难题，寻求高效快捷的管理方法成了当务之急。

图论是数学的一个分支，它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。近几十年来，图论得到广泛的应用，尤其在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、社会科学、经济学、建筑学等问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。其应用于教育管理方面的理论也是值得我们研究探讨的。本文将以图论作为理论基础，通过对学生学习过程以及学习资源的研究，有效地指导教学管理实践，优化教学资源配置，提高学生学习效率。

2 图论与学习资源的相关理论

2.1 基本图论

有向图：有向图 V,E 是一个二元组，其中V是非空集合，称为顶点集；E是称为边集。直观来说，若图中的每条边都是有方向的，则称为有向图。V V的子集，

有向图中的边是由两个顶点组成的有序对，有序对通常用尖括号表示，如 vi,vj 表示一条有向边，其中vi是边的始点，vj是边的终点。 vi,vj 和 vj,vi 代表两条不同的有向边。几何上用箭头表示有向边的方向：箭头所指向的顶点为终点，另一端成为该边的起点，并称有向边与两端点关联。如下图2.1表示一个有向图：

图论在学习资源优化配置中的应用 毕业论文

图 2.1 有向图示例

二部图：图G (V,E)的结点集可以分划成两个子集X和Y，使得它的每一条边的一个关联结点在X中，另一个关联结点在Y中，这类图称为二部图，又常说G是具有二部分划(X,Y)的图。设G是具有二部分划(X,Y)的图，X n1,Y n2，如果X中每个结点与Y中的全部结点都邻接，则称G为完全二部图，并记之为Kn1,n2。

有向图的连通性：设G=(V,E)是一个简单有向图，如果对G中任何一对结点，至少从其中一结点到另一怎么结点是可达的，则称G是单向连通的；如果任何两个结点之间都是相互可达的则称G是强连通的；如果G的基图是连通的，则称G是弱连通的。如下图2.2中a)、b)和c)分别是强连通图、单向连通图和弱连通图的例子。

a） b） c）

图 2.2 有向连通图示例

树：树是在实际问题中，尤其是计算机科学中广泛被使用的一类图。树具有简单的形式和优良的性质，可以从各个不同角度去描述它。连通且不含圈的图称为树。树中度为1的结点称为叶，度大于1的结点称为枝点或内点。Ki是一个既无叶又无内点的特殊树。若在定义中去掉连通的条件，所定义的图称为林。森林的每个支都是树，如下图2.3是一棵2正则树：

图 2.3 树示例

图的匹配：设M是E(G)的一个子集，如果M中任意两条边在G中均不邻接，则称M是G中的一个匹配。M中的一条边的两个端点叫做在M中是配对的。对任何结点v V若有边uv M，称v是M-饱和的，否则说v不是M一饱和的。如果M是G的一个匹配，且不存在别的匹配M 使M M ，则称M是G

的一个最大（基