图论算法matlab实现问题

修改的地方包括：

1、原程序为函数，提供了邻接矩阵和关联矩阵的双向转换，这里针对楼主的需求改为脚本，直接运行即可将邻接矩阵转为关联矩阵。

2、部分语句修改更符合MATLAB的通行写法，如：

sum(sum(F))改为sum(F(:))，

W(i,k)=1W(j,k)=1改为W([i j],k)=1

3、考虑到邻接矩阵为对称阵，第二个for循环改为只针对半个矩阵，减少计算量（对于楼主的这个具体作用微乎其微）。

4、原程序有错误，在else分支fprint为fprintf之误（其实我看到该程序的第一眼就注意到了这个错误，担心还存在其它问题，所以进行了改写）。

F=[0 1 1 11 0 1 11 1 0 11 1 1 0] % 邻接矩阵

m = sum(F(:))/2 % 图的边数

n = size(F,1) % 顶点数

W = zeros(n,m)

k=1

for i = 1:n

for j = 1:i

if F(i,j)~=0

W([i j],k)=1

k = k + 1

end

end

end

W

一、求出这个图的补图　 （1）输入无向图的各边所关联的顶点对，确定每个顶点度，以及图的最大度数和最小度数，求出这个图的补图。

（2）输入有向图的各边所关联的顶点对，确定每个顶点的出度和入度。

二、　编写一个程序，要求于无向图和有向图都能做到：输入图的邻接矩阵和正整数n，求长度为n的链和圈。

三、模拟判断一个程序中是否存在递归的函数，若存在，如何消除递归。

四、输入图的边，确定这是否为连通图。

（1）若不是连通图，则确定连通分图的个数；

（2）若是连通图，判断是否存在割边和割点，若存在各是什么？

五、输入一个多重图各边关联的顶点对。

（1） 判断它是否存在欧拉圈，若存在，则求出一个欧拉圈；

（2）若不存在，则判断是否存在一个欧拉链，若存在则求之。

六、输入一个简单图的边列表。

（1）确定是否存在哈密尔顿圈，若存在求该哈密尔顿圈；

（2）若不存在，判断是否存在哈密尔顿链，若存在则求之。

七、自选一个算法求货郎担问题。

八、给定带权连通简单图的边及权列表，输入图中两个顶点，求两点是否可达？若可达距离为多少？并输出这条最短的链。

提示：

可以使用Dijkstra算法——迪杰斯特拉算法）

九、给定无向图的边列表，对该图进行着色，求着色数。

十、输入一个加权无向简单图的边及权列表，求最小生成树，以及这棵最小生成树的权。

十一、输入一段文章，全部用小写字母，求各字母的哈夫曼编码。

十二、要给n个人分配m个资源，输入每个人可以获得的资源情况，求最大匹配，

要求所有资源在满足尽可能多的人获得的情况下，全部分配出去。