def extended_cube_graph(t,k):
"""
Returns an extended cube graph
:t: a nonnegative integer
:k: a nonnegative integer
:returns: extended cube graph
"""
n = 2*(t+k)+8
g = graphs.CycleGraph(n)
v1=[i+0 for i in range(k+2)]
v2=[i+k+2 for i in range(t+2)]
v3=[i+k+t+4 for i in range(k+2)]
v4=[i+2*k+t+6 for i in range(t+2)]
horizontal_edges = [(v2[i],v4[-i-1]) for i in range(t+2)]
vertical_edges = [(v1[i],v3[-i-1]) for i in range(k+2)]
g.add_edges(horizontal_edges)
g.add_edges(vertical_edges)
return g
|
|
extended_cube_graph(1,2)
|
def list_matrices_Z_2(g,Z,p=2):
"""
:g: A graph.
:Z: The zero forcing number of the given graph.
:returns: A set of tuples with entries corresponding to nonzero diagonal
entries of a potential universally optimal matrices.
:Example:
sage: g=graphs.CycleGraph(7)
....:
sage: list_matrices_Z_2(g,2)
....:
The graph has 21 matrices that achieve minimum rank of 5 over Z_2
{(0, 1, 2),
(0, 1, 2, 3, 5),
(0, 1, 2, 4, 6),
(0, 1, 3, 5, 6),
(0, 1, 4),
(0, 1, 6),
(0, 2, 3, 4, 5),
(0, 2, 4, 5, 6),
(0, 3, 4),
(0, 3, 6),
(0, 5, 6),
(1, 2, 3),
(1, 2, 3, 4, 6),
(1, 2, 5),
(1, 3, 4, 5, 6),
(1, 4, 5),
(2, 3, 4),
(2, 3, 6),
(2, 5, 6),
(3, 4, 5),
(4, 5, 6)}
"""
import itertools
n = g.order()
integer_set = [i for i in range(n)]
nonzero_set = set([ ])
for L in range(n+1):
for subset in itertools.combinations(integer_set, L):
A=g.am()
for i in range(L):
j = subset[i]
A[j,j]=1
A=matrix(GF(p),A)
if A.rank() == n-Z:
nonzero_set.add(subset)
print("The graph has {} matrices that achieve minimum rank"
" of {} over Z_{}".format(len(nonzero_set),n-Z,p))
return nonzero_set
|
|
C7=graphs.CycleGraph(7)
P2=graphs.PathGraph(2)
g=C7.cartesian_product(P2)
|
|
list_matrices_Z_2(g,4)
The graph has 0 matrices that achieve minimum rank of 10 over Z_2 set() The graph has 0 matrices that achieve minimum rank of 10 over Z_2 set() |
|
|