Graph isomorphism

Encyclopedia : G : GR : GRA : Graph isomorphism

---

A graph isomorphism is a bijection, i.e., a one-to-one mapping, between the vertices of two graphs [G] and [H]:

[ f: V(G) \rightarrow V(H)]

with the property that any two vertices [u] and [v] from [G] are adjacent if and only if [f(u)] and [f(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 the graph isomorphism problem.

Example

Consider these two graphs:

Although these graphs look very different, they are isomorphic; one isomorphism between them is

:[ f(a) = 1]

:[ f(b) = 6]

:[ f(c) = 8]

:[ f(d) = 3]

:[ f(g) = 5]

:[ f(h) = 2]

:[ f(i) = 4]

:[ f(j) = 7]

See also

• graph homomorphism

This article incorporates material from on PlanetMath, which is licensed under the [Text of the GNU Free Documentation LicenseGFDL].

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.

Search Titles

0

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

?