Editing Graph (discrete mathematics) (section)

=== Directed graph ===
{{main|Directed graph}}
[[File:Directed.svg|thumb|upright|A directed graph with three vertices and four directed edges, where the double arrow represents two directed edges in opposite directions]]

A '''directed graph''' or '''digraph''' is a graph in which edges have orientations.

In one restricted but very common sense of the term,{{sfn|Bender|Williamson|2010|p=161}} a '''directed graph''' is a pair {{math|1=''G'' = (''V'', ''E'')}} comprising:
* {{mvar|V}}, a [[Set (mathematics)|set]] of ''vertices'' (also called ''nodes'' or ''points'');
* {{mvar|E}}, a [[Set (mathematics)|set]] of ''edges'' (also called ''directed edges'', ''directed links'', ''directed lines'', ''arrows'', or ''arcs''), which are [[ordered pair]]s of distinct vertices: <math>E \subseteq \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math>.
To avoid ambiguity, this type of object may be called precisely a '''directed simple graph'''.

In the edge {{math|(''x'', ''y'')}} directed from {{mvar|x}} to {{mvar|y}}, the vertices {{mvar|x}} and {{mvar|y}} are called the ''endpoints'' of the edge, {{mvar|x}} the ''tail'' of the edge and {{mvar|y}} the ''head'' of the edge. The edge is said to ''join'' {{mvar|x}} and {{mvar|y}} and to be ''incident'' on {{mvar|x}} and on {{mvar|y}}. A vertex may exist in a graph and not belong to an edge. The edge {{math|(''y'', ''x'')}} is called the ''inverted edge'' of {{math|(''x'', ''y'')}}. ''[[Multiple edges]]'', not allowed under the definition above, are two or more edges with both the same tail and the same head.

In one more general sense of the term allowing multiple edges,{{sfn|Bender|Williamson|2010|p=161}} a directed graph is sometimes defined to be an ordered triple {{math|1=''G'' = (''V'', ''E'', ''ϕ'')}} comprising:
* {{mvar|V}}, a [[Set (mathematics)|set]] of ''vertices'' (also called ''nodes'' or ''points'');
* {{mvar|E}}, a [[Set (mathematics)|set]] of ''edges'' (also called ''directed edges'', ''directed links'', ''directed lines'', ''arrows'' or ''arcs'');
* {{mvar|ϕ}}, an ''incidence function'' mapping every edge to an [[ordered pair]] of vertices (that is, an edge is associated with two distinct vertices): <math>\phi : E \to \{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math>.

To avoid ambiguity, this type of object may be called precisely a '''directed multigraph'''.

A ''[[Loop (graph theory)|loop]]'' is an edge that joins a vertex to itself. Directed graphs as defined in the two definitions above cannot have loops, because a loop joining a vertex <math>x</math> to itself is the edge (for a directed simple graph) or is incident on (for a directed multigraph) <math>(x,x)</math> which is not in <math>\{(x,y) \mid (x,y) \in V^2 \;\textrm{ and }\; x \neq y \}</math>. So to allow loops the definitions must be expanded. For directed simple graphs, the definition of <math>E</math> should be modified to <math>E \subseteq V^2</math>. For directed multigraphs, the definition of <math>\phi</math> should be modified to <math>\phi : E \to V^2</math>. To avoid ambiguity, these types of objects may be called precisely a '''directed simple graph permitting loops''' and a '''directed multigraph permitting loops''' (or a ''[[Quiver (mathematics)|quiver]]'') respectively.

The edges of a directed simple graph permitting loops {{mvar|G}} is a [[Binary relation#Homogeneous relation|homogeneous relation]] ~ on the vertices of {{mvar|G}} that is called the ''adjacency relation'' of {{mvar|G}}. Specifically, for each edge {{math|(''x'', ''y'')}}, its endpoints {{mvar|x}} and {{mvar|y}} are said to be ''adjacent'' to one another, which is denoted {{math|''x'' ~ ''y''}}.