category of directed graphs

 graph theory
Notation DiGraph\DiGraph Objects directed graphs, meaning tuples (V,E,s,t)(V,E,s,t), where VV is a set of vertices, EE is a set of edges, and s,t:E⇉Vs,t : E \rightrightarrows V are two maps (the source and target maps); we often abbreviate this tuple as (V,E)(V,E) Morphisms A morphism f:(V,E)→(V′,E′)f : (V,E) \to (V',E') is a pair of maps fV:V→V′f_V : V \to V' and fE:E→E′f_E : E \to E' satisfying s∘fE=fV∘ss \circ f_E = f_V \circ s and t∘fE=fV∘tt \circ f_E = f_V \circ t. Related Set\Set, Set×Set\Set \times \Set, Pair\Pair, Cat\Cat, Bin\Bin External nLab Link

This category can also be described as the functor category [Pair,Set][\Pair,\Set], where Pair\Pair denotes the walking pair.

Satisfied Properties

Assigned properties

Deduced properties

Unsatisfied Properties

Assigned properties

Deduced properties*

*This also uses the deduced satisfied properties.

Unknown properties

—

Special objects

  • terminal object: the graph with one vertex and one loop
  • initial object: the graph with no vertices and hence no edges
  • products: The product of a family of directed graphs (Vi,Ei,si,ti)(V_i,E_i,s_i,t_i) is (∏iVi,∏iEi,∏isi,∏iti)(\prod_i V_i, \prod_i E_i, \prod_i s_i, \prod_i t_i).
  • coproducts: The coproduct of a family of directed graphs (Vi,Ei,si,ti)(V_i,E_i,s_i,t_i) is (∐iVi,∐iEi,∐isi,∐iti)(\coprod_i V_i, \coprod_i E_i, \coprod_i s_i, \coprod_i t_i). Intuitively, we take the disjoint union of the vertices, keep the edges in the individual graphs, and do not add any edges between distinct graphs.

Special morphisms

  • isomorphisms: morphisms f=(fV,fE)f = (f_V, f_E) where fVf_V and fEf_E are bijective
  • monomorphisms: morphisms f=(fV,fE)f = (f_V, f_E) where fVf_V and fEf_E are injective
  • epimorphisms: morphisms f=(fV,fE)f = (f_V, f_E) where fVf_V and fEf_E are surjective
  • regular monomorphisms: same as monomorphisms
  • regular epimorphisms: same as epimorphisms

Indistinguishable categories

These categories in the database currently have exactly the same properties as the category of directed graphs. This indicates that the data may be incomplete or that a distinguishing property may be missing from the database.