OKlibrary  0.2.1.6
Chapter02.hpp File Reference

Chapter "Trees" from [A Course in Combinatorics]. More...

Go to the source code of this file.


Detailed Description

Chapter "Trees" from [A Course in Combinatorics].

Counting, enumerating and sampling trees

See ComputerAlgebra/Graphs/Lisp/Trees/plans/Generators.hpp.

  • The Pruefer code for a given tree is given by, e.g.,
    tree2pruefercode_og([[1,2,3,4,5],[{1,2},{3,2},{2,4},{4,5}]]);
     [2,2,4]
       
    Conversely, given a pruefer code, and the vertex list, the tree can be reconstructed by
    pruefercode2tree_og([1,2,3,4,5],[2,2,4]);
     [[1,2,3,4,5],[{1,2},{2,3},{2,4},{4,5}]])
       
  • pruefercode2tree_og is the inverse of tree2pruefercode_og w.r.t. the underlying graph, while the edge-order in general is not preserved, e.g.,
    pruefercode2tree_og([1,2,3,4,5,6],tree2pruefercode_og([[1,2,3,4,5,6],[{1,2},{3,2},{4,5},{4,6},{2,4}]]));
     [[1,2,3,4,5,6],[{1,2},{2,3},{2,4},{4,5},{4,6}]]
       

Spanning trees

Connectivity

Definition in file Chapter02.hpp.