# 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()