In representing this relation as a graph, elements of are called the vertices of the graph. They are typically represented by labeled points or small circles. We connect vertex to vertex with an arrow, called an edge, going from vertex to vertex if and only if . This type of graph of a relation is called a directed graph or digraph. Figure 6.2.1 is a digraph for . Notice that since 0 is related to itself, we draw a βself-loopβ at 0.
The actual location of the vertices in a digraph is immaterial. The actual location of vertices we choose is called an embedding of a graph. The main idea is to place the vertices in such a way that the graph is easy to read. After drawing a rough-draft graph of a relation, we may decide to relocate the vertices so that the final result will be neater. Figure 6.2.1 could also be presented as in Figure 6.2.2.
A vertex of a graph is also called a node, point, or a junction. An edge of a graph is also referred to as an arc, a line, or a branch. Do not be concerned if two graphs of a given relation look different as long as the connections between vertices are the same in the two graphs.
Let , and let . Then is a relation on whose digraph is Figure 6.2.6.
Figure6.2.6.Graph for set containment on subsets of
We will see in the next section that since has certain structural properties that describe βpartial orderings.β We will be able to draw a much simpler type graph than this one, but for now the graph above serves our purposes.