p27.mws 

#Кирсанов М.Н. Графы в Maple ,   М.: Физматлит 2007

 

>    #Программа 27 с. 134

Наибольшее паросочетание в графе

>    restart: with(networks):

>    new(G):     

>    n:=3:      # Число вершин в каждой доле

>    V:=$1..2*n:# Вершины

>    r:=[seq(n+1-i,i=1..n)],[seq(2*n+1-i,i=1..n)]:

>    addvertex(V,G):

>    #addedge([{1,7},{1,8},{1,9},{1,10},{1,11},{1,12},
#{2,7},{2,8},{3,7},{3,9},{4,7},{4,9},{4,10},{4,11},{4,12},{5,7},{6,12}],G):# Пример на с.128

>    addedge([{1,4},{2,4},{2,5},{2,6},{3,5}],G):                              # c.134

>    draw(Linear(r),G);

[Maple Plot]

>    A:=Matrix(n):#

>    for x in edges(G) do

>      A[ends(x,G)[1],ends(x,G)[2]-n]:=1;

>    od:

>    A;

Matrix(%id = 150562912)

>    read "C:\\bipart.m";

>    B:=Matrix(n):

>    BipartCard(A):

>    B_=B;

B_ = Matrix(%id = 150563152)

>    E:={}:#Ребра для графа наибольшего паросочетания

>    for i to n do

>       for j to n do

>         if B[i,j]=1 then E:=E union {{i,j+n}} fi:

>       od;

>    od;

Наибольшее паросочетание

>    new(G1): addvertex(V,G1):

>    addedge(E,G1): draw(Linear(r),G1);

[Maple Plot]

Число совершенных паросочетаний

>    LinearAlgebra[Permanent](B);

1