图论与组合数学一、浅谈图论中邻接矩阵的应用通过一个学期以来对图论与组合数学这门课程的学习和理解，从图论的理论到应用，更加加强了对这门学科的认识。

图论与组合数学在我们日常生活中应用的非常广泛，并应用于很多领域，是现在的热门讨论与研究的前沿学科。

通过这个学期老师的授课及讲解，我从中学到了很多，因此在学期末对所学的知识做出总结。

主要介绍一下图论中邻接矩阵的应用。

使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。

图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。

这个问题其实也是一个数学游戏问题，是源于生活，高于生活。

图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。

首先介绍图论中邻接矩阵的一个重要定理:G 是一个图,V(G)为 G 的顶点集, E(G)为 G 的边集。

设G 中有 n 个顶点，v 1,v 2,…,v n ;A=(a ij )n ×n 为 G 的邻接距阵, 其中n j i G E v v G E v v a j i j i ij ,...,2,1,)(0)(1=⎪⎩⎪⎨⎧∉∈=定理 1:设 A (G)为图 G 的邻接距阵,则 G 中从顶点 vi 到顶点 vj,长度为 k 的道路的A k条数为中的 i 行 j 列元素。

证:对 k 用数学归纳法k =1时,显然结论成立;假设 k 时,定理A l .A= A l+1成立,考虑 k +1的情形。

记 A l 的 i 行 j 列元素为l ≥2,因为所以nj lin j l i j l i l ija a a a a a a +++=+...2211)1( (1)而从v i ,v j 到长 k +1的道路无非是从v i 经 k 步到某顶点v l (1≤l ≤n),再从v l 走一步到v j ; 由归纳假设从v l 到v j 长为 k 的道路共计 而从v l 到v j 长为 1的道路为a ij 条,所以长为k+1的v l 经过k 部到v i 再一步到v j 的道路共有∑-+=nl ljk il l ija aa1)()1(条。

锁具装箱问题某厂生产一种弹子锁具,每个锁具的钥匙有 5个槽,每个槽的高度从 {1, 2, 3, 4, 5, 6}6个数 (单位略 )中任取一数由于工艺及其他原因,制造锁具时对 5个槽的高度还有两个限制:至少有 3个不同的数,相邻两槽的高度之差不能为 5,满足以上条件制造出来的所有互不相同的锁具称为一批。

销售部门在一批锁具中随意地取每 60个装一箱出售。

问每一批具有多少个,装多少箱。

分析：锁具装箱这个问题是一个排列组合的数学问题,但在这里我们用图论中的邻接矩阵方法来解决这个问题。

每把锁都有 5个槽,每个槽有 6个高度,至少有三个不同高度的槽。

且相邻槽高差不为 。

我们先求出无相邻高5差为 5的锁具数量,再减去仅有一个、两个槽高的锁具数目。

先计算由 1, 2, 3, 4, 5, 6构成无 1, 6相邻的情况的数目。

为此,构造一个 6节点的图:将 1, 2, 3, 4, 5, 6这 6个数作为 6个节点,当两个数字可以相邻时,这两个节点之间加一条边,每个节点有自己到自己的一条边。

我们得到了锁具各槽之间的关系示意图 (见图 1)。

由图我们可以试着画出这个图的邻接矩阵来：⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=111110111111111111111111111111011111A 邻接矩阵 A 的所有元素之和表示两个槽高无 1, 6相邻的锁具的个数,每个无 1, 6相邻的 5位数与图 1中长度为 4的一条链 1 - 1对应,如 12345, 11111, 22335等。

A 的 k 次方中各元素之和就是长度为 k 的链的个数。

事实上,从这2个具体问题可以看出, A 中第 i 行第 j 列的元素指从 i 开始经过两条边到达 j 的链数,即从 i 开始经过一条边到 k,再从k 经过一条边达到 j, i 和 j 就决定了中间顶点 k 的数目。

于是,利用 Matlab 就很容易得到。

⎪⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=1411651651651651401651941941941941651651941941941941651651941941941941651651941941941941651401651651651651414A将该矩阵中的元素求和可得相邻高差不为 5的锁具数为 6306把。

把。

但这 6306把锁具中包含了仅有一个、两个槽高的锁具,需要从其中减去。

需减去的锁具的个数为6+( C 62-1)(25-2)=426其中,第一个 6仅有 1个槽高的锁具; C 62为 1, 2, 3, 4, 5, 6这 6个数中取两个的取法,但扣除 1, 6这一种取法。

最后得到一批锁具的个数为 6306 - 426 =5880,总共装98箱。

这样,就用图论的知识成功地解决了一批锁具的数量问题,这个方法比用别的方法简单,且容易推广。

问题求解反思：使用邻接矩阵求解有关实际问题符合数学中数形结合的思想，对于更好地理解问题，思考问题从而求解问题具有现实意义。

图论知识的应用是相当广泛的，它是数学的重要分支，使今年来较为活跃的数学分支。

这个问题其实也是一个数学游戏问题，是源于生活，高于生活。

图论作为组合数学的一分支，与其他数学分支，如矩阵论，概率论，拓扑学数值分析都有着重要的联系。

课本中也列举几种图论的矩阵表示法，如关联矩阵，邻接矩阵。

从矩阵的角度分析了图的顶点度的问题等相关知识。

对于这样的一个问题我们可以类似的联想到还有一个比较有特色的问题就是商人过河问题：三名商人各带一个随从乘船渡河,现有一只小船只能容纳两个人,由他们自己划行,若在河的任一岸的随从人数多于商人,他们就可能抢劫财物。

但如何乘船渡河由商人决定,试给出一个商人安全渡河的方案。

同样我们也可以用矩阵的方法加以解决。

4、求最小生成树的邻接矩阵法求最小生成树的邻接矩阵法如下：设图G为任意的简单图可以是完全的,也可以是不完全的. 图G有个 n结点,且其边的集合为{（v1,v2），（v1,v3），…，（v n-1,v n）}。

在该算法执行过程中我们使用一个桶存放最小生成树的边一个桶存放最小生成树的结点一个计数器记录桶中边的数目开始时桶桶计数器都是空的。

算法的步骤：1)写出图G的邻接矩阵M,对于无向简单图G矩阵M以对角线为轴对称,我们只取其对角线以上部份的三角形各元素.在所有矩阵元素不为0的边中,选最小权边（v i,v j）放入E桶中，该边的两端点v i,v j放入V桶，并记工=1，若有两个（或两个以上）最小权边，其权值相等，任选其一。

