当前位置：网站首页>Mathematical modeling -- graph and network models and methods (I)

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

2022-07-02 22:39:00 【Herding cattle】

Catalog

Basic concepts

MATLAB Tool box use

Shortest path algorithm

The shortest circuit of the fixed starting point

The shortest path between all vertex pairs

0-1 Integer programming method

Basic concepts

chart , It is composed of some points and the connecting lines between these points .

|V| Diagram G The number of vertices in ,|E| Indicates the number of sides . Each edge is connected by G A line obtained from two vertices in , Write it down as ： $c_{k}=(v_{i},v_{j})$ ,vi and vj Called edge $c_{k}$ Two endpoints of . In the undirected graph , The vertex pair representation of an edge is disordered , That is to say $(v_{i},v_{j})$ and $(v_{j},v_{i})$ It means the same side $c_{k}$ . Two edges with common vertices are called adjacent edges , Also known as Adjacent edge . Two vertices of the same edge are called Adjacent vertices . An edge with a direction is called There is a directional side , Also known as arc . If you specify a direction for each edge of an undirected edge , Got it. Directed graph .

Ring ： The two endpoints of an edge are the same vertex . Heavy edge （ Parallel sides ）： The endpoints of two or more edges are the same pair of vertices . Isolated point ： Vertices that are not connected to any edge . Simple picture ： A graph without rings and double edges . Complete graph ： A simple graph in which any two vertices are adjacent . contain n The complete graph of vertices is $K_{n}$ . Empowerment map ： Each side of the graph is attached with a real number , Real numbers are called weights . Write it down as G=(V,E,W) .

The degree of the vertex ： In the undirected graph , And the summit v Number of associated edges （ The ring counts twice ） be called v Degree , Write it down as d(v). In the directed graph , From the top v The number of arcs drawn is called v The degree of , Write it down as $d^{+}(v)$ , From the top v The number of arcs introduced is called v The degree of , Write it down as $d^{-}(v)$ , $d(v)=d^{+}(v)+d^{-}(v)$ be called v Degree . Vertices with odd degrees are called Odd vertex , Even vertices are called Even vertices .

Theorem ：

The matrix representation of a graph

Correlation matrix ：（ Different software definitions may be different ）

Adjacency matrix ：

for example ：

MATLAB Tool box use

Graph generation ：

S = sparse(A)
% The matrix A Convert to sparse matrix form , Matrix A In any of the 0 The elements are removed ,⾮ Zero elements and their subscripts form a matrix S. If A Ben ⾝ Is sparse ,sparse(S) return S.
A=full(X)
% Put the sparse matrix X Convert to full matrix storage form A

MATLAB In general, sparse matrix is used to generate adjacency matrix

for example ： Draw the following non weighted digraph and derive the adjacency matrix and incidence matrix

