2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Rick Decker Jul 8 '15 at 13:39
  • $\begingroup$ I believe that this is common usage. $\endgroup$ – Yuval Filmus Jul 8 '15 at 14:11
  • $\begingroup$ 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$). $\endgroup$ – Klaus Draeger Jul 8 '15 at 17:13
  • $\begingroup$ I'd use "shape". $\endgroup$ – Raphael Jul 9 '15 at 8:43
  • $\begingroup$ 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? $\endgroup$ – Juho Jul 9 '15 at 18:30
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How can we be assured that two trees are not isomorphic ? Maybe the trees I have are isomorphic, while having a different shape ? $\endgroup$ – user7060 Jul 10 '15 at 9:14
  • $\begingroup$ @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. $\endgroup$ – D.W. Jul 10 '15 at 16:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.