5. Rating of network bandwidth between a pair of points
Flow of P some vertex s called the source to some sink vertex t is called the network is a set of non-negative integers xij (flow of arcs) if these numbers satisfy the following limitations
-Pst,
if j=s (source)
∑ xij - ∑ xjr= 0, if j≠s,t
Pst, if j=t (stock)
A section of the network is not redundant set of arcs (edges), in which the withdrawal from the network connection is broken e.
The cross section for separating the source and stock having a minimum capacity is called a minimal section.
Minimum cross-section, separating the source and drain, is analogous to the "bottleneck" in any network, and, consequently, the magnitude of the maximum flow cannot exceed its capacity. The maximum flow is always equal to the minimum capacity among all sections of separating source and stock.
The network has a source and a drain, called bipolar. Network in which each pair of vertices can be regarded as the source and drain, called a multi-polar. If your network has multiple sources and multiple sinks and flow can come from any source in any stock, then this is called a single-product flow. If a network with multiple sources and sinks of the flow should go from several sources identified in the wastewater are fixed, then this flow is called a multiproduct.
In multiproduct network flow is fixed in the stock’s, and multipolar, each pair of vertices can be regarded as the source and stock.
Determine the maximum bandwidth of each node, and in particular for solving transport problems, such as information communication networks.
Necessary to determine the network bandwidth between all nodes in the network. Since we have 10 nodes, the number of combinations will be determined as 2 to the power 10, which corresponds to 1024 combinations. Since the operation of manual processing will be quite long, for this purpose was written program that allows you to solve this problem.
The initial data for solutions will be the weight matrix.
The algorithm is formed as follows.
In the first step, we assign the source of the mark 0 and mark of stock is 1. We believe the value of cross counter to zero.
In the second step we form a binary representation of the counter top and sort according to markings. Determine the bandwidth of the received version of the cross section for the distribution of peaks as the sum of capacities of arcs or edges that make up the section under consideration.
Increase the value of the counter by one at step number three. If the counter has reached level two in the number of nodes minus 1, then go to step four, if not, then go back to step number №2.
In step 4 of the obtained values we choose the smallest streams, and write in a matrix of the least flow.
Table 5.1 − The matrix of maximum streams
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
1 |
0 |
88 |
97 |
29 |
224 |
192 |
97 |
185 |
66 |
97 |
2 |
88 |
0 |
88 |
29 |
88 |
88 |
88 |
88 |
66 |
88 |
3 |
97 |
88 |
0 |
29 |
97 |
97 |
97 |
97 |
66 |
97 |
4 |
29 |
29 |
29 |
0 |
29 |
29 |
29 |
29 |
29 |
29 |
5 |
224 |
88 |
97 |
29 |
0 |
192 |
97 |
185 |
66 |
97 |
6 |
192 |
88 |
97 |
29 |
192 |
0 |
97 |
185 |
66 |
97 |
7 |
97 |
88 |
97 |
29 |
97 |
97 |
0 |
97 |
66 |
97 |
8 |
185 |
88 |
97 |
29 |
185 |
185 |
97 |
0 |
66 |
97 |
9 |
66 |
66 |
66 |
29 |
66 |
66 |
66 |
66 |
0 |
66 |
10 |
97 |
88 |
97 |
29 |
97 |
97 |
97 |
97 |
66 |
0 |
The minimum bandwidth of the network is equal to 41.