Labeled Graphs
The refining technique is easily generalized to graphs whose vertices
and/or edges are labeled. The labels can be of an arbitrary
nature. Traditionally labels are called colors, so we say that
the graph is colored. For chemical
graphs that represent molecules, the colors of the
vertices are names of the atoms. The edges of the chemical
graphs are often labeled with integers to show the ordinary links, or
double links, etc. Normally, the links are not more than
tripled. Sometimes, instead of showing the labels of the edges, we
duplicate the edges as on the figure.
Formal Definition
Two colored graphs
and
are called isomorphic if there is a bijective mapping
from
onto
such that
- for every
,
the colors of
and
are the same;
- for any two vertices
,
there is a one-to-one correspondence between the edges connecting
with
and those connecting
with
so that the corresponding edges have the same color.
If the vertices and/or edges have no labels, then they can be
given a special label different from the rest. Thus, we can always
assume that all vertices and all edges are colored.
Copyright
2000
Rensselaer Polytechnic Institute. All Rights Reserved.