FACTOID # 15: Most people live in poverty in most African countries.
 
 Home   Encyclopedia   Statistics   Countries A-Z   Flags   Maps   Education   Forum   FAQ   About 
 
WHAT'S NEW
RECENT ARTICLES
More Recent Articles »
 

FACTS & STATISTICS    Simple view

  1. Select countries to view: (hold down Control key and click to select several)

     

     

    Compare:

     

     
  1. Select fact or statistic: (* = graphable)

     

     

     

  2. (OPTIONAL) Compare to statistic: (both need to be graphable)

     

     

     

  3. View result as:

     

       
(OR) SEARCH ALL encyclopedia, stats & forums:   

Encyclopedia > Graph isomorphism

In graph theory, a graph isomorphism is a bijection (a one-to-one and onto mapping) between the vertices of two graphs G and H A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ... A bijective function. ... You may be looking for an Injective function, in which (f(a)=f(b)) -> a=b, or a Bijection function, which is both injective and surjective (ie. ... In mathematics, a surjective function (or onto function or surjection) is a function with the property that all possible output values of the function are generated when the input ranges over all the values in the domain. ... The word mapping has several senses: In mathematics and related technical fields, it is some kind of function: see map (mathematics). ...

f colon V(G) to V(H) ,!

with the property that any two vertices u and v from G are adjacent if and only if ƒ(u) and ƒ(v) are adjacent in H. If an isomorphism can be constructed between two graphs, then we say those graphs are isomorphic. Determining whether two graphs are isomorphic is referred to as the graph isomorphism problem. In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...


The graph isomorphism problem arises in a variety of practical applications. In both organic chemical research and circuit design it is important to build databases of graphs; in this case, we wish to know if a new graph we are entering is the same as one that is already present, to save storage and detect correspondences between data.


Besides its importance for these applications, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems listed by Garey & Johnson (1979) as belonging to NP, but neither known to be in polynomial time nor NP-complete, although isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.[1] As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In computational complexity theory, polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...


A generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete. In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

Contents

Example

The two graphs shown below are isomorphic, despite their very different looking drawings, due to the existence of the bijection described to the right. As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. ...

Graph G Graph H An isomorphism
between G and H
ƒ(a) = 1

ƒ(b) = 6 Image File history File links Graph_isomorphism_a. ... Image File history File links Graph_isomorphism_b. ...


ƒ(c) = 8


ƒ(d) = 3


ƒ(g) = 5


ƒ(h) = 2


ƒ(i) = 4


ƒ(j) = 7

Solved special cases

A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:

In graph theory, a planar graph is a graph that can be drawn so that no edges intersect (or that can be embedded) in the plane. ... In graph theory, an interval graph is a graph that captures the intersections among a set of intervals on the real line. ... In mathematics, the genus has few different meanings Topology The genus of a connected, oriented surface is an integer representing the maximum number of cuttings along closed simple curves without rendering the resultant manifold disconnected. ... In graph theory, the degree (or valency) of a vertex is the number of edges incident to the vertex. ... In mathematics, a number is called an eigenvalue of a matrix if there exists a nonzero vector such that the matrix times the vector is equal to the same vector multiplied by the eigenvalue. ...

Complexity class GI

Because the graph isomorphism problem is neither known to be complete for any known classical class nor known to be efficiently solvable, researchers sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem.[12] In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...


GI is contained in both NP and co-AM. Graph isomorphism remains GI-complete even when restricted to a number of "hard" special cases, such as directed acyclic graphs and regular graphs. It also has nontrivial complete problems in addition to isomorphism problems, such as a variation on the maximum clique problem.[13] GI is contained in and low for Parity P, as well as contained in the potentially much smaller class SPP.[14] That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial-time nondeterministic Turing machine has an even or odd number of accepting paths. GI is also contained in and low for ZPPNP.[15] This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time. In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ... A simple directed acyclic graph In computer science and mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no nonempty directed path that starts and ends on v. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ... In computational complexity theory, the clique problem or k-clique problem is a graph-theoretical NP-complete problem. ... In computational complexity theory, it is said that a complexity class B is low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional... In computational complexity theory, the complexity class ⊕P (pronounced parity P) is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. ... In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ... In computing, a Las Vegas algorithm is a randomized algorithm that is correct; that is, it always produces the correct result. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ...


See also

In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. ...

Notes

  1. ^ McKay 1981
  2. ^ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957) pp. 961–968
  3. ^ Aho, Hopcroft & Ullman 1974
  4. ^ Hopcroft & Wong 1974
  5. ^ Booth & Lueker 1979
  6. ^ Colbourn 1981
  7. ^ Bodlaender 1990
  8. ^ Miller 1980
  9. ^ Filotti & Mayer 1980
  10. ^ Luks 1982
  11. ^ Babai, Grigoryev & Mount 1982
  12. ^ Booth & Colbourn 1979; Köbler, Schöning & Torán 1993
  13. ^ Kozen 1978.
  14. ^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
  15. ^ Arvind & Köbler 2000

