Graph matching & Levenshtein distance (p1)

J.K. Nguyen

Graphs are mathematical structures widely used to abstract and model relation dynamics in various systems. For example, the web can be represented by a graph in which nodes (vertices) correspond to webpages and edges (links) correspond to hyperlinks.

Definition: A graph $latex G$ is a set of vertex $latex V$ connected by edges  $latex E$ denoted as the ordered pair $latex G=(V,E)$.

A very important problem in graph theory is called graph matching which is measuring the similarity between graphs. This problem has a variety of applications such as social networks, image processing and bioinformatics.

How do we know if two graphs are the same? Well, you can try to take nodes of one graph and rearrange it to look like the other graph without adding or removing edges. If the two graphs end up looking identical (ignoring labels if any) then we say that the graphs are isomorphic. You can…

View original post 386 more words


About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 27, 2013, in Algorithms and tagged , . Bookmark the permalink. 3 Comments.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: