I know that two graphs that have the same shape are isomorphic. Such as these two:


enter image description here


enter image description here

But how do I say that the contents are different?

Furthermore, how does mathematic notation even refer to the contents of graphs? From the introductory lectures I've seen so far on graph theory I see no place in E(G) and V(G) for edge labels and vertex values/contents.

I'm looking for a sentence like: Graph1 and Graph2 are isomorphic but hetro-contental. But obviously using real technical terms...


For my use-case I need some real words and not phrases. I'm writing about the difference between an analog computer, which you re-wire, and a digital computer which you don't. So, for example, the graph of the traces on all Raspberri-pi's are all isomorphic, but the Pi is re-programmed to create a large number of different behaviors, wher-as this modular synth is programmed by changing the morphism(morphology) of the signal graph.

Photo credit Nina Richards Copyright 2011 CC By 3.0 Photo credit Nina Richards Copyright 2011 CC By 3.0

Do I need to come up with my own vocabulary to discuss this, or does vocabulary already exist? I'm going to be using these words alot in the document that I'm writing. If these words don't yet exist, can you give me any tips on what I should use as my neologism? I'm thinking of talking about systems with:

  • Static morphology vs dynamic morphology

and systems with

  • Static node state vs dynamic node state

Or something like that.

That the modular synth has both dynamic morphology and node state (it is programmed both by re-wiring and turning the knobs on the modules). Where-as the raspberry pi has static morphology and dynamic node state. The animal nervous system is yet another case, it has static node-state(the individual neurons don't store information) but has dynamic morphology (memories and skills are stored by changing how the neurons are connected together.

  • 2
    $\begingroup$ I would call them isomorphic "up to content". $\endgroup$ Dec 12 '16 at 14:52
  • $\begingroup$ You may just say that graphs $G$ and $H$ are isomorphic while different. Equality between graphs is achieved if $V(G) = V(H)$ and $E(G)=E(H)$. Isomorphism relates different graphs that have the same "shape". No new vocabulary needed. $\endgroup$
    – laurent
    Dec 12 '16 at 14:53
  • $\begingroup$ You could say that they are "graph theoretically isomorphic". $\endgroup$
    – Lee Mosher
    Dec 12 '16 at 14:53
  • 2
    $\begingroup$ I would usually refer to the contents as 'labels'. Then they are "isomorphic when considered as simple graphs" but they have different labellings. $\endgroup$
    – gilleain
    Dec 12 '16 at 15:00
  • $\begingroup$ @gilleain thank you for the note about 'labels'. It does seem that you are right, that the word 'labels' is used. But, as per my edit, I don' believe that the word 'labels' is very easy to understand/appropriate in my use-case. $\endgroup$
    – timthelion
    Dec 13 '16 at 11:42

Graphs, as mathematical objects, do not have any content by themselves. They are just vertices and edges, and there is nothing more to it. What people do, is they apply weights (weighted graph) or labels (labeled graph). In general they are just functions from edges or vertices, say \begin{align*} \operatorname{weight} &: E(G) \to \mathbb{N},\\ \operatorname{label} &: V(G) \to \{a, b, c\},\\ \end{align*} and of course you can have your own function, for example $\operatorname{content}: V(G) \to \mathbb{N}\times\mathbb{N}$. In that context, isomorphism usually means isomorphism of weigted graphs (or labeled graphs), that is, it has to be weigth-preserving (or label-preserving, or content-preserving, etc.).

Moreover, I think label is a good term in your case (of course, there might some even better). It can be used as follows:

We label the nodes of the graph with pairs of natural numbers that represent their content. Furthermore, for any node $v \in V$ we will refer to the first and second coordinate of the corresponding pair by $\operatorname{foo}(v)$ and $\operatorname{bar}(v)$ respectively.

To use to non-labeled-graph isomorphism you have to explicitly mention it, or make a special note at the beginning that defines a non-standard convention. A third way would to use of non-labeled version of the graph, i.e., a structure with their labels stripped off. For example, if $G_i = (V_i, E_i, \operatorname{label}_i)$ are your labeled graphs, then you can say that simple graphs $(V_i, E_i)$ are isomorphic and there are no labels there to preserve or not preserve. If you would like to use language that is a bit less technical, you could say that the shapes of these devices are the same, or isomorphic, from graph-theoretic perspective.

I hope this helps $\ddot\smile$

  • $\begingroup$ Thank you for the answer. It does seem like "label" is the word. I do wonder though, why it is, that there are multiple feilds that study graphs: graph-theory, network topology theory, network analysis, neural networking theory, and in computer science data flow models, control flow models, signal processing networks. And all of these feilds have their own words for basic and identical concepts, and it seems none of them have a vocabulary that is able to unify, or express all of the various concepts. $\endgroup$
    – timthelion
    Dec 14 '16 at 9:33
  • $\begingroup$ @timthelion That happens everywhere, and not just in science or math, only it is more evident there as it is easier to see that two things are actually the same if these are abstract concepts rather than real objects or phenomena. If I were to guess why it happens, observe that different areas have different contexts and thus their respective vocabulary might make more sense, and there is historical baggage, cruft, inertia. For example, early matching research was related to matching people to hospitals, army units, etc., and its no surprise they didn't called it resource assignment. $\endgroup$
    – dtldarek
    Dec 14 '16 at 10:03

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.