Exercises on Graphs¶

import matplotlib.pyplot as plt
import numpy as np
import networkx as nx


# Functions
def permute(M, P):
    return P@(P@M).transpose()

def make_perm_matrix(l):
    P = np.zeros((len(l),len(l)))
    for i,j in enumerate(l):
        P[i,j] = 1
        P[j,i] = 1
    return P

def drawmatrix(M):
    plt.figure(np.random.randint(20000))
    nx.draw(nx.Graph(M))

REMEMBER: DO NOT SOLVE PROBLEMS FOR THE ASSIGNMENT - AUTOMATICALLY CHECKING THE NUMBER OF AUTOMORPHISMS IS THE ASSIGNMENT!

Exercise 1¶

Let P1 and P2 be two permutation matrices. Is P1 × P2 also a permutation matrix? Argue for or against your answer.

# Example:

A = np.array([[0,0,0,1],[0,1,0,0],[0,0,1,0],[1,0,0,0]])
B = np.array([[1,0,0,0],[0,0,1,0],[0,1,0,0],[0,0,0,1]])

A@B

array([[0, 0, 0, 1],
       [0, 0, 1, 0],
       [0, 1, 0, 0],
       [1, 0, 0, 0]])

In general, yes. Consider P1 as an adjacency matrix of a graph instead. This graph has the property that every vertex has in- and out- degree exactly 1 (Permutation matrices have one '1' in each row and column). P2 now permutes this graph, but it still satisfies the same condition.

Corresponds to composing the permutations.

Exercise 2¶

Draw the graphs A and B

A = np.array([[0,1,1,1],[1,0,1,0],[1,1,0,1],[1,0,1,0]])
B = np.array([[0,1,1,0],[1,0,1,1],[1,1,0,1],[0,1,1,0]])

# Draw
plt.figure(1)

nx.draw(nx.Graph(A))

plt.figure(2)
nx.draw(nx.Graph(B))

Are the two graphs isomorphic?

Yes, the graphs are clearly isomorphic

How many different representations (in terms of adjacency matrices) of

GA are there?

All four nodes can be permuted, so 4! = 12

How many different representations (in terms of adjacency matrices) of

GB are there?

Ditto, 4! = 12

Is there a permutation matrix P s.t. A = P(PB)^T holds?

Yes, as they are clearly isomorphic

If so, give all matrices P s.t. A = P(PB)^T Hold

# Brute-force check all permutations of the two deg2 nodes and deg3 nodes (only 4 total)
print(make_perm_matrix([0,1,2,3])) #Trivial
print(make_perm_matrix([2,1,0,3]))
print(make_perm_matrix([0,3,2,1]))
print(make_perm_matrix([2,3,0,1]))

print('Permutation test')

print(permute( np.array([[1,2],[3,4]]), np.array([[0,1],[1,0]]) ))

#etc

[[1. 0. 0. 0.]
 [0. 1. 0. 0.]
 [0. 0. 1. 0.]
 [0. 0. 0. 1.]]
[[0. 0. 1. 0.]
 [0. 1. 0. 0.]
 [1. 0. 0. 0.]
 [0. 0. 0. 1.]]
[[1. 0. 0. 0.]
 [0. 0. 0. 1.]
 [0. 0. 1. 0.]
 [0. 1. 0. 0.]]
[[0. 0. 1. 0.]
 [0. 0. 0. 1.]
 [1. 0. 0. 0.]
 [0. 1. 0. 0.]]
Permutation test
[[4 2]
 [3 1]]

Exercise 3¶

Give an adjacency matrix A for the graph

A = np.array([[0,1,1],[1,0,1],[1,1,0]])
drawmatrix(A)

This is the only one!

For your chosen adjacency matrix, how many permutation matrices P are there s.t. A = P(PA)^T holds? (The size of the automorphism group)

All possible permutation matrices hold, as the graph is completely symmetric, 3! = 6

Exercise 4¶

Give adjacency matrix A for the graph

A = np.array([[0,1,1,0,0],[0,0,1,1,0],[0,1,0,1,0],[0,1,1,0,1],[0,0,0,1,0]])
drawmatrix(A)

For your chosen adjacency matrix, how many permutation matrices P are there s.t. A = P(PA)^T holds?

Two different, vertices 1, 2 can be permuted

Exercise 5¶

Given the following tow graphs G_a and G_b, give adjacency matrices

GA = np.array([[0,1,1,0],[1,0,1,0],[1,1,0,1],[0,0,1,0]])
drawmatrix(GA)

GB = np.array([[0,1,0],[1,0,1],[0,1,0]])
drawmatrix(GB)

Is G_B a subgraph of G_A?

Yes, clearly (both induced and not)

How many ways are there to find G_B as a subgraph of G_A?

Need to make n(A) x n(B) matrix as a 'permutation matrix'

At least 4

Exercise 6¶

The following is from the unit-testing of the graph theory assignment. Explain the expected result 10.

A = np.array([[ 0, 1, 0, 0, 1], \
[ 1, 0, 1, 0, 0], \
[ 0, 1, 0, 1, 0], \
[ 0, 0, 1, 0, 1], \
[ 1, 0, 0, 1, 0]])

drawmatrix(A)

Number of isomorphisms from/to itself.

10 automorphisms:

identity + 4 'rotations'
invert direction + 4 'rotations'

Exercise 7¶

Use sigma aldrich https://www.sigmaaldrich.com/DK/en/structure-search to look for chemical structures. How many structures can you find which have the following as a substructure?

Good example of application - subgraph of LSD

https://www.sigmaaldrich.com/DK/en/product/sigma/l7007

A = np.array([[0,0,]])

A = np.array([[0,0,1,1,1],[0,0,0,1,1],[1,0,0,0,0],[1,1,0,0,1],[1,1,0,1,0]])

P = make_perm_matrix([0,1,2,4,3])

print(P)

drawmatrix(A)

B = P@(P@A).T
print(A)
print(B)
drawmatrix(B)

[[1. 0. 0. 0. 0.]
 [0. 1. 0. 0. 0.]
 [0. 0. 1. 0. 0.]
 [0. 0. 0. 0. 1.]
 [0. 0. 0. 1. 0.]]
[[0 0 1 1 1]
 [0 0 0 1 1]
 [1 0 0 0 0]
 [1 1 0 0 1]
 [1 1 0 1 0]]
[[0. 0. 1. 1. 1.]
 [0. 0. 0. 1. 1.]
 [1. 0. 0. 0. 0.]
 [1. 1. 0. 0. 1.]
 [1. 1. 0. 1. 0.]]

A = np.array([[ 0, 1, 0, 0, 1], \
[ 1, 0, 1, 0, 0], \
[ 0, 1, 0, 1, 0], \
[ 0, 0, 1, 0, 1], \
[ 1, 0, 0, 1, 0]])

drawmatrix(A)