> restart: n:=4:
> A:=[[1,7,1,3],[1,6,4,6],[17,1,5,1],[1,6,10,4]]:
eqWorld.ipmnet.ru eqWorld.ipmnet.ru
> w:=0:
> for i1 to n do
> for i2 to n do
> for i3 to n do
> for i4 to n do
> if((i1<>i2)and(i1<>i3)and(i1<>i4)
> and(i2<>i3)and(i2<>i4)and(i3<>i4))
> then w:=w+1;
> S[w]:=add(A[i||k,k],k=1..n);
> fi;
> od;
> od;
> od;
> od;
> MinSum:=min(seq(S[i],i=1..w));
> restart: n:=4:
> N:=1..n:
> with(LinearAlgebra):
> A:=Matrix([[1,7,1,3],[1,6,4,6],[17,1,5,1],
> [1,6,10,4]]):
> A0:=A:
> A1:=Matrix(n):
Из каждой строки вычитаем min
> for i to n do
> m:=min(op(convert(Row(A,i),list)));
> R[i]:=convert(map(‘-‘,Row(A,i),m),list);
> od:
> A:=Matrix([seq(R[i],i=N)]):
Из каждого столбца вычитаем min
> for i to n do
> m:=min(op(convert(Column(A,i),list)));
> C[i]:=convert(map(‘-‘,Column(A,i),m),list);
> od:
> A:=Transpose(Matrix([seq(C[i],i=N)])):
> n1:=1:
> while n1<>n do # Пока паросочетание несовершенное
> for i to n do # Матрица A1 двудольного графа
> for j to n do
> if A[i,j]=0 then A1[i,j]:=1
> else A1[i,j]:=0:fi;
> od:
> od:
> read "C:\\SBDISKR\\MAPLE\\bipart.m";
> B:=Matrix(n):
> BipartCard(A1): # Максимальное паросочетание
> n1:=nops(op(B)[3]):# Число 1 в матрице B
> C:=A1-B: # Матрица графа с дугами от X к Y
> XM:={}:YM:={}:
Множества вершин, не входящих в паросочетание
> for i to n do
> if not 1 in convert(Row(B,i),list)
> then XM:=XM union {i} fi;
> if not 1 in convert(Column(B,i),list)
> then YM:=YM union {i} fi;
> od:
> Xs:=XM: Ys:={}:
> L12:=1;
> while L12<>0 do# Пока не установится процесс
> L1:=nops(Xs):
> for k in Xs do
> for j to n do
> for i to n do
> if C[k,i]=1 then
> Ys:=Ys union {i};
> if B[j,i]=1 then Xs:=Xs union {j};fi;
> fi;
> od;
> od;
> od;
> L12:=L1-nops(Xs):
> od:
> Y0:={$N} minus Ys:
Подматрица из строк Xs и столбцов Y0
> sbm:=SubMatrix(A,[op(Xs)],[op(Y0)]):
Минимальный элемент подматрицы
> m:=min(op(convert(sbm,set)));
> for i to n do
> for j to n do
> if i in Xs then A[i,j]:=A[i,j]-m; fi;
> if j in Ys then A[i,j]:=A[i,j]+m; fi;
> od;
> od;
> od:
> MinSum=add(add(B[i,j]*A0[i,j],i=N),j=N);
MinSum = 7-- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
