数学图论模型

目录目录 (1)第8章图论模型 (1)8.1图的基本知识 (2)8.1.1图的相关定义 (2)8.1.2图的顶点的度 (3)8.1.3子图及运算 (4)8.1.4 图的连通性 (5)8.1.5一些特殊图 (7)8.2图的矩阵表示 (7)8.2.1邻接矩阵 (7)8.2.2 关联矩阵 (8)8.3图的方法建模 (9)8.3.1 图的最小生成树问题及算法 (10)1．树及最小生成树 (10)2．克鲁斯卡尔算法 (11)3．普利姆算法 (13)8.3.2图的最短路问题及算法 (15)1．迪克斯特拉算法 (15)8.3.3图的匹配及应用 (20)1. 图的匹配 (20)2．指派问题： (23)3．最优指派 (27)8.3.4 图的覆盖及应用 (33)1. 逻辑算法 (34)2．启发式算法： (35)3．利用关联矩阵求极小覆盖： (37)8.3.5图的遍历问题 (38)1．边的遍历-中国邮差问题 (38)2．点的遍历-旅行商问题 (41)8.3.6 竞赛图问题 (48)1．竞赛图的定义 (48)2．循环比赛排名 (50)8.4 实战篇 (51)第8章图论模型图论（Graph Theory）18世纪起源于欧洲。