2)矩阵M中，将（v i,v j）边对应元素改为0，对v i,v j结点所对应的行与列上的矩阵元素做“乘2的模4运算”。

3)检查若有不为0的元素，则转第四步。

否则算法结束。

此时若I=n-1.则E桶中各边构成最小生成树。

I《n-1，则没有最小生成树。

4)将邻接矩阵M中,值为2的各元素对应边作为候选边.在候选边中找出最小权边（v i,v j），若有两个或两个以上最小权边任取其一。

将该边放入E桶，并将其在V桶外的端点v i+1放入V桶。

同时：I=I+1。

5)将（v i,v j）边对应元素改为0，将新入V桶的结点v i+1对应的M行列中做“乘2的模4运算”。

6)转第三步。

在关于算法的叙述中应说明两点：第一、算法中规定即乘2的模4运算它的含义是对一个变量乘以2 如果乘积等于4，则改该变量的值为0。

第二、因为在步骤3检查矩阵，如有不为0的元素，才转4，所以在第4步中邻接矩阵中必有值为2的元素.这是因为当一条边进人E桶，它的两端点进人V桶，与该两端点邻接而尚未进入E桶的各边对应的矩阵元素值原来为1经乘2后，其值必为2。

另一方面某一条边成为候选边，则它的矩阵元素值为2，如在下一步 它未被选中其值不变，如被选中它的值才会 因为乘2的模4运算而变为0.所以 只要最小生成树最后未被求出在步骤4， 矩阵中必有值为2的元素。

该算法求解反思：1、本算法在此虽然为涉及具体题目，但是这样的算法在实际问题的求解中是非常奏效的。

通俗易懂，便于检验。

这样对于运用计算机程序加以运算提供可能。

2、该算法有其简便之处，每次选最小权边2时，仅在部份元素中选取，就是说只矩阵元素为2时 对应边才是候选边。

二、一类基于二部图的(,)3g f -覆盖图设G 是一个图，分别用V （G ）和E （G ）表示图G 的顶点集合边集，用()G d x 表示顶点x 在G 中的次数。

设g ，f 分别是定义在V （G ）上的两个整数值函数，若对每个()x V G ∈有()()g x f x ≤，则图G 的一个（g ，f ）-因子是G 的一个支撑子图F ，使得对每个()x V G ∈有()()()F g x d x f x ≤≤。

若对任意()x V G ∈有()()()g x f x g f ≤<，以下简记为()g f g f ≤<。

设任意,()S T V G ⊆，[]G S 表示G 的由S 导出的子图，记[()\]G S G V G S -=。

若1()E E G ⊆，用1G E -表示从G 中去掉1E 中的全部边所得到的图。

且有为方便，对任意函数f ，记()()x Sf S f x ∈=∑，并且令()0f φ=。

记Folkman, Fulkers on 曾得到下面的结果。

引理 设 G = (X, Y)是一个二部图, g 和 f 分别是定义在 V (G)上的两个整数值函数,使对每个 x ∈V (G)有 g ( x) ≤f ( x) ,则 G 有一个 ( g, f) 因子当且仅当对任意 S X ⊆和T Y ⊆有刘桂真教授引进的（g ，f ）覆盖图的概念，即过图G 的任意一条边都有G 的一个（g ，f ）因子，则称图G 是一个（g ，f ）覆盖图。

并且给出了一个图是 ( g, f) 2 覆盖图的充要条件,又给出了一个图有一个 ( g, f) 因子含有一条指定边的充要条件。

黄光鑫推广了这一概念如下,如果过图 G 的任意 k 条边都有 G 的一个 ( g, f) 因子,则称 G 是一个 ( g, f) 2 k2 覆盖图 ( k = 2, 3) ,并且分别得到了当 g < f 时一个图是 ( g, f) 2 22 覆盖图和 ( g, f) 2 32 覆盖图的充分必要条件。

若 P x ∈V (G)有 f ( x) = g ( x) ,则称一个 ( g, f) 2 32 覆盖图 G 是一个 f232 覆盖图。

当 g ≤f 时,寻找图 G 是一个 ( g, f) 2 32 覆盖图的充要条件是一个相当困难的问题。