BFS Spanning Tree

This notebook illustrates how to create a spanning tree of a graph with vertex labels consistent with breadth-first search traversal.

%%capture
%run receptor_tools.ipynb

P = graphs.PetersenGraph()
P.show(edge_labels=False)
(BFSVertexList,BFSTree) = P.lex_BFS(tree=True,initial_vertex=0)
BFSTree.show(edge_labels=False)
show(BFSVertexList)

\(\displaystyle \left[0, 1, 4, 5, 2, 6, 3, 9, 7, 8\right]\)

d = dict((v,i) for i, v in enumerate(BFSVertexList))
print(d)

{0: 0, 1: 1, 4: 2, 5: 3, 2: 4, 6: 5, 3: 6, 9: 7, 7: 8, 8: 9}

P2 = P.copy()
P2.relabel(d)
P2 = add_edge_monomials(P2)
P2.show(figsize=6,edge_labels=True)

T2=BFSTree.copy()
T2.relabel(d)
T2 = add_edge_monomials(T2,short_name=True)
T2.show(figsize=6,edge_labels=True)