You are Here: Home

# Graph Theory vs Normal diagrams Tweet

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
Ask me ANYTHING - Andrew O'Neill - Buzzcocks comedian, amateur occultist, vegan... 22-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
Sign in to Reply
1. Graph Theory vs Normal diagrams
I'm a bit confused with 'Graph Theory' and 'normal diagrams' that have edges and nodes; are the latter also a part of Graph Theory? Do they differ in any sense?

Any kind of help would be very appreciated.
2. Re: Graph Theory vs Normal diagrams
You're more likely to get a response if you post in the maths academic help forum.
3. Re: Graph Theory vs Normal diagrams
(Original post by tommm)
You're more likely to get a response if you post in the maths academic help forum.
Thanks

*Hope the mods see this : (
4. Re: Graph Theory vs Normal diagrams
(Original post by kka25)
Thanks

*Hope the mods see this : (
The report button is there to make sure exactly that happens

Moved it now
5. Re: Graph Theory vs Normal diagrams
(Original post by Potally_Tissed)
The report button is there to make sure exactly that happens

Moved it now
Thanks! Didn't know that
6. Re: Graph Theory vs Normal diagrams
Can you elaborate on what a "normal diagram" is (or an online reference)? I could guess, but as Google's not showing anything definitive, I can't be certain.
Last edited by ghostwalker; 18-07-2012 at 19:05.
7. Re: Graph Theory vs Normal diagrams
(Original post by ghostwalker)
Can you elaborate on what a "normal diagram" is? I could guess, but as Google's not showing anything definitive, I can't be certain.
Thank your very much for replying!

Alright, what I meant by "normal diagram" was diagrams such as hierarchical diagram (those that you see in offices and companies) or organizational charts/diagrams, generic images that have symbols and lines connecting to them, etc.

Would those be a part of Graph Theory as well?

Via definition, a graph consists of a set of vertices, a set of edges and a relationship that associates the edge to the vertices, which is called endpoints.

So, that's a graph, which is a part of the bigger picture of Graph theory. But would it be sufficed to say that any diagrams that have generic 'symbols', and that 'symbols' have a line that defines a relationship between those 'symbols', a part of graph in Graph theory?

Hope you understand this lol : (
8. Re: Graph Theory vs Normal diagrams
I think I follow you.

Any diagram that conforms to the definition of a graph, could be considered as a graph in the graph theoretic sense.

But not every diagram conforms to that definition:

For example, some of the hierarchical diagrams used in structured programming connect an instance on one level with multiple instances on another level. Here the "edge" can have more than 2 endpoints (one upper and multiple lower). As such it is not a graph in the graph theoretic sense. See diagram, top right, on http://en.wikipedia.org/wiki/Jackson...ed_programming, the way the bottom two blocks connect to the upper.

Most electrical circuit diagram will also break the rules. Top right of http://en.wikipedia.org/wiki/Circuit_diagram for example.

Now, although, as they stand they don't conform to the rules, they could possibly be rejigged to do so.
E.g. if an "edge" in a normal graph has three end points then it could be represented by three edges, each connecting two of the endpoints of our original "edge". If this were a hierarchy though, this is going to colour the interpretation, as we now have edges connecting items on the same level. Perhaps a different implementation, using a directed graph would be suitable.

As you can see it's starting to get a bit grey.
Last edited by ghostwalker; 18-07-2012 at 19:39.
9. Re: Graph Theory vs Normal diagrams
(Original post by kka25)
Thank your very much for replying!

Alright, what I meant by "normal diagram" was diagrams such as hierarchical diagram (those that you see in offices and companies) or organizational charts/diagrams, generic images that have symbols and lines connecting to them, etc.

Would those be a part of Graph Theory as well?
Not really. Don't let the name "graph" distract you: graph theory is the study of an abstract algebraic structure (namely, a graph) which can be represented by some dots and lines, but really it's just a pair of sets where (i.e. is a set of (unordered) pairs of elements of ).

(Original post by kka25)
So, that's a graph, which is a part of the bigger picture of Graph theory. But would it be sufficed to say that any diagrams that have generic 'symbols', and that 'symbols' have a line that defines a relationship between those 'symbols', a part of graph in Graph theory?
In the sense that any diagram which consists of 'nodes and edges' can be abstracted to graph theory yes; but for applications of the nature of those of the graphs you're referring to, graph theory isn't an awful lot of use. Because graph theory studies those properties of a graph that hold "up to isomorphism", it is only the graph structure of a graph that is detected by graph theory, so if your nodes have different 'meanings' then that meaning is lost as soon as you consider it graph-theoretically. (Intuitively: graph theory doesn't distinguish between a map which joins cities together with roads, and the 'map' you get by rubbing out the names of the cities and roads and then moving the cities and roads around.)
Last edited by nuodai; 18-07-2012 at 19:36.
10. Re: Graph Theory vs Normal diagrams
Thank you : D

I'll reply to you after I read and understand the links you gave!
11. Re: Graph Theory vs Normal diagrams
(Original post by kka25)
I'll reply to you after I read and understand the links you gave!
Don't expect to understand my link. All you need to know is that a graph isomorphism is a relationship between two graphs that asserts that they are "the same" (from the point of view of graph theory), in the sense that they can be represented by the same picture of dots and lines. So for instance the graphs and and and are all "isomorphic" to each other, but not to (where the lines are meant to be edges and the other things are vertices). The former can be represented abstractly by and the last by .

(And of this, all you need to understand is the bit in italics.)
Last edited by nuodai; 18-07-2012 at 20:04.
12. Re: Graph Theory vs Normal diagrams
(Original post by nuodai)
Don't expect to understand my link. All you need to know is that a graph isomorphism is a relationship between two graphs that asserts that they are "the same" (from the point of view of graph theory), in the sense that they can be represented by the same picture of dots and lines. So for instance the graphs and and and are all "isomorphic" to each other, but not to (where the lines are meant to be edges and the other things are vertices). The former can be represented abstractly by and the last by .

(And of this, all you need to understand is the bit in italics.)
I haven't read fully on Isomorphisms, and I'll get back to the original question, but could you tell me the benefit of identifying that two or more structures are isomorphic to each other? There must be some motivation to identify these isomorphic graphs.

At the moment, I could infer that if two distinct graphs are Isomorphic, then they share a common mathematical structure (characteristics? is that the term for it?), but I don't know in what practical sense does this matter or is it important to know.
13. Re: Graph Theory vs Normal diagrams
(Original post by kka25)
I haven't read fully on Isomorphisms, and I'll get back to the original question, but could you tell me the benefit of identifying that two or more structures are isomorphic to each other? There must be some motivation to identify these isomorphic graphs.
Graph theory is a field within abstract algebra (and combinatorics). What abstract algebra is, when it comes down to it, is a study of the ways in which different objects are "the same". When you forget the details and look only at the structure, you can learn a lot more about what you're studying. For instance, the concept of "eating" covers that of "eating oranges" and "eating apples", and the latter also covers that of "eating green apples" and "eating red apples", and the latter of these also covers that of "eating this red apple" and "eating that red apple", and so on. But if you know how to "eat", ignoring exactly what it is that you're eating, then you know how to do all of the above. It's the same sort of concept in graph theory (and group theory, field theory, ring theory, module theory, vector space theory, etc... and especially category theory): you forget what the graph represents (indeed, it needn't represent anything) and instead study the deeper structure.

(Original post by kka25)
At the moment, I could infer that if two distinct graphs are Isomorphic, then they share a common mathematical structure (characteristics? is that the term for it?), but I don't know in what practical sense does this matter or is it important to know.
It's not really important to know unless you actually want to study it. I think this has gone into a lot more detail than it needed to. A sufficient answer to your original question is "in graph theory, graphs don't represent data".
Last edited by nuodai; 18-07-2012 at 21:09.
14. Re: Graph Theory vs Normal diagrams
(Original post by nuodai)
Graph theory is a field within abstract algebra (and combinatorics). What abstract algebra is, when it comes down to it, is a study of the ways in which different objects are "the same". When you forget the details and look only at the structure, you can learn a lot more about what you're studying. For instance, the concept of "eating" covers that of "eating oranges" and "eating apples", and the latter also covers that of "eating green apples" and "eating red apples", and the latter of these also covers that of "eating this red apple" and "eating that red apple", and so on. But if you know how to "eat", ignoring exactly what it is that you're eating, then you know how to do all of the above. It's the same sort of concept in graph theory (and group theory, field theory, ring theory, module theory, vector space theory, etc... and especially category theory): you forget what the graph represents (indeed, it needn't represent anything) and instead study the deeper structure.

It's not really important to know unless you actually want to study it. I think this has gone into a lot more detail than it needed to. A sufficient answer to your original question is "in graph theory, graphs don't represent data".
The first paragraph is rather interesting; do you have any books/articles that you like regarding Graph Theory?

Aw, for the second paragraph, although I *think* I know what you mean, but it's still a bit fragmented for me : (

*BTW, I do want to study them. It's something of a research question for me; "How can isomorphic structure benefit this <some problem>"

Thanks loads.
15. Re: Graph Theory vs Normal diagrams
(Original post by kka25)
The first paragraph is rather interesting; do you have any books/articles that you like regarding Graph Theory?
'Fraid not, the subject makes me want to tear out my eyeballs, but there might be others on here who can help you.

(Original post by kka25)
Aw, for the second paragraph, although I *think* I know what you mean, but it's still a bit fragmented for me : (

*BTW, I do want to study them. It's something of a research question for me; "How can isomorphic structure benefit this <some problem>"
Perhaps an unsatisfactory answer, but an answer nonetheless, is that you need to have a more thorough grounding in algebra to be able to understand answers to these questions. (Though as it is, the question doesn't make much sense anyway )
16. Re: Graph Theory vs Normal diagrams
(Original post by nuodai)
'Fraid not, the subject makes me want to tear out my eyeballs, but there might be others on here who can help you.
Thanks loads : )

Perhaps an unsatisfactory answer, but an answer nonetheless, is that you need to have a more thorough grounding in algebra to be able to understand answers to these questions. (Though as it is, the question doesn't make much sense anyway )
Thanks for telling me this; I will check all the necessary things that are needed to appreciate the topic.

Regarding back to "in graph theory, graphs don't represent data"; can I say that Graph Theory studies more on the structure of the data, rather than the data itself? (But then again, some other Mathematician or Logician would say; "Wouldn't that be the same thing?" lol)
17. Re: Graph Theory vs Normal diagrams
(Original post by kka25)
Regarding back to "in graph theory, graphs don't represent data"; can I say that Graph Theory studies more on the structure of the data, rather than the data itself?
In some distant sense yes, but not really: data doesn't really come into it.
Sign in to Reply
Share this discussion:
Article updates
Moderators

We have a brilliant team of more than 60 volunteers looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is moderated by:
Reputation gems:
The Reputation gems seen here indicate how well reputed the user is, red gem indicate negative reputation and green indicates a good rep.
Post rating score:
These scores show if a post has been positively or negatively rated by our members.