# Alfonso Cevallos. April 21 2015.
# Please report any mistakes.
# This week we work with Python integers.
# We also compute the determinant using the library numpy
import math
import os
import random
import numpy
def HasPerfectMatching(A,K):
# returns True if graph G has a perfect matching,
# where A is the adjacency matrix of G.
# K is the security parameter.
# We transform A itself into the Tutte matrix, with random variables between 1 and 2n
for k in range(K):
for i in range(len(A)):
for j in range(i):
if A[i][j] != 0:
ran = random.randint(1, 2*len(A))
A[i][j] = ran
A[j][i] = -ran
Det = numpy.linalg.det(A)
if abs(Det) >= 1: return True
return False
def PickEdge(A):
# Returns (u,v), where (u,v) is an edge, and u > v.
# It also erases the edge from G, i.e. it modifies A
# by setting A[u][v] = A[v][u] = 0.
for i in range(len(A)):
for j in range(i):
if A[i][j] != 0:
A[i][j] = 0
A[j][i] = 0
return i,j
return
def FindPerfectMatching(A,K):
# Returns list M corresponding to a perfect matching,
# Where M[u]=v and M[v]=u, if uv is an edge in the matching.
# And A is the adjacency matrix of G.
# Returns -1 if there is no perfect matching.
# K is the security parameter.
# This is a recursive algorithm. From a perfect matching of a subgraph
# we build a perfect matching of the original graph.
if len(A)==0: return []
if not HasPerfectMatching(A,K): return -1
u,v = PickEdge(A) #take an edge, and remove it from G.
if HasPerfectMatching(A,K): return FindPerfectMatching(A,K) #if there's still perfect matching, ignore edge
else: # else, remove vertices, find a perfect matching of G-u,v, and add uv to matching.
for i in range(len(A)): # here we remove vertices u and v from G
del A[i][u]
del A[i][v]
del A[u]
del A[v]
M = FindPerfectMatching(A,K) #this is the "partial" matching, for G - u,v
for i in range(len(M)): #we update the labels, needed to insert u and v
if M[i] >= v: M[i] += 1
if M[i] >= u: M[i] += 1
M.insert(v,u) #we insert edge uv into matching
M.insert(u,v)
return M
def Test():
A = [[0,0,0,1,0,1], [0,0,0,1,1,0], [0,0,0,0,0,1], [1,1,0,0,1,0], [0,1,0,1,0,1],[1,0,1,0,1,0]]
print "The graph G has adjacency matrix "
for V in A: print V
M = FindPerfectMatching(A,6)
if M == -1: print "\nG has no perfect matching."
else:
print "\nA perfect matching is coded here: M = ", M
print "where the vectors are labeled from 0 to 5,"
print "and for edge (u,v) in the matching we have M(u)=v, M(v)=u.\n"
B = [[0,1,1,1], [1,0,0,0], [1,0,0,0], [1,0,0,0]]
print "The graph H has adjacency matrix "
for V in B: print V
N = FindPerfectMatching(B,6)
if N == -1: print "\nH has no perfect matching"
else: print "\nA perfect matching is ", N
Test()