学习常用模型及算法：4.图论模型和算法

美赛中涉及到图论的题是比较多的。

无向图是由边、节点和关联函数构成的。关联函数说明了哪条边由哪两个节点构成。

再简单图里，我们说的边就是连杆。

在有向图中，关联函数里前后两点的顺序不能颠倒。

将原图去掉一些边和节点得到的图就是子图

完全二分图：将所有点分为两个集合，集合里面的每个点都与另一个集合内的所有点连接。

星图是完全二分图的特殊情况。

在路里面，除了首尾节点以外，其他任意节点都是入度为1，出度为1。

图有两种矩阵表现形式：关联矩阵和邻接矩阵。其中matlab用的最多的还是邻接矩阵。

这是有关节点的几个中心度。

图论工具箱

matlab有自带的工具箱，省去了很多繁琐的步骤。

满矩阵和稀疏矩阵可以相互转化

例：求A-F点的最短路径

[a, b, c, d, e, f] = deal(1, 2, 3, 4, 5, 6);
w = [0 2 3 0 0 0
     2 0 6 5 3 0
     3 6 0 0 1 0
     0 5 0 0 1 2
     0 3 1 1 0 4
     0 0 0 2 4 0];
 
 W = sparse(w)
 [dist, path, pred] = graphshortestpath(W, a, f)

W =

   (2,1)        2
   (3,1)        3
   (1,2)        2
   (3,2)        6
   (4,2)        5
   (5,2)        3
   (1,3)        3
   (2,3)        6
   (5,3)        1
   (2,4)        5
   (5,4)        1
   (6,4)        2
   (2,5)        3
   (3,5)        1
   (4,5)        1
   (6,5)        4
   (4,6)        2
   (5,6)        4


dist =

     7


path =

     1     3     5     4     6


pred =

     0     1     1     5     3     4

所以最短路径为1 3 5 4 6

网络分析工具箱

如图，求得点度中心度和接近中心度。

图论常用算法

1.求最短路径

[a, b, c, d, e, f] = deal(1, 2, 3, 4, 5, 6);
w = [0 2 3 0 0 0
     2 0 6 5 3 0
     3 6 0 0 1 0
     0 5 0 0 1 2
     0 3 1 1 0 4
     0 0 0 2 4 0];
 
 W = sparse(w);
 [dist, path, pred] = graphshortestpath(W, 1, 6)

dist =

     7


path =

     1     3     5     4     6


pred =

     0     1     1     5     3     4

2.最小生成树

w = [0 4 inf 5 inf 3
     4 0 5 inf 3 3
     inf 5 0 5 3 inf
     5 inf 5 0 2 4
     inf 3 3 2 0 1
     3 3 inf 4 1 0];
 W = sparse(w);
 [ST, pred] = graphminspantree(W)
 st = full(ST)

ST =

   (6,1)        3
   (6,2)        3
   (5,3)        3
   (5,4)        2
   (6,5)        1


pred =

     0     6     5     5     6     1


st =

     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     0     0     0     0
     0     0     3     2     0     0
     3     3     0     0     1     0

3.最短Hamilton回路

tic
lat = [ 39.54  31.14  39.09  29.32  45.45 ...	   
        43.52  41.50  40.49  38.02  37.52 ...	
        36.38  34.48  34.16  36.03  38.20 ...	
        36.38  43.48  31.51  32.02  30.14 ...	
        28.11  28.41  30.37  30.39  26.35 ...	
        26.05  23.08  20.02  22.48  25.00 ...
        29.39  22.18  22.14  25.03          ];

lon = [116.28 121.29 117.11 106.32 126.41 ...	  
       125.19 123.24 111.48 114.28 112.34 ...
       117.00 113.42 108.54 103.49 106.16 ...	
       101.45  87.36 117.18 118.50 120.09 ...
       113.00 115.52 114.21 104.05 106.42 ...	
       119.18 113.15 110.20 108.20 102.41 ...
        90.08 114.10 113.35 121.31          ];

n = length(lat);

R = 6378.137;

dist = zeros(n);
for i = 1:n
    for j = i+1:n
        dist(i,j) = distance(lat(i),lon(i), lat(j),lon(j), R);
    end
end

dist = dist + dist';
[order,totdist] = minhamiltonpath(dist)
plot(lon(order(1:end)), lat(order(1:end)),'o-')

order =

  1 至 17 列

     3     5     6     7    11    18    19     2    20    34    26    22    23    21    27    32    33

  18 至 34 列

    28    29    25     4    24    30    31    17    16    14    15    13    12    10     8     9     1


totdist =

     1.565184183216451e+04