• Nebyly nalezeny žádné výsledky

# Homomorphisms of graphs

1.3.9 Example In the same spirit as Example 1.3.8, let us see what data type is represented by the graph

a s

−→−→t n (1.4)

The data type has a signature consisting of two objects, call thema and n, and two arrows, let us call them (temporarily) s,t: a−→ n. But if we interpreta as arrows, n as nodes and s and t as source and target, this is exactly what we have defined a small graph to be: two sets and two functions from one of the sets to the other. For this reason, this graph is called the graph of graphs. (See [Lawvere, 1989].)

1.3.10 Exercises

1. The graphs in this section have labeled nodes; for example, the two nodes in (1.3) are labeled ‘1’ and ‘n’. Produce a graph analogous to (1.4) that expresses the concept of ‘graph with nodes labeled from a setL’.

2. LetG be a graph with set of nodesN and set of arrowsA. Show thatG is simple if and only if the functionhsource,targeti:A−→N×N is injective.

(This uses the pair notation for functions to products as described in 1.2.8.)

### 1.4 Homomorphisms of graphs

A homomorphism of graphs should preserve the abstract shape of the graph.

A reasonable translation of this vague requirement into a precise mathemat-ical definition is as follows.

1.4.1 Definition A homomorphismφ from a graph G to a graph H, denotedφ:G −→H, is a pair of functionsφ0:G0−→H0andφ1:G1−→H1

with the property that ifu:m−→n is an arrow of G, then φ1(u) :φ0(m)

−→φ0(n) inH.

It is instructive to restate this definition using the source and target mappings from 1.3.9: let sourceG :G1−→G0 be the source map that takes an arrow (element ofG1) to its source, and similarly define targetG, sourceH

and targetH. Then the pair of mapsφ0:G0−→H0 andφ1:G1−→H1is a graph homomorphism if and only if

sourceH φ10sourceG and

targetH φ10targetG

1.4.2 Notation of the form a: B −→C is overloaded in several ways. It can denote a set-theoretic function, a graph homomorphism or an arrow in a graph. In fact, all three are instances of the third since there is a large graph whose nodes are sets and arrows are functions (see 1.3.3) and another whose nodes are (small) graphs and arrows are graph homomorphisms.

Another form of overloading is that if φ :G −→ H is a graph homo-morphism, φ actually stands for a pair of functions we here call φ0 : G0

−→H0 and φ1:G1−→H1. In fact, it is customary to omit the subscripts and useφfor all three (the graph homomorphism as well as its components φ0 andφ1).

This does not lead to ambiguity in practice; in reading about graphs you are nearly always aware of whether the author is talking about nodes or arrows. We will keep the subscripts in this section and drop them thereafter.

1.4.3 Example IfG is any graph, theidentity homomorphismidG :G

−→G is defined by (idG)0= idG0 (the identity function on the set of nodes ofG) and (idG)1= idG1.

1.4.4 Example IfG is the graph

1 -2 -3

4

?

R

(1.5)

andH is this graph,

S -F

Q

?

R

I (1.6)

then there is a homomorphism φ:G −→H for whichφ0(1) =S, φ0(2) = φ0(3) =F and φ0(4) =Q, andφ1 takes the loop on 2 and the arrow from 2 to 3 both to the upper loop onF; what φ1does to the other two arrows is forced by the definition of homomorphism. Because there are two loops onF there are actually four possibilities forφ1on arrows (while keepingφ0 fixed).

1.4 Homomorphisms of graphs 13 1.4.5 Example IfH is any graph with a node nand a loopu:n−→n, then there is a homomorphism from any graph G to H that takes every node of G to n and every arrow to u. This construction gives two other homomorphisms fromG toH in Example 1.4.4 besides the four mentioned there. (There are still others.)

1.4.6 Example There is a homomorphism σ from Example 1.3.8 to the graph of sets that takes the node called 1 to a one-element set, which in contexts like this we will denote{∗}, and that takes the nodento the setN ofnatural numbers. (Following the practice in computing science rather than mathematics, we start our natural numbers at 0.) The homomorphism σtakes the arrow 1−→nto the function∗ 7→0 that picks out the natural number 0, andσ(succ), naturally, is the function that adds 1. This is an ex-ample of a model of a sketch, which we discuss in 4.7.7. This homomorphism gives a semantics for the sketch constituted by the abstract graph of 1.3.8.

1.4.7 Example The homomorphism in Example 1.4.6 is not the only homo-morphism from Example 1.3.8 to sets. One can letngo to the set of integers (modk) for a fixedkand let succbe the function that adds one (modk) (it wraps around). You can also get other homomorphisms by taking this ex-ample (or 1.4.6) and adjoining some extra elements to the set corresponding tonwhich are their own successors.

1.4.8 Example Example 1.3.9 can be given a semantics in the same way as Example 1.3.8. IfG isany small graph, there is a graph homomorphism φfrom the diagram in (1.4) to the graph of sets for which φ0(n) is the set of nodes of G, φ0(a) is the set of arrows, and φ1 takes the arrows labeled source and target to the corresponding functions from the set of arrows of G to the set of nodes ofG.

Moreover, the converse is true: any homomorphism from (1.4) to the graph of sets gives a graph. The nodes of the graph are the elements ofφ0(n) and the arrows are the elements ofφ0(a). Iff ∈φ0(a), then the source off isφ1(source)(f) and the target isφ1(target)(f). Thus the graph of Exam-ple 1.3.2 corresponds to the homomorphismφwhereφ0(n) ={1,2},φ0(a) = {a, b, c},φ1(source) is the functiona7→1, b7→1, c7→2 andφ1(target) is the functiona7→1, b7→2, c7→1.

In short, graph homomorphisms from (1.4) to the graph of sets corre-spond to what we normally call graphs.

1.4.9 Notation In an expression like ‘φ1(source)(f)’,φ1is a function whose value at ‘source’ is a function that applies to an arrowf. As this illustrates, the application operation associates to the left.

1.4.10 Exercises

1. Show that if the codomainH of a graph homomorphism φ is a simple graph, thenφ1is determined uniquely byφ0.

2. Show that the composite of graph homomorphisms is a graph homo-morphism. Precisely: if φ: G −→H and ψ :H −→K are graph homo-morphisms, then define the compositeψ φ by requiring that (ψ φ)0= ψ0 φ0 and (ψ φ)11 φ1. Then prove that ψ φ is a graph homo-morphism.

3. Letφbe a homomorphismG −→H for which bothφ0andφ1are bijective.

Defineψ:H −→G byψ0= (φ0)−1andψ1= (φ1)−1. a.Show thatψis a graph homomorphism fromH toG.

b.Using the definition of composite in the preceding exercise, show that bothψφ= idG andφψ= idH.

Outline

Související dokumenty