what are the applications of the isomorphic graphs?

Question

While studying data structures i was told my instructor that even i am given 3 hour/30 days/3 years to find out whether two graphs are isomorphic or not, it is very very complex and even after spending this much amount of time i will not able to figure out clearly whether the given two graphs are isomorphic or not. It is NP-complete problem.

So i got the curiosity that why i am studying it then. What could be the possible applications of such isomorphic graphs which can be solved ?

Answer 1

If your question is actually: "what are possible applications of the isomorphism problem", then check this: http://en.wikipedia.org/wiki/Graph_isomorphism_problem#Applications

Another very interesting application of the isomorphism problem is the development of algorithms for fingerprint matching http://euler.mat.ufrgs.br/~trevisan/workgraph/regina.pdf

Answer 2

For subgraph isomorphism, there are too many applications; like finding defect in texture. Texture mades of regular images, and if some pieces of given texture has another shape, it can be defect (like hole).

You can divide texture in different pieces and apply graph isomorphism on pieces (Instead of using NP-Complete problem like subgraph isomorphism). Also graph isomorphism is solvable in planar graphs (by knowing that planar graphs tree-width is at most 3 times of its diameter), and texture is planar graph, so this can be a real application in real world.

Also another sample is implicitly related problems, too many problems can be reduced to graph isomorphism (and vise versa). May be this is theoretical result, but in fact, you can find at least one usage of each problem in real world, and this usage can be extended to graph isomorphism.

And finally, I personally like pure science, another real world usage of graph isomorphism is enjoyment of people like me.

Answer 3

Bluntly put, the applications are endless...

Before I start the list, I think it will be appropriate to explain something. First of all, all the entities in the world (real and abstract) are connected by some relations. A big part of them is kind of regular or close to regular (e.g. the ordering of natural numbers), and people can and do exploit this very often. However, there is huge, gigantic, infinitely larger (or even more colossal, but I lack words...) class of relations that are weird, curious, peculiar, or even ridiculous. We do not know how to bridle them, so we analyze very tiny, finite parts of them using graphs. Every time when we show an isomorphism between such graphs, a new star starts to shine on the firmament of human thinking power.

Ok, to be more concrete (this list wasn't sorted by any criterion):

• Cryptography, e.g. zero knowledge proofs.
• In automata theory: multiple uses, mainly to show that some two languages are equal.
• In parallel processing, to reason about behaviour of complex systems.
• In verification of many things: computer programs, logic proofs, or even electronic circuits.
• In compilers, e.g. to perform various optimizations.
• In any search engine that can use formulas more sophisticated than words, e.g. in chemistry, biology, but I guess also music and other arts fall into that category as well.
• Security, i.e. fingerprints scanners, facial scanners, retina scanners and so on.
• I do not know for sure, but it is highly probable, that any system that performs clustering would benefit from fast graph-isomorphism algorithm, e.g.
  • linking two facebook's accounts of the same person,
  • recognizing web users based on their behavior,
  • recognizing plagiarism in students solutions,
  • :-) I have no idea if there is a Numb3rs episode that uses graph isomorphism problem, but there should be one.
• Civil engineering, city planning, building interior planning (this may fall into "search" category as well, e.g. recognizing geographic locations with desired properties).
• Analysis of social structures (special cases may include schools, military, parties, events, etc.), big part of it is search again.
• Analysis of business relations.
• I have no idea about medicine (not biology), but there has to be something there, this domain is too wide. Edit: Quick search revealed two (quite obvious...) applications:
  • travel medicine,
  • searching in database or medical images.

Please note, that most of those points are meta-examples, they do not specify particular use, i.e. there are multiple uses in each of those.

Answer 4

A good example is the perturbative expansion of Feynman's path integral by summing over Feynman diagrams. This is an infinite series, each stage of which is parameterized by a finite sum over isomorphism classes of certain kinds of graphs. Writing down all isomorphism classes of graphs with certain data requires being able to tell if two graphs are isomorphic.