瑞士著名数学家欧拉(Euler）于1736 年发表的第一篇图论论文—“哥尼斯堡七桥问题”，不但解决了曾经困扰了人们多年的难题，同时它宣告了图论这门学科的诞生。

在普鲁士的小镇哥尼斯堡，一条河穿城而过，河中央有两个小岛，小岛之间及岛与河岸共有七座桥连接。

能否从四块陆地中的任何一处出发，恰好通过每座桥一次再回到起点，这就是著名的“哥尼斯堡七桥问题”。

人们曾经做过很多尝试，但是都没有获得成功。

为了解决这个问题，欧拉将问题进行几何抽象：将陆地分别用“点”代替，将桥用连接这些点的“线”来代替，得到一个包含四个“点”，七条“线”的“图”，将问题转化为“如何从一点出发一笔画出这个图，最后回到起点”的问题。

因为每次经过一个点必须消耗掉两条与该点相关联的边（从一边进入，另一条边离开），所以和每个点相关联的边的数量应该是一个偶数，此问题显然是无解的。

各种图论模型及其解答摘要：本文用另一种思路重新组织《图论及其应用》相关知识。

首先，用通俗化语言阐述了如何对事物间联系的问题进行图论建模；接着从现实例子出发，给出各种典型图论模型，每种图论模型对应于图论一个重要内容；再者，介绍相关知识对上述提到的图论模型涉及的问题进行解答；最后，补充一些图论其他知识，包括图论分支、易混概念。

符号约定：Q(Question)表示对问题描述，M(Modeling)表示数学建模过程，A(Answer)表示原问题转化为何种图论问题。

一、引言图论是研究点、线间关系的一门学科，属于应用数学的一部分。

现实生活中，凡是涉及到事物间的关系，都可以抽象为图论模型。

点表示事物，连线表示事物间的联系。

整个求解过程如下：原问题——>图论建模——>运用图论相关理论求解——>转化为原问题的解整个过程关键在于图论建模，所谓图论建模，就是明确点表示什么，连线表示什么，原问题转化为图论中的什么问题。

存在以下两种情况：①若事物间联系是可逆的(比如双行道，朋友)，则抽象成无向图②若事物间联系是不可逆的(比如单行道，状态转化不可逆)，则抽象成有向图如果需要进一步刻画事物间的联系（比如城市间的距离），就给连线赋一个权值，从而抽象成赋值图。

综上，根据实际问题，可建模成下列图论模型的一种：无向赋权图、有向赋权图、无向非赋权图、有向非赋权图。

例1.宴会定理：任何一宴会中，一定存在两个人有相同的数量朋友M：点表示人，连线表示当且仅当该两个人是朋友A：问题转化为任何一个图一定存在两个顶点的度相等二、图论模型接下来介绍若干典型的图论模型，每种模型几乎对应于图论的一个重要内容，这些内容将在第三章进行讨论，也就给出了这些模型的解答思路。

2.1 偶图模型凡涉及两类事物间的联系（即只考虑两类事物间的联系，而不考虑同类事物间的联系），均可抽象成偶图模型。

作图时，将两类事物分成两行或者两列。

这类模型通常被包含在后续的模型中，但因许多现实问题可抽象成该模型，所以单列出来讨论。

第九章 图论模型现实世界的许多实际问题都可以用图形来解释或说明.例如通讯网络就可以用图的形式直观的表现出来：点可以表示通讯中心，而边表示通讯线路.图论模型是应用十分广泛的数学模型,它已经在物理、化学、控制论、信息论、科学管理和计算机等领域.由于它具有图形直观，方法简单容易掌握的特点，因此在实际、生活和数学建模中，有许多问题可以运用图论的理论和方法解决.§9.1图论起源图论起源于18世纪欧拉对哥尼斯堡七桥问题的研究.哥尼斯堡是18世纪东普鲁士的一个城市，城中有一条普雷格尔河，河中有两个岛，河上有七座桥，如图1所示.图1 当时那里的居民热终于思考这样一个问题，一个人能否经过七座桥且每座桥只走过一次，最后回到出发点.能否用数学的方法解决这个问题一贯成为当时居民的一个悬而未决的问题.1736年欧拉创造性的将陆地用点表示，桥用边表示，从而将这个问题转化为如图2所示的一笔画问题，即能否从某个点开始一笔画出这个图形，最后回到原点而不重复.欧拉证明了这个问题是不可能的.图2欧拉解决七桥问题时，其方法超出了常用的数学方法，充分发挥自己的想象力，用了全新的思想方法，从而使得问题得到完美解决.由于这一项开创性的工作，产生了“图论”这门崭新学科，欧拉被认为是图论的创始人.ABCDABCD1e 2e 5e 6e 7e 4e 3e§9.2基本概念定义1 图G 由两个点集合V 以及边集合E 组成，记为(),G V E =，其中： (1)V 是顶点构成的集合；(2)E 是连接某些顶点对构成的边组成的集合.例1 {}1234,,,V v v v v =，{}12232434,,,E e e e e =，画出图(),G V E =.图3注：图分为无向图和有向图.定义2 若图(),G V E =的边均没有方向，这样的图成为无向图.例如图2，图3为无向图.无向图的边称为无向边，无向边是由两个顶点构成的无序对，无序对通常用圆括号表示. 例2 (),i j v v 表示一条无向边，(),i j v v 与(),j i v v 是同一条边.定义3 若图(),G V E =的边均有方向，这样的图称为有向图.有向图的边称为有向边，有向边是由两个顶点构成的有序对，有序对通常用尖括号表示.有向边又称为弧. 例3,i j v v 表示一条有向边，,i j v v与,j i v v 是两条不同的有向边.定义4 一条边的端点称为与这条边关联，反之，一条边称为与它的端点关联.与同一条边关联的两个端点是邻接的.如果两边有一个公共端点，则这两条边是邻接的。

目录五、图论模型1.迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-Ford）算法2.弗洛伊德（Floyd）算法六、分类模型1.逻辑回归2.Fisher线性判别分析五、图论模型图论模型主要解决最短路径问题，根据图的不同，对应采用迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-Ford）算法、弗洛伊德算法（Floyd）。

Matlab代码：% Matlab中的图节点要从1开始编号s = [9 9 1 1 2 2 2 7 7 6 6 5 5 4];t = [1 7 7 2 8 3 5 8 6 8 5 3 4 3];w = [4 8 3 8 2 7 4 1 6 6 2 14 10 9];G =graph(s,t,w);plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) set ( gca, 'XTick', [], 'YTick', [] );%% Matlab作无向图% （1）无权重（每条边的权重默认为1）% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并生成一个图% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组% 注意：编号从1开始连续编号s1 = [1,2,3,4];t1 = [2,3,1,1];G1 = graph(s1, t1);plot(G1)% 注意字符串元胞数组是用大括号包起来s2 = {'学校','电影院','网吧','酒店'};t2 = {'电影院','酒店','酒店','KTV'};G2 = graph(s2, t2);% 设置线的宽度plot(G2, 'line width', 2) % 画图后不显示坐标set( gca, 'XTick', [], 'YTick', [] ); % （2）有权重% 函数graph(s,t,w)：可在 s 和 t 中的对应节点之间以w的权重创建边，并生成一个图s = [1,2,3,4];t = [2,3,1,1];w = [3,8,9,2];G = graph(s, t, w); plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) set( gca, 'XTick', [], 'YTick', [] ); %% Matlab作有向图% 无权图 digraph(s,t)s = [1,2,3,4, 1];t = [2,3,1,1,4];G = digraph(s, t);plot(G)set( gca, 'XTick', [], 'YTi ck', [] ); % 有权图 digraph(s,t,w)s = [1,2,3,4];t = [2,3,1,1];w = [3,8, 9,2];G = digraph(s, t, w);plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2) set( gca, 'XTick', [], 'YTick', [] );1.迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-Ford）算法迪杰斯特拉算法是基于贪婪算法的思想，从起点出发逐步找到通向终点的最短距离。

图论模型简介一、图及其矩阵表示1、起源：哥尼斯堡七桥问题：欧拉为了解决这个问题，建立数学模型：陆地——点，桥——边，得到一个有四个“点”，七条“边”的“图”。

问题转化为能否从任一点出发一笔画出七条边再回到起点。

欧拉考察了一般一笔画的结构特点，给出了一笔画判定法则：图是连通的，且每个顶点都与偶数条边相关联（这种图称为欧拉图）。

由此可以得出结论：七桥问题无解。

2、基本概念：图（graph）：由顶点和边（又称线，边的两端必须是顶点）组成的一个结构。

邻接：一条边的两个端点称是邻接的；关联：边与其两端的顶点称是关联的。

无向图（graph）：边无方向的图；有向图（digraph）：边有方向的图。

路(path)：由相邻边组成的序列，其中中间顶点互不相同。

圈(cycle)：首、尾顶点相同的路，即闭路。

连通图（connected graph）：图中任意两顶点间都存在路的图。

树（tree）：无圈连通图完全图（complete graph）：任意两个顶点之间都有边相连的无向图，记为K n。

竞赛图（tournament）：由完全图给每条边定向而得到的有向图。

二部图（bipartite graph）：图的顶点分成两部分，只有不同部分顶点之间才有边相连。

图G的子图H（subgraph）：H是一个图，H的顶点（边）是图G的顶点（边）。

网络（Network）：边上赋了权的有向图。

3、图的矩阵表示无向图 有向图01000101100101101100010⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦ ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡011101000001001000001104、著名的图论问题例1 最短路问题（shortest path problem）出租车司机要从城市甲地到乙地，在纵横交错的路中如何选择一条最短的路线？例2 最小生成树问题（minimum-weight spanning tree problem）为了给小山村的居民送电，每户立了一根电杆，怎样连接可使连线最短？例3 中国邮递员问题（chinese postman problem）一名邮递员负责投递某个街区的邮件。

十大经典数学模型十大经典数学模型是指在数学领域中具有重要意义和广泛应用的数学模型。

这些模型涵盖了不同的数学分支和应用领域，包括统计学、微积分、线性代数等。

下面将介绍十大经典数学模型。

1. 线性回归模型线性回归模型用于描述两个变量之间的线性关系。

它通过最小化观测值与模型预测值之间的差异来拟合一条直线，并用该直线来预测未知的观测值。

线性回归模型在统计学和经济学等领域有广泛应用。

2. 概率模型概率模型用于描述随机事件发生的可能性。

它通过定义事件的概率分布来描述事件之间的关系，包括离散型和连续型概率分布。

概率模型在统计学、金融学、生物学等领域中被广泛应用。

3. 微分方程模型微分方程模型用于描述物理系统、生物系统和工程系统中的变化过程。

它通过描述系统中各个变量之间的关系来解释系统的动态行为。

微分方程模型在物理学、生物学、经济学等领域中具有重要应用。

4. 矩阵模型矩阵模型用于表示线性关系和变换。

它通过矩阵和向量的乘法来描述线性变换，并用于解决线性方程组和特征值问题。

矩阵模型在线性代数、网络分析、图像处理等领域中广泛应用。

5. 图论模型图论模型用于描述物体之间的关系和连接方式。

它通过节点和边的组合来表示图形，并用于解决最短路径、网络流和图着色等问题。

图论模型在计算机科学、电信网络等领域中有广泛应用。

6. 最优化模型最优化模型用于寻找最佳解决方案。

它通过定义目标函数和约束条件来描述问题，并通过优化算法来找到使目标函数最优的变量取值。

最优化模型在运筹学、经济学、工程优化等领域中被广泛应用。

7. 离散事件模型离散事件模型用于描述在离散时间点上发生的事件和状态变化。

它通过定义事件的发生规则和状态转移规则来模拟系统的动态行为。

离散事件模型在排队论、供应链管理等领域中有重要应用。

8. 数理统计模型数理统计模型用于从样本数据中推断总体特征和进行决策。

它通过概率分布和统计推断方法来描述数据的分布和抽样误差，包括参数估计和假设检验等方法。