Graphics Reference
In-Depth Information
Figure . . Gantt chart
putethe critical path with graph-theoretic algorithms anddisplaythe results in some
variety of the Gantt chart.
Graph Matching
5.5.3
Given two graphs, how do we determine if there is an isomorphism between them?
Andiftheyarenotisomorphic,canweidentify isomorphicsubgraphs orcomputean
overall measure of concordance? hese questions have many answers; we will cover
only a few.
Matching graphs has many applications in biology, chemistry, image processing,
computer vision, and search engines. To the extent that a body of knowledge can be
representedasagraph(asetofverticesandrelationsamongthem),graphmatchingis
a core application. It provides, for example, the foundation for searching a database
of graphs for a particular graph. If images and other material can be represented
as graphs, then graph matching provides a powerful indexing mechanism for large
databases ofdisparatematerials. Indeed,sincearelational table canberepresentedas
agraph,matchingcanbeusedtoidentifycongruenttablesofprimitivesinadatabase.
Given the topic of this chapter, however, we will focus on matching D geometric
graphs.
Exact Graph Matching
Exact graph matching consists of identifying the isomorphism between two graphs.
his amounts to finding ( ) a vertex in one graph for every vertex in the other (and
viceversa) and( )anedgeinonegraphforeveryedgeintheother(andviceversa).If
bothgraphsareconnected,thenthesecondconditionsu cestoestablishtheisomor-
phism. Because this is a standard sorting-and-searching problem, it has polynomial
complexity.
heproblemismoregeneral,however,becauseweareusuallyinterestedinfinding
isomorphisms underapermutation transformation. hat is,weseek avertex relabel-
ing of G such that an isomorphism between G and G exists ater the relabeling.
his more general matching problem has unknown complexity. For planar graphs,
however, Hopcrot and Wong ( ) prove linear time complexity. Skiena ( ) and
Shashaetal.( )discussthistopicfurtherandreviewsotwareforgraphmatching.
Search WWH ::




Custom Search