|
|
|
|
graph isomorphism
|
(Definition)
|
|
|
A graph isomorphism is a bijection between the vertices of two graphs  and  :
with the property that any two vertices  and  from  are adjacent if and only if  and  are adjacent in  .
If an isomorphism can be constructed between two graphs, then we say those graphs are isomorphic.
For example, consider these two graphs:
Although these graphs look very different at first, they are in fact isomorphic; one isomorphism between them is
|
"graph isomorphism" is owned by vampyr.
|
|
(view preamble)
Cross-references: adjacent, property, graphs, vertices, bijection
There are 26 references to this entry.
This is version 2 of graph isomorphism, born on 2002-02-03, modified 2002-02-03.
Object id is 1708, canonical name is GraphIsomorphism.
Accessed 14437 times total.
Classification:
| AMS MSC: | 05C60 (Combinatorics :: Graph theory :: Isomorphism problems ) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ a \ar@{-}[r] \ar@{-}[rd] \ar@{-}... ...-}[r] \ar@{-}[rd] & i \ d \ar@{-}[ruu] \ar@{-}[ru] \ar@{-}[r] & j} } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1708/l2h/img10.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ a \ar@{-}[r] \ar@{-}[rd] \ar@{-}... ...-}[r] \ar@{-}[rd] & i \ d \ar@{-}[ruu] \ar@{-}[ru] \ar@{-}[r] & j} } \end{xy}$")
![$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ 1 \ar@{-}[rrr] \ar@{-}[rd] \ar@{... ...@{-}[dl] & 7 & \ 4 & & & 3 \ar@{-}[uuu] \ar@{-}[lll] \ar@{-}[ul] } } \end{xy}$](http://images.planetmath.org:8080/cache/objects/1708/l2h/img11.png "$\displaystyle \begin{xy} *!C\xybox{ \xymatrix{ 1 \ar@{-}[rrr] \ar@{-}[rd] \ar@{... ...@{-}[dl] & 7 & \ 4 & & & 3 \ar@{-}[uuu] \ar@{-}[lll] \ar@{-}[ul] } } \end{xy}$")
