6 ms·

Tree's are subsets of DAGs — A DAG where each node has a single parent except for a specific root element which has none.

zmgsabst 2y ago
Technically a tree doesn’t need to be directed. A tree is (also) any loop-free graph.
- cperciva 2y ago
  A forest is an acyclic graph. A tree is a connected forest.
  - holden_nelson 2y ago
    Exactly one path between any two nodes is how I best visualize it.
    - hughesjj 2y ago
      You gotta be careful -- a path does not exist between two leaf nodes, unless your edges are non-directional, in which case you're right. Oh and restrict it to 'only visit each node once' given undirected. Sorry my inner edge case fairy beckoned.
      - zmgsabst 2y ago
        Visiting a node twice implies a loop, which implies two paths between your original nodes. Let’s say we want to get from A to B, but we visit Y twice. That means there’s a segment of A~B that is Y~Y (a loop). However, since we’re talking about undirected edges, we can reverse that segment. Then both our original A~B and the A~B with Y~Y reversed are paths from A to B. So if there’s a single path from A to B, there cannot be a Y we visit twice along that path. (Please don’t take this as criticism; my pedantic nature got the better of me.)
        hughesjj 2y ago
        Yes, but in an UndirectedGraph you can do loops easy peasy. A->b->a->b etc. if you have a tree with a parent node, then the tree (A{children:[b], parent: null}, B{children:[], parent: A}) still may allow for this behavior (graph representation unions parent and children since a parent in tree parlence is basically 'incoming-edges' in graph parlence while children is 'outgoing-edges') I was trying to find terminology for something Like 'all possible paths between these two nodes contain exactly one Hamiltonian sub-path' but I think that's a bit of a circular definition All that said I'm running off 3 hours of sleep and about to recoup so that probably explains my non constructive comments here
    - shrimp_emoji 2y ago
      A forest is where all nodes are connected by at most one path. 0 or 1. And a single tree is a forest. And a single node is a tree.
- contingencies 2y ago
  I think that I shall never see; A graph more lovely than a tree. A tree whose crucial property; Is loop-free connectivity. - Radia Perlman, inventor of spanning tree ... via https://github.com/globalcitizen/taoup https://github.com/globalcitizen/taoup
- jraph 2y ago
  any loop-free graph which is connected (a 2 unlinked dot graph would be loop-free, but wouldn't be a tree) (to complement cperciva's answer with a counter example)
Someone 2y ago
> where each node has a single parent except for a specific root element which has none. Slight nitpick: in mathematics, a tree need not have a root. https://mathworld.wolfram.com/FreeTree.html https://mathworld.wolfram.com/FreeTree.html: “a normal tree with no node singled out for special treatment” https://mathworld.wolfram.com/RootedTree.html https://mathworld.wolfram.com/RootedTree.html: “A rooted tree is a tree in which a special ("labeled") node is singled out. This node is called the "root" or (less commonly) "eve" of the tree. Rooted trees are equivalent to oriented trees (Knuth 1997, pp. 385-399). A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree.”
- kjeetgill 2y ago
  Huh, TIL - though > A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree. I wonder if that was once the case but no longer is. I'm learning I think of trees mostly through the lens of data structures and not graph theory and I imagine more people do than not.

zmgsabst 2y ago

Technically a tree doesn’t need to be directed. A tree is (also) any loop-free graph.

cperciva 2y ago
A forest is an acyclic graph. A tree is a connected forest.
- holden_nelson 2y ago
  Exactly one path between any two nodes is how I best visualize it.
  - hughesjj 2y ago
    You gotta be careful -- a path does not exist between two leaf nodes, unless your edges are non-directional, in which case you're right. Oh and restrict it to 'only visit each node once' given undirected. Sorry my inner edge case fairy beckoned.
    - zmgsabst 2y ago
      Visiting a node twice implies a loop, which implies two paths between your original nodes. Let’s say we want to get from A to B, but we visit Y twice. That means there’s a segment of A~B that is Y~Y (a loop). However, since we’re talking about undirected edges, we can reverse that segment. Then both our original A~B and the A~B with Y~Y reversed are paths from A to B. So if there’s a single path from A to B, there cannot be a Y we visit twice along that path. (Please don’t take this as criticism; my pedantic nature got the better of me.)
      - hughesjj 2y ago
        Yes, but in an UndirectedGraph you can do loops easy peasy. A->b->a->b etc. if you have a tree with a parent node, then the tree (A{children:[b], parent: null}, B{children:[], parent: A}) still may allow for this behavior (graph representation unions parent and children since a parent in tree parlence is basically 'incoming-edges' in graph parlence while children is 'outgoing-edges') I was trying to find terminology for something Like 'all possible paths between these two nodes contain exactly one Hamiltonian sub-path' but I think that's a bit of a circular definition All that said I'm running off 3 hours of sleep and about to recoup so that probably explains my non constructive comments here
  - shrimp_emoji 2y ago
    A forest is where all nodes are connected by at most one path. 0 or 1. And a single tree is a forest. And a single node is a tree.
contingencies 2y ago
I think that I shall never see; A graph more lovely than a tree. A tree whose crucial property; Is loop-free connectivity. - Radia Perlman, inventor of spanning tree ... via https://github.com/globalcitizen/taoup https://github.com/globalcitizen/taoup
jraph 2y ago
any loop-free graph which is connected (a 2 unlinked dot graph would be loop-free, but wouldn't be a tree) (to complement cperciva's answer with a counter example)

Someone 2y ago

> where each node has a single parent except for a specific root element which has none. Slight nitpick: in mathematics, a tree need not have a root. https://mathworld.wolfram.com/FreeTree.html https://mathworld.wolfram.com/FreeTree.html: “a normal tree with no node singled out for special treatment” https://mathworld.wolfram.com/RootedTree.html https://mathworld.wolfram.com/RootedTree.html: “A rooted tree is a tree in which a special ("labeled") node is singled out. This node is called the "root" or (less commonly) "eve" of the tree. Rooted trees are equivalent to oriented trees (Knuth 1997, pp. 385-399). A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree.”

kjeetgill 2y ago
Huh, TIL - though > A tree which is not rooted is sometimes called a free tree, although the unqualified term "tree" generally refers to a free tree. I wonder if that was once the case but no longer is. I'm learning I think of trees mostly through the lens of data structures and not graph theory and I imagine more people do than not.