Graph (discrete mathematics): Difference between revisions

Revision as of 19:36, 31 December 2024

Revision as of 01:45, 11 January 2025

Line 68:

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 \{(x,y) \mid (x,y) \in V^2 \}</math>. For directed multigraphs, the definition of <math>\phi</math> should be modified to <math>\phi : E \to \{(x,y) \mid (x,y) \in 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''}}.