最后更新: 2025-11-21 15:07 查看: 33 次纠错评论(0) 课件开VIP

图论的作用

为了理解图轮的作用，将通过几个引例进行说明。

## 运输网络
图和有向图出现在很多运输问题中。例如，考虑快递公司运输货物。如下图所示，我们可以把城市/场所类抽象为“**点**”，当从场所 $x$ 到场所 $y$ 可以移送货物时，画一**有向线**（或曲线）表示。

![图片](/uploads/2025-11/c635ee.jpg){WIDTH=300PX}
 
当所有连线都是双向时，我们可以用下面的方法更简单地把它们表示出来：在可以直接连接起来的两个场所之间画一条单一**无向线**，而不用对每对场所画出两个箭头

![图片](/uploads/2025-11/c29f2f.jpg){WIDTH=300PX}
 
 
 运输网络有诸多有趣问题，包括如何设计高效的交通网络，如何确保它们不易破坏，等等．
 
## 通信网络

图也用于通信的研究中．考虑一个委员会、一个法人团体或任意类似的需要联络的组织．如下图所示，把这样的组织中的每一个成员表示成一个点，并且如果成员 $x$能够与成员 $y$ 直接联络，那么从成员 $x$ 到成员 $y$ 画一条有箭头的线。例如，在下图的警察局中，长官能够直接与调度员联络，而这位调度员又能通过任意一位副官找到长官 ．

![图片](/uploads/2025-11/474926.jpg){WIDTH=500PX}

关于这样的＂通信网络＂，所问及的典型问题类似于运输网络的问题：如何设计高效网络，破坏通信的容易程度等．现代通信网络理论通常涉及交互通信网络和计算装备网络，而且它所生成的图是巨大的．

## 物理网络
图通常对应于物理系统．例如，可以把电网想象为一个图，点表示各电气部件，当且仅当存在一条连接两个点的电线时，用一条无向直线将它们相连．类似地，在电话网络中，我们可以把切换中心和各个电话想象成为点，且两个点有直线连接，如果它们之间存在直通电话线。 另外，原油和天然气管道也可以以这种方式翻译成图。我们通常寻找满足某种相互连接需求的最高效网络或成本最低的网络设计，或寻找最不易受到破坏的网络．
 
## 网络冗余/可靠性
如果运输、通信、电力或计算机网络被模型化成图，那么这一网络的组成可靠性就需要得到足够的保证。好的网络设计应该拥有冗余，这样，某些组成部分的故障不至于导致整个网络的故障。

例如，假设我们有如下图所示由 6 台计算机组成的网络，且它们之间的直接连接表示成图中的直线。 如果$AD$点网络通讯终端，那么信号可以$ACD$继续联通。

![图片](/uploads/2025-11/546258.jpg){width=300px}

##   因特网上的信息搜索
由于因特网上的网站和网页数量的急剧增加，出现了诸如 Google 等的搜索引擎．这样的系统构建需要不断更新网页数据库．这种更新是通过周期性遍历网络的超文本结构的机器人实现的．假设把每个网站表示成一个点，并在其中从一个网站到另一个网站之间画箭头线，如果机器人可以在访问前一个网站之后访问后一个网站．应该以什么样的顺序访问各网站，使得最小化数据库中的网页过时的时间因素？答案部分依赖于给定网页的更新概率的评估．当我们查看用户查询的＂最相关＂网站或带足够高的＂相关得分＂的网站集合时，还要涉及因特网搜索中的图论的其他应用，这是图论中的匹配问题．

##  物种间的竞争
图也应用于生态系统的研究中．考虑构成生态系统的若干物种．把物种（或物种群）表示成点，如下图所示，并在物种 $x$ 和 $y$ 之间画一条无向线当且仅当 $x$ 和 $y$ 相互竞争．结果图称为**竞争图**（competition graph，或生态位重叠图）．关于竞争图能提出的问题包括这些竞争图的结构性质的问题（例如它们如何连接，它们的连通部分是什么），以及这些连线的密度问题（出现的连线数量与可能的连线数量的比率）．

![图片](/uploads/2025-11/b4c254.jpg){width=500px}
 
 
 
 ##  循环赛
 作为图的另一个应用，考虑网球循环赛 $\ominus$ ，其中每一名球手必须与其余每一位球手正好比赛一次，且不允许平局。可以把球手表示成点并当＂$x$ 打败 $y$＂时从 $x$ 到 $y$画一条有箭头的线，如下图所示。
 
 
  ![图片](/uploads/2025-11/280216.jpg){width=300px}
  
  
 
 类似的循环赛大量出现于社会学、生物学和环境科学中．心理学家在一个选项集合上进行成对比较优先选择实验，对于这一选项集合中的每一对选项，要求对象说明他对此的喜好。如果我们把这些选项对应于球手，而把＂喜爱＂对应于＂打败＂，那么这就定义一个循环赛．生物学中也发生循环赛现象．研究表明，农家的每一对小鸡中的一只＂统治＂另外一只。这种小鸡间的啄食顺序同样定义一个循环赛 （这同样也适合其他动物）。在循环赛的研究中，一个基础问题是确定＂赢者＂并排列＂球手＂。图论也有助于解决这一问题．
 
## 人际关系图
现代应用程序都有人际关系图，如果$B$是$A$的好朋友，而$C$是$B$的好朋友，那么$A$与$C$就变成了间接的朋友关系，通过收集每个人的资料，就可以建立人际关系图。

![图片](/uploads/2025-11/fac3d9.jpg){width=400px}
 
总之，图的关系存在生活中的方方面面。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：哥尼斯堡（Könisberg）七桥问题

下一篇：无向图与有向图

本文对您是否有用？有用 (0) 无用 (0)