Maths - Graph Theory - Morphism Between Graphs

A morphism between graphs is required to preserve structure, so,

A morpism between preordered sets is:

  • monotone if xy implies f(x)f(y).
  • antitone if xy implies f(y)f(x).

where:

  • xy represents an edge from x to y.
function between preordered sets

So a morphism between graphs maps nodes to nodes and edges to edges in a way the preserves the structure.

Decision Problem

Deciding if there is a morphism between graphs is an NP-complete problem. That is:

Deciding if there is an isomorphism between graphs is also an important problem in computational complexity theory.

Hom Sets

We will use the notation:

Hom(A,X)

to denote all the possible morphisms from graph 'A' to graph 'X'.

Properties of Morphisms of Graphs

Graph Colourings

Graph colourings are an example of a graph-morphism where each node maps to a given colour.

Endomorphisms on Graphs

 


metadata block
see also:

For a discussion about using and representing graphs in category theory see this page.

There is a program which can represent and do calculations on graph theory on this page.

Correspondence about this page

Book Shop - Further reading.

Where I can, I have put links to Amazon for books that are relevant to the subject, click on the appropriate country flag to get more details of the book or to buy it from them.

cover Modern Graph Theory (Graduate Texts in Mathematics, 184)

Terminology and Notation

Specific to this page here:

 

This site may have errors. Don't use for critical systems.

Copyright (c) 1998-2017 Martin John Baker - All rights reserved - privacy policy.