Elements of are called vertices, elements of edges. The vertex/vertices associated with any edge via the map is/are called the endpoint(s) of . If an edge has only one endpoint, it is called a loop. and are said to be parallel if .
As two examples, a multigraph is a pseudograph such that for each edge (no loops allowed). A graph is a multigraph such that is one-to-one (no parallel edges allowed).
Definition. Given two pseudographs and , a graph homomorphism from to consists of two functions and , such that
The function is defined as .
In case when and are graphs, a graph homomorphism may be defined in terms of a single function satisfying the condition (*)
is an edge of is an edge of .
To see this, suppose is a graph homomorphism from to . Then . The last equation says that and are endpoints of . Conversely, suppose is a function sastisfying condition (*). For each with end points , let be the edge whose endpoints are . There is only one such edge because is a graph, having no parallel edges. Define by . Then is a well-defined function which also satisfies Equation (1). So is a graph homomorphism .
The definition of a graph homomorphism between pseudographs can be analogously applied to one between directed pseudographs. Since the incidence map now maps each edge to an ordered pair of vertices, a graph homomorphism thus defined will respect the “direction” of each edge. For example,
|Date of creation||2013-03-22 16:04:53|
|Last modified on||2013-03-22 16:04:53|
|Last modified by||CWoo (3771)|