For a directed graph with vertex set $X$, why are the arcs members of $X\times X$?

42 Views Asked by At

A directed graph G is defined to be pair $(X,U)$ where

a. $X$ is a set $(x_1, x_2, x_n,..., x_n)$ of elements called vertices; and

b. $U$ is a set $(u_1, u_2, u_3,...,u_n)$ of elements of the Cartesian product $X \times X$, called arcs.

I don't understand why is it $X \times X$? Does anyone here know? What is the example of that?

1

There are 1 best solutions below

0
On

You can think of a digraph as being a set of points with directed edges going between them. As such, a digraph is uniquely described by $X$, its set of vertices (points) and $U$, its set of edges.

A directed edge can be described by some source $u$ and some destination $v$, where $u, v \in X$. We often refer to the directed edge from $u$ to $v$ as the ordered pair $(u, v)$. Now the Cartesian product $X \times X = X^2$ is the set of all ordered pairs of two elements lying in $X$. Since every edge in a digraph points from one vertex to another, it follows that the set of all possible edges is the set $X^2$ (which is all possible ordered pairs). Of course, a digraph may not have all these possible edges in it, so the edge set $U$ is a (not necessarily proper) subset of these ordered pairs.