general.hpp File Reference

Plans regarding trees (as combinatorial objects) More...

Go to the source code of this file.

Detailed Description

Plans regarding trees (as combinatorial objects)

  • The "rooted ordered trees" are the trees (rt) as in ComputerAlgebra/Trees/Lisp/Basics.mac.
  • Are there other types of "directed trees" than "oriented trees" (directed graphs without antiparallel edges, such that the underlying graph is a tree)?
    1. We have "arborescences", which are rooted oriented trees such that all edges point to the root. They are the same as rooted trees, when considered on their own, but their use is as subgraphs of digraphs.
Isomorphism testing
  • We need a poly-time test for the isomorphism of trees.
  • We need also to detect whether a graph is a pathgraph or a star.
  • This seems to belong to Graphs/Lisp/Isomorphisms/Trees.mac.
  • Or should we place it in this module?
  • And the automorphism group needs to be determined.
Spanning trees
  • It seems they also belong to here, but they also belong to GraphTraversal (see ComputerAlgebra/Graphs/Lisp/plans/general.hpp)?
  • Likely in GraphTraversal we should have the special algorithms obtained by this approach, while other algorithms and other questions are handled in Trees/SpanningTrees.

Definition in file general.hpp.