Mathematical modeling -- graph and network models and methods (II)

Catalog

Basic concepts

Find the minimum spanning tree

The coloring problem

Maximum flow problem

Minimum cost flow problem

Travel agent problem

---

Basic concepts

Connected acyclic graphs are called Trees . for example ：

  Make trees ： If the figure G The generated subgraph H It's a tree. , said H by G Spanning tree or spanning tree . The spanning tree with the smallest sum of edge weights is the smallest spanning tree . The spanning tree of a connected graph must exist .

The algorithms for constructing the minimum spanning tree of connected graphs are Kruskal Algorithm and Prim Algorithm .

Find the minimum spanning tree

Kruskal、Prim Algorithm

for example , Find the following minimum spanning tree ：

clc,clear,close all,a=zeros(9);
a(1,[2:9])=[2 1 3 4 4 2 5 4];
a(2,[3,9])=[4,1];a(3,4)=1;a(4,5)=1;
a(5,9)=5;a(6,7)=2;a(7,8)=3;a(8,9)=5;
s=cellstr(strcat('v',int2str([0:8]')));
G=graph(a,s,'upper');p=plot(G,"EdgeLabel",G.Edges.Weight);
T=minspantree(G,'Method','sparse');%sparse by Kruskal Algorithm ,dense by Prim Algorithm 
L=sum(T.Edges.Weight);
highlight(p,T);

Mathematical programming model

  constraint condition ：

  Solve the above example ：

clc,clear,close all,n=9;
nod = cellstr(strcat('v',int2str([0:n-1]')));
G = graph;G = addnode(G,nod);% Add a new node to the diagram 
ed = {'v0','v1',2;'v0','v2',1;'v0','v3',3;'v0','v4',4;
      'v0','v5',4;'v0','v6',2;'v0','v7',5;'v0','v8',4;
      'v1','v2',4;'v1','v8',1;'v2','v3',1;'v3','v4',1;
      'v4','v5',5;'v5','v6',2;'v6','v7',4;'v7','v8',5};
G = addedge(G,ed(:,1),ed(:,2),cell2mat(ed(:,3)));
w = full(adjacency(G,'weighted'));
w(w==0) = 1000000% Represents a positive real number that is sufficiently large 
prob = optimproblem;
x = optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1);
u = optimvar('u',n,'LowerBound',0);
prob.Objective = sum(sum(w.*x));
prob.Constraints.con1 = [sum(x(:,[2:end]))'==1;u(1)==0];
con2 = [1<=sum(x(1,:));1<=u(2:end);u(2:end)<=n-1];
for i = 1:n
    for j = 2:n
        con2 = [con2;u(i)-u(j)+n*x(i,j)<=n-1];
    end
end
prob.Constraints.con2 = con2;
[s,f,flag,out] = solve(prob);
[i,j]=find(s.x);
ind = [(i-1)';(j-1)']

The coloring problem

Vertex shading problem ： Known figures G=(V,E), Pair graph G When shading all vertices of , The color of two adjacent vertices should be different , At least several colors are needed .

Edge coloring problem ： Pair graph G When shading all edges of , The color of two adjacent edges shall be different , At least several colors are needed .

  In graph theory , Degree of a point （degree） Refers to the number of edges connected to this point in the graph .

Example ：

Regard the Department as a point , Departments with duplicate members are connected . According to the theorem

  The sequence of conditions is ： Each vertex can only have one color , The color of two connected vertices cannot be the same , Know the number of colors ,x Only for 0 perhaps 1.

clc,clear
s = {
   {' Zhang ',' Li ',' king '};{' Zhao ',' Li ',' Liu '};{' Zhang ',' Liu ',' king '};
     {' Zhao ',' Liu ',' Grandchildren '};{' Zhang ',' Grandchildren ',' king '};{' Liu ',' Li ',' king '}};
n = length(s);w = zeros(n);
for i = 1:n-1
    for j = i+1:n
        if ~isempty(intersect(s{i},s{j}))
            w(i,j) = 1;% If there is an intersection , Then there is a connection between the two points 
        end
    end
end
[ni,nj] = find(w);
w = w+w';
deg = sum(w);K = max(deg)% Find the maximum degree of the vertex , Theorem to use 
prob = optimproblem;
x = optimvar('x',n,K+1,'Type','integer','LowerBound',0,'UpperBound',1);
y = optimvar('y');
prob.Objective = y;
prob.Constraints.con1 = sum(x,2)==1;
prob.Constraints.con2 = x(ni,:)+x(nj,:)<=1;
prob.Constraints.con3 = x*[1:K+1]'<=y;
[s,fval,flag,o] = solve(prob)
[i,k] = find(s.x);
ik = [i';k']

Maximum flow problem

The maximum flow problem is the problem that makes the traffic in the network largest .

Feasible flow satisfies the condition ：

 c For the capacity of each line ,v Is the total traffic ,A Is the collection of all lines

It can be written as a linear programming model ：

  Example （ use matlab Built-in function ）：

  seek ① To ⑧ The maximum flow of ：

clc,clear
a = zeros(8);
a(1,[2:4])=[6,4,5];a(2,[3,5,6])=[3,9,9];
a(3,[4:7])=[5,6,7,3];a(4,[3,7])=[2,5];
a(5,8)=12;a(6,[5,8])=[8,10];
a(7,[6,8])=[4,15];
G=digraph(a);H=plot(G,'EdgeLabel',G.Edges.Weight);
[M,F]=maxflow(G,1,8);
F.Edges
highlight(H,F);

The maximum flow can also be obtained by planning .

Minimum cost flow problem

While completing the transportation , Seek the transportation scheme with the lowest transportation cost .

If v Greater than the maximum flow , There is no solution to the problem . 

Example ：

clc,clear
%%  First, find the maximum flow 
NN = cellstr(strcat('v',int2str([2:5]')));
NN = {'vs',NN{:},'vt'};% After the conversion is 1*6 Array of 
L  = {'vs','v2',5,3;'vs','v3',3,6;
    'v2','v4',2,8;'v3','v2',1,2;
    'v3','v5',4,2;'v4','v3',1,1;
    'v4','v5',3,4;'v4','vt',2,10;
    'v5','vt',5,2};
G  = digraph;
G  = addnode(G,NN);
G1 = addedge(G,L(:,1),L(:,2),cell2mat(L(:,3)));
[M,F] = maxflow(G1,'vs','vt')

H=plot(G1,'EdgeLabel',G1.Edges.Weight);
highlight(H,F);
%%  Minimum cost 
G2 = addedge(G,L(:,1),L(:,2),cell2mat(L(:,4)));
c  = full(adjacency(G1,"weighted"));% Export the flow matrix 
b  = full(adjacency(G2,"weighted"));% Export cost matrix 
f  = optimvar('f',6,6,'LowerBound',0);
prob = optimproblem;
prob.Objective = sum(b.*f,"all");
con1 = [sum(f(1,:))==M
        sum(f(:,[2:end-1]))'==sum(f([2:end-1],:),2)
        sum(f(:,end))==M];
prob.Constraints.con1 = con1;
prob.Constraints.con2 = f<=c;
[s,fval,flag,out] = solve(prob)
ff = s.f

Travel agent problem

Use the planning model ：

  Example ：

clc,clear
a = readmatrix('data.xlsx');
a(isnan(a)) = 0;n = 10;
b = zeros(n);
b([1:end-1],[2:end]) = a;
b = b+b';
b([1:n+1:end]) = 1000000;
prob = optimproblem;
x = optimvar('x',n,n,'Type','integer','LowerBound',0,'UpperBound',1);
u = optimvar('u',n,'LowerBound',0);
prob.Objective = sum(b.*x,"all");
prob.Constraints.con1 = [sum(x,2)==1;sum(x,1)'==1;u(1)==0];
con2 = [1<=u(2:end);u(2:end)<=14];
for i = 1:n
    for j = 2:n
        con2 = [con2;u(i)-u(j)+n*x(i,j)<=n-1];
    end
end
prob.Constraints.con2 = con2;
[s,fval,flag] = solve(prob)
xx = s.x;[i,j] = find(xx);
ij = [i';j']

The result is ：

  The optimal path is 1 3 7 9 10 8 4 5 6 2 1.