616.sagews

Here, we get all graphs indexed by the Atlas of Graphs number.

import networkx.generators.atlas
atlas_graphs = [Graph(i) for i in networkx.generators.atlas.graph_atlas_g()]

g=atlas_graphs[1225]
show(g)

The next (hidden) cell contains our minimum rank code for the real field.  However, things like the zero forcing bound hold for all fields, so it can still be useful.  Click on "%hide" to see the code, or see below for examples using the code.

print minrank_bounds(g)

(3, 3)

lower,upper = minrank_bounds(g, all_bounds=True)
print "Lower bounds: ", lower
print "Upper bounds: ", upper

Lower bounds: {'precomputed': 3, 'forbidden minrank 2': 3, 'zero forcing': 3, 'rank': 0, 'diameter': 2} Upper bounds: {'clique cover': 5, 'precomputed': 3, 'not path': 5, 'not outer planar': 4, 'order': 6, 'rank': 7, 'not planar': 3}

find_zero_forcing_set(g)

{0, 1, 2, 3}

minimum_rank(FiniteField(3), graphs.PathGraph(4))

min rank example: rank 3 [1 1 0 0] [1 1 1 0] [0 1 0 1] [0 0 1 0] matrix(GF(3), [[1, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 1], [0, 0, 1, 0]]) (3, [1 1 0 0] [1 1 1 0] [0 1 0 1] [0 0 1 0])

def minimum_rank(F, g):
    """
    Returns the minimum rank of the graph g over the field F.  This is done by exhaustively iterating 
    through all possible matrices in S(F,G).
    
    EXAMPLES:
        
        sage: min_rank, mat = minimum_rank(FiniteField(3), graphs.PathGraph(4))
        sage: min_rank
        3
        sage: mat
        [1 1 0 0]
        [1 1 1 0]
        [0 1 0 1]
        [0 0 1 0]
    """
    A=g.adjacency_matrix().change_ring(F)
    n=g.order()
    nonzero_elements = [e for e in F if e != 0]
    all_possible_nonzero_entries = CartesianProduct(*[nonzero_elements]*g.size())
    nonzero_positions = set(g.edges(labels=False))
    diagonals = VectorSpace(F, n) # The vector space of n-dimensional vectors over F

    minimum_rank = n

    for nonzero_entries in all_possible_nonzero_entries:
        #print "testing nonzero entries: ", nonzero_entries
        
        # Set the nonzero positions
        for position, entry in zip(nonzero_positions, nonzero_entries):
            A[tuple(position)] = entry
    
        # Iterate through all the diagonals
        for diagonal in diagonals:
            for index, diagonal_entry in enumerate(diagonal):
                A[index, index] = diagonal_entry

            new_rank = A.rank()
            if new_rank < minimum_rank:
                minimum_rank = new_rank
                minimum_rank_matrix = A.copy()
                print "min rank example: rank ", minimum_rank
                print minimum_rank_matrix
                print sage_input(minimum_rank_matrix)
                print

    return minimum_rank, minimum_rank_matrix

%time
minimum_rank_slow(FiniteField(3), g)

(4, [1 1 0 0 0 0] [1 1 0 0 1 1] [0 0 1 1 1 1] [0 0 1 1 0 0] [0 1 1 0 2 1] [0 1 1 0 1 0]) CPU time: 9.17 s, Wall time: 9.50 s

g=graphs.PetersenGraph()
g.show()

minrank_bounds(g)

(5, 6)

lower,upper = minrank_bounds(g, all_bounds=True)
print "Lower bounds: ", lower
print "Upper bounds: ", upper

Lower bounds: {'diameter': 2, 'forbidden minrank 2': 3, 'zero forcing': 5, 'rank': 0} Upper bounds: {'clique cover': 15, 'not path': 8, 'not outer planar': 7, 'order': 9, 'rank': 10, 'not planar': 6}

g=graphs.DodecahedralGraph()
print "%s vertices, %s edges"%(g.order(), g.size())
g.show3d()

20 vertices, 30 edges

# Stereoscopic views too!

lower,upper = minrank_bounds(g, all_bounds=True)
print "Lower bounds: ", lower
print "Upper bounds: ", upper

Lower bounds: {'diameter': 5, 'forbidden minrank 2': 3, 'zero forcing': 14, 'rank': 0} Upper bounds: {'clique cover': 30, 'not outer planar': 17, 'not path': 18, 'order': 19, 'rank': 20}

g.show()

find_zero_forcing_set(g)

{0, 1, 2, 3, 4, 5}