Ask Your Question

Revision history [back]

You can use graphs.trees(n) to enumerate undirected trees of order n. 

sage: for g in graphs.trees(1):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 1, m = 0, E = []
sage: for g in graphs.trees(2):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 2, m = 1, E = [(0, 1)]
sage: for g in graphs.trees(3):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 3, m = 2, E = [(0, 1), (0, 2)]
sage: for g in graphs.trees(4):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
sage: for g in graphs.trees(5):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (3, 4)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (1, 2)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (0, 4)]

Then, for a given tree g you can use digraphs.nauty_directg(g, "-o") to enumerate its orientations. 

sage: for g in graphs.trees(3):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....:     for h in digraphs.nauty_directg(g, "-o"):
....:         print(f"\t{h.edges(labels=False)}")
....: 
n = 3, m = 2, E = [(0, 1), (0, 2)]
    [(0, 1), (0, 2)]
    [(0, 1), (2, 0)]
    [(1, 0), (2, 0)]
sage: for g in graphs.trees(4):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....:     for h in digraphs.nauty_directg(g, "-o"):
....:         print(f"\t{h.edges(labels=False)}")
....: 
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
    [(0, 1), (0, 3), (1, 2)]
    [(0, 1), (0, 3), (2, 1)]
    [(0, 1), (1, 2), (3, 0)]
    [(0, 1), (2, 1), (3, 0)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
    [(0, 1), (0, 2), (0, 3)]
    [(0, 1), (0, 2), (3, 0)]
    [(0, 1), (2, 0), (3, 0)]
    [(1, 0), (2, 0), (3, 0)]

Finally, you can combine that as follows:

sage: for g in digraphs.nauty_directg(graphs.trees(1), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 1, m = 0, E = []
sage: for g in digraphs.nauty_directg(graphs.trees(2), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 2, m = 1, E = [(0, 1)]
sage: for g in digraphs.nauty_directg(graphs.trees(3), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 3, m = 2, E = [(0, 1), (0, 2)]
n = 3, m = 2, E = [(0, 1), (2, 0)]
n = 3, m = 2, E = [(1, 0), (2, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(4), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
n = 4, m = 3, E = [(0, 1), (0, 3), (2, 1)]
n = 4, m = 3, E = [(0, 1), (1, 2), (3, 0)]
n = 4, m = 3, E = [(0, 1), (2, 1), (3, 0)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
n = 4, m = 3, E = [(0, 1), (0, 2), (3, 0)]
n = 4, m = 3, E = [(0, 1), (2, 0), (3, 0)]
n = 4, m = 3, E = [(1, 0), (2, 0), (3, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(5), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (3, 4)]
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (4, 3)]
n = 5, m = 4, E = [(0, 1), (0, 3), (2, 1), (4, 3)]
n = 5, m = 4, E = [(0, 1), (1, 2), (3, 0), (3, 4)]
n = 5, m = 4, E = [(0, 1), (1, 2), (3, 0), (4, 3)]
n = 5, m = 4, E = [(0, 1), (2, 1), (3, 0), (3, 4)]
n = 5, m = 4, E = [(0, 1), (2, 1), (3, 0), (4, 3)]
n = 5, m = 4, E = [(1, 0), (1, 2), (3, 0), (3, 4)]
n = 5, m = 4, E = [(1, 0), (1, 2), (3, 0), (4, 3)]
n = 5, m = 4, E = [(1, 0), (2, 1), (3, 0), (4, 3)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (1, 2)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (2, 1)]
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 3), (2, 1), (4, 0)]
n = 5, m = 4, E = [(0, 1), (1, 2), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (2, 1), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 3), (0, 4), (1, 0), (1, 2)]
n = 5, m = 4, E = [(0, 3), (0, 4), (1, 0), (2, 1)]
n = 5, m = 4, E = [(0, 3), (1, 0), (1, 2), (4, 0)]
n = 5, m = 4, E = [(0, 3), (1, 0), (2, 1), (4, 0)]
n = 5, m = 4, E = [(1, 0), (1, 2), (3, 0), (4, 0)]
n = 5, m = 4, E = [(1, 0), (2, 1), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (0, 4)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 2), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (2, 0), (3, 0), (4, 0)]
n = 5, m = 4, E = [(1, 0), (2, 0), (3, 0), (4, 0)]

You can use graphs.trees(n) to enumerate undirected trees of order n. 

sage: for g in graphs.trees(1):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 1, m = 0, E = []
sage: for g in graphs.trees(2):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 2, m = 1, E = [(0, 1)]
sage: for g in graphs.trees(3):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 3, m = 2, E = [(0, 1), (0, 2)]
sage: for g in graphs.trees(4):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
sage: for g in graphs.trees(5):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (3, 4)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (1, 2)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (0, 4)]

Then, for a given tree g you can use digraphs.nauty_directg(g, "-o") to enumerate its orientations. 

sage: for g in graphs.trees(3):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....:     for h in digraphs.nauty_directg(g, "-o"):
....:         print(f"\t{h.edges(labels=False)}")
....: 
n = 3, m = 2, E = [(0, 1), (0, 2)]
    [(0, 1), (0, 2)]
    [(0, 1), (2, 0)]
    [(1, 0), (2, 0)]
sage: for g in graphs.trees(4):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....:     for h in digraphs.nauty_directg(g, "-o"):
....:         print(f"\t{h.edges(labels=False)}")
....: 
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
    [(0, 1), (0, 3), (1, 2)]
    [(0, 1), (0, 3), (2, 1)]
    [(0, 1), (1, 2), (3, 0)]
    [(0, 1), (2, 1), (3, 0)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
    [(0, 1), (0, 2), (0, 3)]
    [(0, 1), (0, 2), (3, 0)]
    [(0, 1), (2, 0), (3, 0)]
    [(1, 0), (2, 0), (3, 0)]

Finally, you can combine that as follows:

sage: for g in digraphs.nauty_directg(graphs.trees(1), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 1, m = 0, E = print(g.edges(labels=False))
....: 
[]
sage: for g in digraphs.nauty_directg(graphs.trees(2), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 2, m = 1, E = print(g.edges(labels=False))
....: 
[(0, 1)]
sage: for g in digraphs.nauty_directg(graphs.trees(3), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 3, m = 2, E = [(0, 1), (0, 2)]
n = 3, m = 2, E = [(0, 1), (2, 0)]
n = 3, m = 2, E = print(g.edges(labels=False))
....: 
[(0, 1), (0, 2)]
[(0, 1), (2, 0)]
[(1, 0), (2, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(4), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
n = 4, m = 3, E = print(g.edges(labels=False))
....: 
[(0, 1), (0, 3), (1, 2)]
[(0, 1), (0, 3), (2, 1)]
n = 4, m = 3, E = [(0, 1), (1, 2), (3, 0)]
n = 4, m = 3, E = [(0, 1), (2, 1), (3, 0)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
n = 4, m = 3, E = [(0, 1), (0, 2), (3, 0)]
n = 4, m = 3, E = [(0, 1), (2, 0), (3, 0)]
n = 4, m = 3, E = [(0, 1), (1, 2), (3, 0)]
[(0, 1), (2, 1), (3, 0)]
[(0, 1), (0, 2), (0, 3)]
[(0, 1), (0, 2), (3, 0)]
[(0, 1), (2, 0), (3, 0)]
[(1, 0), (2, 0), (3, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(5), "-o"):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
n = 5, m = 4, E = print(g.edges(labels=False))
....: 
[(0, 1), (0, 3), (1, 2), (3, 4)]
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (4, 3)]
n = 5, m = 4, E = [(0, 1), (0, 3), (2, 1), (4, 3)]
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (4, 3)]
[(0, 1), (0, 3), (2, 1), (4, 3)]
[(0, 1), (1, 2), (3, 0), (3, 4)]
n = 5, m = 4, E = [(0, 1), (1, 2), (3, 0), (4, 3)]
n = 5, m = 4, E = [(0, 1), (1, 2), (3, 0), (4, 3)]
[(0, 1), (2, 1), (3, 0), (3, 4)]
n = 5, m = 4, E = [(0, 1), (2, 1), (3, 0), (4, 3)]
n = 5, m = 4, E = [(0, 1), (2, 1), (3, 0), (4, 3)]
[(1, 0), (1, 2), (3, 0), (3, 4)]
n = 5, m = 4, E = [(1, 0), (1, 2), (3, 0), (4, 3)]
n = 5, m = 4, E = [(1, 0), (2, 1), (3, 0), (4, 3)]
n = 5, m = 4, E = [(1, 0), (1, 2), (3, 0), (4, 3)]
[(1, 0), (2, 1), (3, 0), (4, 3)]
[(0, 1), (0, 3), (0, 4), (1, 2)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (2, 1)]
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 3), (2, 1), (4, 0)]
n = 5, m = 4, E = [(0, 1), (1, 2), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (2, 1), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (4, 0)]
[(0, 1), (0, 3), (2, 1), (4, 0)]
[(0, 1), (1, 2), (3, 0), (4, 0)]
[(0, 1), (2, 1), (3, 0), (4, 0)]
[(0, 3), (0, 4), (1, 0), (1, 2)]
n = 5, m = 4, E = [(0, 3), (0, 4), (1, 0), (2, 1)]
n = 5, m = 4, E = [(0, 3), (1, 0), (1, 2), (4, 0)]
n = 5, m = 4, E = [(0, 3), (1, 0), (2, 1), (4, 0)]
n = 5, m = 4, E = [(1, 0), (1, 2), (3, 0), (4, 0)]
n = 5, m = 4, E = [(1, 0), (2, 1), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 3), (1, 0), (1, 2), (4, 0)]
[(0, 3), (1, 0), (2, 1), (4, 0)]
[(1, 0), (1, 2), (3, 0), (4, 0)]
[(1, 0), (2, 1), (3, 0), (4, 0)]
[(0, 1), (0, 2), (0, 3), (0, 4)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 2), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (2, 0), (3, 0), (4, 0)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (4, 0)]
[(0, 1), (0, 2), (3, 0), (4, 0)]
[(0, 1), (2, 0), (3, 0), (4, 0)]
[(1, 0), (2, 0), (3, 0), (4, 0)]

You can use graphs.trees(n) to enumerate undirected trees of order n. 

sage: for g in graphs.trees(1):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 1, m = 0, E = []
sage: for g in graphs.trees(2):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 2, m = 1, E = [(0, 1)]
sage: for g in graphs.trees(3):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 3, m = 2, E = [(0, 1), (0, 2)]
sage: for g in graphs.trees(4):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
sage: for g in graphs.trees(5):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....: 
n = 5, m = 4, E = [(0, 1), (0, 3), (1, 2), (3, 4)]
n = 5, m = 4, E = [(0, 1), (0, 3), (0, 4), (1, 2)]
n = 5, m = 4, E = [(0, 1), (0, 2), (0, 3), (0, 4)]

Then, for a given tree g you can use digraphs.nauty_directg(g, "-o") to enumerate its orientations. 

sage: for g in graphs.trees(3):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....:     for h in digraphs.nauty_directg(g, "-o"):
....:         print(f"\t{h.edges(labels=False)}")
....: 
n = 3, m = 2, E = [(0, 1), (0, 2)]
    [(0, 1), (0, 2)]
    [(0, 1), (2, 0)]
    [(1, 0), (2, 0)]
sage: for g in graphs.trees(4):
....:     print(f"n = {g.order()}, m = {g.size()}, E = {g.edges(labels=False)}")
....:     for h in digraphs.nauty_directg(g, "-o"):
....:         print(f"\t{h.edges(labels=False)}")
....: 
n = 4, m = 3, E = [(0, 1), (0, 3), (1, 2)]
    [(0, 1), (0, 3), (1, 2)]
    [(0, 1), (0, 3), (2, 1)]
    [(0, 1), (1, 2), (3, 0)]
    [(0, 1), (2, 1), (3, 0)]
n = 4, m = 3, E = [(0, 1), (0, 2), (0, 3)]
    [(0, 1), (0, 2), (0, 3)]
    [(0, 1), (0, 2), (3, 0)]
    [(0, 1), (2, 0), (3, 0)]
    [(1, 0), (2, 0), (3, 0)]

Finally, you can combine that as follows:

sage: for g in digraphs.nauty_directg(graphs.trees(1), "-o"):
....:     print(g.edges(labels=False))
....: 
[]
sage: for g in digraphs.nauty_directg(graphs.trees(2), "-o"):
....:     print(g.edges(labels=False))
....: 
[(0, 1)]
sage: for g in digraphs.nauty_directg(graphs.trees(3), "-o"):
....:     print(g.edges(labels=False))
....: 
[(0, 1), (0, 2)]
[(0, 1), (2, 0)]
[(1, 0), (2, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(4), "-o"):
....:     print(g.edges(labels=False))
....: 
[(0, 1), (0, 3), (1, 2)]
[(0, 1), (0, 3), (2, 1)]
[(0, 1), (1, 2), (3, 0)]
[(0, 1), (2, 1), (3, 0)]
[(0, 1), (0, 2), (0, 3)]
[(0, 1), (0, 2), (3, 0)]
[(0, 1), (2, 0), (3, 0)]
[(1, 0), (2, 0), (3, 0)]
sage: for g in digraphs.nauty_directg(graphs.trees(5), "-o"):
....:     print(g.edges(labels=False))
....: 
[(0, 1), (0, 3), (1, 2), (3, 4)]
[(0, 1), (0, 3), (1, 2), (4, 3)]
[(0, 1), (0, 3), (2, 1), (4, 3)]
[(0, 1), (1, 2), (3, 0), (3, 4)]
[(0, 1), (1, 2), (3, 0), (4, 3)]
[(0, 1), (2, 1), (3, 0), (3, 4)]
[(0, 1), (2, 1), (3, 0), (4, 3)]
[(1, 0), (1, 2), (3, 0), (3, 4)]
[(1, 0), (1, 2), (3, 0), (4, 3)]
[(1, 0), (2, 1), (3, 0), (4, 3)]
[(0, 1), (0, 3), (0, 4), (1, 2)]
[(0, 1), (0, 3), (0, 4), (2, 1)]
[(0, 1), (0, 3), (1, 2), (4, 0)]
[(0, 1), (0, 3), (2, 1), (4, 0)]
[(0, 1), (1, 2), (3, 0), (4, 0)]
[(0, 1), (2, 1), (3, 0), (4, 0)]
[(0, 3), (0, 4), (1, 0), (1, 2)]
[(0, 3), (0, 4), (1, 0), (2, 1)]
[(0, 3), (1, 0), (1, 2), (4, 0)]
[(0, 3), (1, 0), (2, 1), (4, 0)]
[(1, 0), (1, 2), (3, 0), (4, 0)]
[(1, 0), (2, 1), (3, 0), (4, 0)]
[(0, 1), (0, 2), (0, 3), (0, 4)]
[(0, 1), (0, 2), (0, 3), (4, 0)]
[(0, 1), (0, 2), (3, 0), (4, 0)]
[(0, 1), (2, 0), (3, 0), (4, 0)]
[(1, 0), (2, 0), (3, 0), (4, 0)]
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
about | faq | help | privacy policy | terms of service
Powered by Askbot version 0.7.59