# Tolerated use of the term topology

In the field of data structures (and maybe in graph theory), can we use the term topology to speak about the shape of a tree? For instance, consider the two following trees :

1) The first one: Node $a$ is parent of $b$ and $c$. Node $e$ is parent of $a$ and $d$

2) the second one: Node $a$ is parent of nodes $b$, $c$ and $d$.

Can we say that their topology are different, in the sense that the set of relations parents/children are different?

• It's a use of a technical term in a less than formal way, but only a serious pedant would take you to task if you said that two graph-like structures had different topologies. I've seen the term frequently (and, IMO, acceptably) to describe network structures, for example. – Rick Decker Jul 8 '15 at 13:39
• I believe that this is common usage. – Yuval Filmus Jul 8 '15 at 14:11
• If you want, you can actually relate this informal usage to the mathematical notion of topology on finite sets, e.g. by considering the Alexandrov topology (en.wikipedia.org/wiki/Alexandrov_topology) on your trees (for example, your second example would have open sets $\emptyset$ as well as all subsets containing $a$). – Klaus Draeger Jul 8 '15 at 17:13
• I'd use "shape". – Raphael Jul 9 '15 at 8:43
• Why do you insist on using "topology" there though? Couldn't you just say they are different trees? Or that they are (somehow) structurally different? – Juho Jul 9 '15 at 18:30

## 1 Answer

Yes, I suppose you could, though it might be viewed as a somewhat informal usage of the term "topology". "Shape" would probably be a better word, as @Raphael suggests.

A more precise way would be to say that these two trees are not isomorphic.

Background: Two graphs $G,G'$ are considered isomorphic if there exists a map $f:V \to V'$ that is a graph isomorphism. Since any tree can be viewed as a graph, you can consider two trees to be isomorphic if they are isomorphic as graphs. One can also define a natural notion of a tree isomorphism directly; this happens to be equivalent to the notion of a graph isomorphism for unrooted trees, but is slightly different (and more appropriate to use) for rooted trees. You can read more about isomorphisms in standard sources.

• How can we be assured that two trees are not isomorphic ? Maybe the trees I have are isomorphic, while having a different shape ? – user7060 Jul 10 '15 at 9:14
• @user7060, well, you write a mathematical proof that they are not isomorphic. That proof refers back to the definition of isomorphism. The appropriate proof techniques will differ. Sometimes it's as simple as saying "G has a node of degree 7, G' doesn't", sometimes it can be much more complex to prove it -- but in any case, the way you can be assured is to prove the statement. – D.W. Jul 10 '15 at 16:50