References

  • Arvind, Vikraman & Köbler, Johannes (2000), "Graph isomorphism is low for ZPP(NP) and other lowness results.", Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Lecture Notes in Computer Science 1770, pp. 431–442, ISBN 3-540-67141-2.
  • Arvind, Vikraman & Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", Information and Computation 204 (5): 835–852, DOI 10.1016/j.ic.2006.02.002.
  • Babai, László; Grigoryev, D. Yu. & Mount, David M. (1982), Isomorphism of graphs with bounded eigenvalue multiplicity, pp. 310-324, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, <http://portal.acm.org/citation.cfm?id=802206&dl=ACM&coll=portal>
  • Bodlaender, Hans (1990), "Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees", Journal of Algorithms 11: 631–643
  • Booth, Kellogg S. & Colbourn, C. J. (1979), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.
  • Booth, Kellogg S. & Lueker, George S. (1979), "A linear time algorithm for deciding interval graph isomorphism", Journal of the ACM 26 (2): 183–195, DOI 10.1145/322123.322125
  • Colbourn, C. J. (1981), "On testing isomorphism of permutation graphs", Networks 11: 13–21
  • I. S. Filotti , Jack N. Mayer (1980), A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236-243
  • Hopcroft, John & Wong, J. (1974), "Linear time algorithm for isomorphism of planar graphs", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184, DOI 10.1145/800119.803896.
  • Köbler, Johannes; Schöning, Uwe & Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330, DOI 10.1007/BF01200427.
  • Köbler, Johannes; Schöning, Uwe & Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0817636807.
  • Kozen, Dexter (1978), "A clique problem equivalent to graph isomorphism", ACM SIGACT News 10 (2): 50–52, DOI 10.1145/990524.990529.
  • Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences 25: 42–65.
  • McKay, Brendan D. (1981), "Practical graph isomorphism", Congressus Numerantium 30: 45–87, 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), <http://cs.anu.edu.au/~bdm/nauty/PGI/>
  • Miller, Gary (1980), Isomorphism testing for graphs of bounded genus, pp. 225-235, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, <http://portal.acm.org/citation.cfm?id=804670&dl=ACM&coll=portal>

Surveys

  • Ronald Read and Derek Corneil. "The graph isomorphism disease". Journal of Graph Theory 1977, 1, 339-363
  • Gati, G. "Further annotated bibliography on the isomorphism disease." – J. of Graph Theory, 3 (1979), 95-109
  • V. N. Zemlyachenko, N. M. Korneenko and R. I. Tyshkevich, "Graph isomorphism problem", " Journal of Mathematical Sciences", Vol. 29, no. 4, 1985, pp. 1426-1481 doi:10.1007/BF02104746 (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 118, pp. 83–158, 1982.)

This article incorporates material from graph isomorphism on PlanetMath, which is licensed under the GFDL. Dr. Alfred V. Aho is a computer scientist. ... John Hopcroft John E. Hopcroft (born October 7, 1939) is a renowned theoretical computer scientist and the grandson of Jacob Nist, founder of the Seattle Box Company. ... Jeffrey D. Ullman (born November 22, 1942) is a renowned computer scientist. ... László Babai László Babai (called Laci by friends and colleagues) is a professor of mathematics and computer science at the University of Chicago. ... Dima Yurevitz Grigoriev (b. ... The Association for Computing Machinery, or ACM, was founded in 1947 as the worlds first scientific and educational computing society. ... Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractibility: A Guide to the Theory of NP-completeness. ... David S. Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. ... John Hopcroft John E. Hopcroft (born October 7, 1939) is a renowned theoretical computer scientist and the grandson of Jacob Nist, founder of the Seattle Box Company. ... Brendan D. McKay is a Professor in the Department of Computer Science at ANU (Australian National University). ... Gary Lee Miller (March 19, 1947 – February 16, 1969) was a United States Army officer and a recipient of the United States militarys highest decoration—the Medal of Honor—for his actions in the Vietnam War. ... A digital object identifier (or DOI) is a standard for persistently identifying a piece of intellectual property on a digital network and associating it with related data, the metadata, in a structured extensible way. ... PlanetMath is a free, collaborative, online mathematics encyclopedia. ...


  Results from FactBites:
 
PlanetMath: graph isomorphism (66 words)
A graph isomorphism is a bijection between the vertices of two graphs
If an isomorphism can be constructed between two graphs, then we say those graphs are isomorphic.
This is version 2 of graph isomorphism, born on 2002-02-03, modified 2002-02-03.
Graph theory - definition of Graph theory in Encyclopedia (875 words)
Graph theory is the branch of mathematics that examines the properties of graphs.
Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs).
A graph with only vertices and no edges is known as an empty graph; the graph with no vertices and no edges is the Null graph.
  More results at FactBites »


 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments
Please enter the 5-letter protection code

Want to know more?
Search encyclopedia, statistics and forums:
 


Lesson Plans | Student Area | Student FAQ | Reviews | Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms.