图论模型

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

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

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

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

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

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

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

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

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

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

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

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

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

图论模型图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。

许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。

图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。

1936年，匈牙利数学家柯尼希（D. Kӧnig ）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。

近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。

9.1 图的基础理论9.1.1 图的基本概念所谓图，概括地讲就是由一些点和这些点之间的连线组成的。

定义为(,)G V E =，V 是顶点的非空有限集合，称为顶点集。

E 是边的集合，称为边集。

边一般用(,)i j v v 表示，其中,i j v v 属于顶点集V 。

以下用V 表示图(,)G V E =中顶点的个数，E 表示边的条数。

如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为(,)G V E =，123{,,}V v v v =，1213{(,),(,)}E v v v v =.23v 45v 34(a)(c)图9.1 图的示意图1.无向图和有向图如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。

如图9.1 (a)和(b)都是无向图。

连接两顶点i v 和j v 的无向边记为(,)i j v v 或(,)j i v v 。

如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。

连接两顶点i v 和j v 的弧记为,i j v v 〈〉，其中i v 称为起点，j v 称为终点。

显然此时弧,i j v v 〈〉与弧,j i v v 〈〉是不同的两条有向边。

图论模型图是为了解决一些具体问题而产生的模型，这可以从它的发源“哥尼斯堡的七桥问题”看到。

一个图表示了某些对象集合元素之间的关系，所以它被广泛用来作为许多与对象的离散安排有关问题的模型。

它已在物理、化学、经济、管理、信息、控制等所有离散系统中应用。

本章仅介绍几类图论模型。

9.1 连线问题一、问题的背景与提出现实社会中，我们可以看到，公路、铁路、通信、输电线路等的建设中，都涉及到“如何设计建造一个既能畅通无阻又造价小的网络”问题，即连线问题。

二、模型假设与符号说明假设要建造一个连接若干城镇的通信网络，第i个城镇与第j个城镇之间直通线路的造价为cij。

三、模型的建立与求解把每个城镇看作是一个点v；两个城镇直通线路看作边e；城镇vi与城镇vj之间直通线路的造价看作边vivj的权w(vivj)=cij，这样我们得到了一个赋权图G。

设计一个总造价最小的通信网络，就转化为：在赋权图G，找出具有最小权的连通生成子图，即寻找赋权图的最小权的生成树（最优数）。

1956年Kruskal给出了一种求最优树的算法，称为避圈法，算法如下： 10 选择边e1，使得w(e1)尽可能小；20 若已选定边e1, e2, …, ei, 则从边集E\{e1, e2, …, ei}中选取ei+1，使（ⅰ）G[{e1, e2, …, ei+1}]为无圈图；（ⅱ）w(ei+1)是满足（ⅰ）的尽可能小的权， 30 当20不能继续执行时停止。

对于p个点ε条的赋权图G，该算法就是先将赋权图的边按权的递增顺序排列：a1, a2, …, aε设e1=a1, e2=a2, 检查a3，如果a3与e1, e2不构成圈，则令e3=a3，否则放弃a3，检查a4，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）一名邮递员负责投递某个街区的邮件。