clc,clear,close all
E = [1,2;1,3;2,3;3,2;3,5;4,2;4,6;5,2;5,4;6,5];
s = E(:,1);
t = E(:,2);
nodes = cellstr(strcat('v',int2str([1:6]')))
%cellstr Used to convert to a character vector cell array 
%strcat Used to concatenate strings horizontally 
G = digraph(s,t,[],nodes);
plot(G,'LineWidth',1.5,'Layout','circle','NodeFontSize',15)
%layout Parameters can be found in the help document 
W1 = adjacency(G)% Sparse matrix for deriving adjacency matrix 
W2 = incidence(G)% Sparse matrix for deriving incidence matrix , Use full Function to restore

Shortest path algorithm

Pipe laying 、 Routing 、 Plant layout 、 Device update can be attributed to the shortest path

Definition ：

If two vertices have more than one path , Then the shortest length is called two points $u_{0},v_{0}$ Distance of , Write it down as $d(u_{0},v_{0})$

The algorithms for calculating the shortest path include dixtra labeling algorithm and Freud Algorithm , The former only applies when the edge weight is nonnegative . The shortest path problem can also be reduced to a 0-1 Integer regularization model .

The shortest circuit of the fixed starting point

Seek the shortest path from one fixed point to the rest ,Dijkstra The algorithm is very effective , It is an iterative algorithm .

MATLAB Toolbox , If there is no edge between two vertices , The corresponding adjacency matrix elements are 0, Instead of corresponding to infinity or 0.

Example

The line side figure is the required cost , Seek from 1 To 8 The least expensive travel route .

clc,clear,close all
E = [1,2,6;1,3,3;1,4,1;2,5,1;3,2,2;
    3,4,2;4,6,10;5,4,6;5,6,4;5,7,3;
    5,8,6;6,5,10;6,7,2;7,8,4;9,5,2;9,8,3];
G = digraph(E(:,1),E(:,2),E(:,3));% The starting point , End , The weight 
plot(G);
[path,d] = shortestpath(G,1,8,"Method","positive")%1,8 Represents the source and termination nodes ,method You can see the help document ,positive It stands for Dijkstra Algorithm

You can make path The point becomes bigger .

For weighted undirected graphs , Use the above code graph Function is OK , Another kind ( seek 1 To 11)：

clc,clear,close all
a=zeros(11);
a(1,2)=2;a(1,3)=8;a(1,4)=1;
a(2,3)=6;a(2,5)=1;
a(3,4)=7;a(3,5)=5;a(3,6)=1;a(3,7)=2;
a(4,7)=9;a(5,6)=3;a(5,8)=2;a(5,9)=9;
a(6,7)=4;a(6,9)=6;a(7,9)=3;a(7,10)=1;
a(8,9)=7;a(8,11)=9;
a(9,10)=1;a(9,11)=2;a(10,11)=4;
s=cellstr(strcat('v',int2str([1:11]')));
G=graph(a,s,'upper');
[p,d]=shortestpath(G,1,11);
h=plot(G,'EdgeLabel',G.Edges.Weight);% Show the weights on the graph 
highlight(h,p,'EdgeColor','red','LineWidth',2);% Highlight the path 

%% [p,d,ed]=shortestpath(G,1,11);
%% highlight(h,"Edges",ed)

The shortest path between all vertex pairs

use Floyd Algorithm , This algorithm allows the weighted graph to contain negative weighted edges or arcs , however , The sum of all arcs on each circuit is non negative .

The iterative formula is used in the calculation ：

k For the number of iterations , When k=n when , Get the shortest distance between vertices .

Example

Find the shortest distance matrix between all vertices ：

clc,clear,close all
a=zeros(4);
a(1,[3,4])=[10,60];
a(2,[3,4])=[5,20];
a(3,4)=1;
n=length(a);
b=a+a';
b(b==0)=inf;%
b([1:5:end])=0;% Convert it into a standard adjacency matrix 
path=zeros(4);
for k=1:n
    for i=1:n
        for j=1:n
            if b(i,j)>b(i,k)+b(k,j)%b(i,j) From i To j
                b(i,j)=b(i,k)+b(k,j);
                path(i,j)=k;
            end
        end
    end
end
b,path

Call directly Dijkstra The algorithm can find the shortest distance between each vertex :

clc,clear,close all
a=zeros(4);
a(1,[3,4])=[10,60];% Define adjacent points 
a(2,[3,4])=[5,20];
a(3,4)=1;
G=graph(a,'upper');
d=distances(G,'Method','positive')

0-1 Integer programming method

Example

seek 2 To 4 The shortest path and the shortest distance （ The first condition i It does not include the beginning 、 Termination point ）

clc,clear,close all
a=zeros(6);
a(1,[2,5])=[18,15];
a(2,[3,4,5])=[20,60,12];
a(3,[4,5])=[30,18];
a(4,6)=10;
a(5,6)=15;
b=a+a';
b(b==0)=1000000% A sufficiently large positive real number is sufficient 
x=optimvar('x',6,6,'Type','integer','LowerBound',0,'UpperBound',1);
p=optimproblem("Objective",sum(b.*x,"all"));
con=[sum(x(2,:))==1;
    sum(x(:,2))==0;
    sum(x(:,4))==1];
for i = [1,3,5,6]% Does not include the beginning 、 Termination point 
    con=[con;sum(x(i,:))==sum(x(:,i))];
end
p.Constraints=con;
[s,f]=solve(p),xx=s.x
[i,j]=find(xx);
ij=[i';j']