3 ms·
A / \ B C / \ / \ D E F G This is clearly a tree, but doesn't B have 2 paths through it? A->B->D and A->B->E.
by jstanley 5y ago
A
/ \
B C
/ \ / \
D E F G
This is clearly a tree, but doesn't B have 2 paths through it? A->B->D and A->B->E.
- gmfawcett 5y agoYou're right. The correct definition is that any two vertices are connected by (i.e. are the endpoints of) exactly one path. Fun fact -- since graph-theory trees are undirected by definition, an inheritance graph is more properly called an arborescence (for single inheritance). For multiple inheritance it's a DAG (with diamond-pattern) or a directed tree (without).
- jholman 5y ago> any two vertices are connected by (i.e. are the endpoints of) exactly one path No. You just described a connected acyclic graph, not a tree. In addition to being connected and acyclic, a tree must also have a root, and is thus implicitly directed.