www.gusucode.com > 里面有最大流，最小费用最大流和着色问题的matlab程序和lingo程序 > 里面有最大流，最小费用最大流和着色问题的matlab程序和lingo程序/最大流，最小费用流，着色程序/着色问题welsh-powell算法.m

    %命令窗口输入
%e=[0 1 1 1 0 1 1
%     1 0 1 0 1 1 0
%    1 1 0 1 1 0 0
%   1 0 1 0 1 0 1
%  0 1 1 1 0 0 0
% 1 1 0 0 0 0 0
%1 0 0 1 0 0 0];
function [a1,b1]=sort2(n,a,b)%排序
[m,n]=size(a);
for h=1:n-1
  for j=1:n-h
   if a(j)<a(j+1)
      t1=a(j);a(j)=a(j+1);a(j+1)=t1;
     t2=b(j);b(j)=b(j+1);b(j+1)=t2;
  end
end
end
a1=a;
b1=b;


function welsh(n,e)
totalcolor=0;%e为邻接矩阵
temp=zeros(1,n);%临时矩阵 

for (i=1:n)  temp=e(i,:);t(i)=sum(temp);temp=0;q(i)=i;c(i)=i;end%t记录vi的度－邻接矩阵行和，q记录顶点标号,c：颜色集
[t,q]=sort2(n,t,q);%按度排序
[m,n]=size(e);
bepaint=zeros(m,n);%初始化着色矩阵
for i=1:n bepaint(i,:)=c; end 
i=1;

    for j=1:n%顶点－行
      pcivj=min(bepaint(j,:));bepaint(j,i)=pcivj;%求行最小值
        for k=j+1:n
            if (e(j,k)==1) bepaint(k,i)=bepaint(k,i)+inf;end
        end
         pcivj=0;i=i+1;
    end
bepaint