7/10

gt93

今天凉爽，感觉秋天不远了，开学也不远了。今天的课程是图论V点E边，路指顶点序列，网络是图的所有边都具有权值。图的存储方法：邻接矩阵和关联矩阵。重点讲了邻接矩阵，这里我先说关联矩阵。Aij表示Vi与ej的关联次数

Case vi是ej的始点  aij=1

Case vi是ej的终点  aij=-1

Case 不关联 aij=0

下面介绍邻接矩阵

一般图  case i=j aij=0  case i!=j (i,j)属于E aij=1 (i,j)不属于E aij=0

网络图 case i=j aij=0 case i!=j (i,j)属于E aij=w(i,j) (i,j)不属于E aij=inf

接下来讲了最短路问题

若从图中的某一点到达另一点的路径不止一条，如何寻找一条路径，使得沿此路径各个边上的权值总和最小，这条路就是最短路。输入邻接矩阵输出d ，di表示由源点到第i个点的最短路径，index2为顶点索引，许峰说可以用2行代码改进index2。课间和同学一起讨论了C的一个实现方法，回来后自己实现了MATLAB的写法。

（clear

i=input('请输入到第i个点：');

a=[1 3 1 6 2 3];%等待排序的路径

b=a(i);

while b~=1

disp(b)

c=a(b);

disp(c)

b=a(c);

end

disp(1)%倒序得出路径

）接下来讲了最小生成树，不包含圈的连通圈称为树，包含图所有点的极小连接子图称为G的生成树。可行遍历，中国邮递员遍历边，旅行商问题遍历点。网络流＾>都为前向，最大流等于最小割的容量。下午上机调试了最短路的Dijkstra和Floyd算法。最小生成树的Kruskal和Prim算法。图论最大流的Flod_Fulkerson和Dinic算法，最大流最小费用的Busacker_Gowan迭代法。Euler环游（遍历边）的Fleury算法，Tsp（遍历点）的改良圈算法。明天放假一天。

0 \6 V9 L7 P. N# \4 T/ K6 F7 E: s0 k