科学是使人变得勇敢的最好途径。——布鲁诺
通信网络问题
在通信网络中，分为主机和路由器两部分，我们将主机分为输入端和输出端，则构成的图中有三部分：路由器、输入端、输出端，构成了一个有向图。那么，一个N*N规模的通信网络，应该怎么构成才能达到性能最佳呢（假设N总是2的整数次幂）？
二叉树型
二叉树是最容易想到的构建方法，示意图如下：
其中，圆形表示路由器，I矩形表示输入端，O矩形表示输出端，从左到右分别是主机0~n的输入、输出端。箭头方向表示数据流向，没有箭头表示数据可以双向流动。
二叉树型网络的性能数据如下：
logN即以2为底，N的对数。接下来我们对这些数据进行证明。
直径
定义：一个网络的直径是从任一个输入端到任一个输出端的最远路径。
不难从图中看出，只要是经过最上面的路由器的路径都是最远路径。一个完全二叉树，最远路径长为2（1+logN）。
路由器规模
定义：最多同时有几个IO流流经一个路由器的数量，就是路由器规模。
求一个网络的路由器规模，实际上就是看最多有多少链路经过了同一个路由器，不难看出，在上图中，第二层路由器经过的链路最多，经过了3条输入链路和3条输出链路，继续扩展输入端和输出端的数量，该规模也不会增大，因此规模为3*3.
路由器数量
定义：在一个网络中使用的路由器的数量。
在网络中的路由器数量就是20+21+22+…+2logN，化简后得2N-1.
拥挤程度
在说明这个概念之前，我们先明确一个观点：输入端和输入端是双射关系。然后我们给出拥挤程度的定义。
定义：在任意双射关系中，路径经过同一个路由器的数量上限称作这个网络的拥挤程度。
设输入端i所映射的输出端fi=n-1-i，那么每一个输入端的数据都会经过最顶端的路由器，此时拥挤程度最大，达到N，因为最多也就是N个主机。
二维数组型
二维数组的示意图如下：
输入端从上到下分别对应主机0-3，输出端从左到右对应主机0-3。
二维数组型网络性能如下：
直径
不难看出，最远路径是从I0到O3，长为2N。
路由器规模
在网络上中间的路由器规模最大，有两条输入链路和两条输出链路穿过，因此是2*2，当网络再扩展时，该规模不变。
路由器数量
路由器数量就是N2，没什么好解释的。
拥挤程度
列举任意输入端与输出端的映射，可以发现最多只有两条路径在同一个路由器上交汇。图中用蓝线画出的两条路径在第三行第三列的路由器交汇。所以拥挤程度为2；从另一个角度讲，一行只能有一个路径，而一列也只能用一个，一行一列定位一个路由器，所以当占据该路由器所在行和列的路径不同时，这个路由器的拥挤程度最高，为2.
蝴蝶型
蝴蝶型将二叉树和二维数组结合起来，实现了一定的性能提高。示意图如下：
注意，在这个网络中，分别给行和列进行编号，其中列用二进制进行编号。这样，就可以方便的从看起来复杂的图中抽象出信息：
如果一个路由器的坐标是（b0，…，bl，…，blogN，l），那么这个路由器可以连接（b0，…，¬bl，…，blogN，l+1）和（b0，…，bl，…，blogN，l+1）。其中b0到blogN是列的各个二进制位。例如（1，0，0，0）可以连接到（0，0，0，1）和（1，0，0，1）。
蝴蝶型网络的性能数据如下：
直径
该网络的所有路径长度都相同，都是2+logN。
路由器规模
对于图中1,2列的节点，有两条输入链路和两条输出链路，因此规模为2*2.
路由器数量
行列相乘即可，数量为N（1+logN）。
拥挤程度
该网络的拥挤程度证明较复杂，但可以证明当logN为偶数时，拥挤程度为N^1/2；当logN为奇数时，拥挤程度为（N/2） ^1/2。
benes型
将蝴蝶型稍加改进，即得到benes型网络：
benes型网络的性能如下：
直径
benes型网络的直径与蝴蝶型类似，为1+2logN。
路由器规模
和蝴蝶型网络相同，为2*2.
路由器数量
直接将行列相乘即可，为2NlogN。
拥挤
我们用归纳法证明benes型网络中任意一个路由器的拥挤程度为1，假设P（n）：网络中包含n台主机时命题成立。
基础步骤：证明P（21）。n=2时，网络如下：
不论怎样将输入端映射到输出端，四个路由器的拥挤程度都为1，因此P（2）=T。
归纳步骤：假设P（2i）=T。首先我们要弄清2i的网络如何扩展到2i+1的网络。注意我们的示例图：
图中用蓝色框和黄色框框住的部分就是当主机数量为4时的路由器网络，因此从2i到2i+1就是将2个2i网络拼在一起，再将首尾各加一列路由器。由于我们假设P（2i）成立，因此绿色框中的路由器拥挤程度一定为1，而首尾两列路由器拥挤程度也为1，因此只需考虑第1列和第4列路由器。
为了让第1列拥挤程度为1，某些特定对的输入端不能将数据发送到同一个颜色的框中。例如，如果000输入端和100输入端都将数据送入蓝色框，那么他们一定会送到同一台路由器；同理，对于第4列来说，某些特定对的输出端的数据也不能来自同一个颜色的框，例如000号输出端和100号输出端不能都来自蓝框。有了这些特定数字主机之间的关系，我们可以构造一个图：
假设输入端与输出端之间的映射关系为：f0=1，f1=5，f2=4，f3=7，f4=3，f5=6，f6=0，f7=2，那么该图可以构造成：
如果两个节点相邻，那么他们不能将数据发送到同一个框中；蓝色线说明他们的输入端可能链接同一个路由器，红色线说明他们的输出端可能链接同一个路由器。于是，这个问题演变成一个涂色问题。下面是一种解法：0，2，3，5涂蓝色，即他们将数据送入蓝色框内；1，4，6，7涂黄色，即他们将数据送入黄色框内。通过这种方式，可以发现第1列和第4列的所有路由器都只有一条路径经过，拥挤程度为1.□文章来源：https://www.toymoban.com/news/detail-488415.html
我是霜_哀，在算法之路上努力前行的一位萌新，感谢你的阅读！如果觉得好的话，可以关注一下，我会在将来带来更多更全面的知识讲解！文章来源地址https://www.toymoban.com/news/detail-488415.html
到了这里，关于MIT6.024学习笔记（三）——图论（2）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
