Question

matlab 以坐标画圆

随机生成一组坐标，然后以此坐标为圆心，再一另一组随机数做为半径画圆，查看圆之间有没有相互覆盖，并显示出来，最好能生成用户邻接图然后在用户邻接图中找完全子图，使得完全子图的数目尽量少。将属于不同子图的用户标注，用颜色加以区分。

Answer 1

n=5;%节点个数

x=rand(n,1);%随机x坐标

y=rand(n,1);%随机y坐标

r=rand(n,1)/4;%随机半径

t=0:360;

figure(1);

clf;

hold on;

for ii=1:n 

    plot(x(ii),y(ii),'r.');%画出随机5点

    plot(x(ii)+r(ii)*cosd(t),y(ii)+r(ii)*sind(t));%画圆

    text(x(ii),y(ii),num2str(ii));%标节点号

end

a=false(n);

for ii=1:n

    a(ii,:)=sqrt((x-x(ii)).^2+(y-y(ii)).^2)<=r+r(ii);%利用距离判断生成邻接矩阵

end

a=a-eye(n); %令对角元素为0

gplot(a,[x,y],'k');%画邻接关系图，这里使用了原来的随机x，y坐标

axis equal;

hold off;

这是其中一次随机的结果，找子图等操作留给你自己完成

追问

完全子图是不是就是最大独立集啊或者极大团？？？？

追答

先去看完全图的定义
完全图是所有节点都亮亮相连的图n个节点的完全图有n(n-1)/2条无向边

完全子图，应该就是从图中找出的子图要满足完全图

追问

貌似是你说的那样，额，能给个思路么

追答

1如果图不是空图，从图中任找一个点

2寻找包含此节点的最大完全子图

3记录找到的完全子图包含的节点，分在一个类中

4从图中删除这些节点(删除对应邻接矩阵的行和列）

5用剩下节点和边组成的图回到步骤1

其中关键是2寻找包含某节点的最大完全子图，这一步
可以上网搜搜最大完全子图用什么算法

从不同点开始可能有不同的分类办法
每个类里面的元素根据能够组成完全图
但是分得的类别的总数是不会变的

就如我上边随机得到的图，可能的分类有两种
2 3 1 4 5
2 3 4 5 1
每个子图都是完全图，两种分法子图的总数都是3

Answer 2

画圆不是关键，只需要两两判断用户之间的距离即可。
用邻接矩阵表示上述图的结构就可以。

追问

额，能不能具体实现一下

追答

没人帮你写整个问题的代码的。至少也得自己把问题分解一下才有可能。
另外，自己分解完了以后，多搜一搜，这些问题都是比较常规的问题，会有现成代码。