Loading...
墨滴

进击的土豆同学

2021/08/23  阅读:39  主题:默认主题

网络模型1-网络模型相关概念

网络模型相关概念

0 引言

因为跨考824,因此最近在疯狂啃运筹学的书,在这篇博客中,我会介绍从几本书中学习到的网络模型的相关知识点,并做一个小结,帮助自己和读者更好地学习网络模型。

1 网络模型的定义和概念

1.1 网络模型的定义

一个网络是由节点(node) 集合以及连接节点的 [arc,或(branch)]集合组成。用符号(N, A)表示,其中N表示节点的集合,A表示弧的集合。 在这里插入图片描述

图1.(N,A)网络例子

1.2 网络模型相关概念

先来了解一下无向图和有向图:

无向图:由点和边组成的图,记为 ,其中 个点的集合,简称点集; 条边的集合,简称边集.并且 是一个无序二元组,记为 .

有向图:由点和弧组成的图,记为 ,其中 个点的集合, 条弧的集合,并且 是一个有序二元组,记为 ,并称 是以 为始点, 为终点的弧.

流(flow):概念比较好理解,比如管道中的流量,路上的车辆的流量。网络的流是由网络中弧上的容量限定的,弧上的最大容量可以是有限的也可以是无限的。

再来看看网络:

        如果一条弧上其中一个防线的流量允许是正数,相反方向的流量都为0,那么称这条弧是有向的(directed或oriented)。如果网络中所有弧都是有向弧,那么这个网络称作有向网络(directed network)

        路(path):用一系列不考虑方向的弧将两个节点连接起来,其中经过其他一些节点,这一系列的弧就称作一条路(path)。

        圈(cycle)或环(loop):如果一条路从某个节点出发经过其他一些节点又回到自身,那么这条路称作圈(cycle)或环(loop)。例如上图中的弧(2,3),(3,4),(4,2),组成了一个圈。

        连通网络(connected network):如果一个网络中任意两个不同节点都至少有一条路连接,那么这个网络称作连通网络(connected network)。如上图..

        树(tree):网络中部分节点组成的一个无圈连通网络称作树(tree),如果一棵树上包含了网络中所有节点,那么这棵树称作生成树(spanning tree)。如下图给出了图1网络中的一棵生成树。

图2.生成树
图2.生成树
1.3 柯尼斯堡七桥问题

        普鲁士的柯尼斯堡坐落在Pergrl河两岸,整个城市分为4个区域(A, B, C, D),四个区域由7座桥相连。如下图所示....。有居民提出这样的问题:是否可以找到一条到达每个区域并且通过每座桥恰好一次的环游,每个区域上的到达次数不受限制在这里插入图片描述

        19世纪,有学者将这个问题转化为了网络,其中每个区域看做一个节点,每座桥看做一条弧。如下图。

在这里插入图片描述
在这里插入图片描述

        基于网络的方法可以证明所设想的环游是不存在的。原因很简单,图中有4个节点,每个节点都有奇数条弧相连。因为要求每座桥只能经过一次,即图上每条边只能通过一次,但是对于一个节点而言,由于弧的数目是奇数,所以不能保证进入和出去这个节点的次数相等。 柯尼斯堡七桥问题的更一般结论是:一个网络中只有当每个节点都有偶数条边相连,或者恰好只有两个节点有奇数条边相连,才存在经过每条边恰好一次的通路,否则就不可能存在。

1.4 网络优化算法

        现实中很多问题都可以转化为网络进行解决或优化,其中几种常用的优化算法为:最小生成树算法、最短路径算法、最大流算法,下面会详细介绍一下这几个算法。

进击的土豆同学

2021/08/23  阅读:39  主题:默认主题

作者介绍

进击的土豆同学