Introduction to Discrete Mathematics

A digraph (or directed graph) \(D\) consists of a set \(V\) of vertices and a set \(E\) of directed edges (or arrows), each of which is represented as an ordered pair \((u,v)\text{,}\) where \(u,v\in V\text{.}\) We say that \(u\) is the initial vertex and \(v\) is the terminal vertex of the directed edge \((u,v)\text{.}\) We write \(D=(V,E)\) as we did with undirected graphs. The indegree of a vertex \(v\) in a digraph, denoted \({\deg^-(v)}\text{,}\) is the number of directed edges that have \(v\) as a terminal vertex while the outdegree of \(v\text{,}\) denoted \({\deg^+(v)}\text{,}\) is the number of edges having \(v\) as an initial vertex.

As expected, we have the following result that is analogous to the Handshake Lemma (Theorem 10.14).

Each graph/digraph is determined by its vertices and the manner in which they are connected by edges, not the way a graph/digraph might be sketched. We can represent a graph in a couple of ways.

The adjacency list of a simple graph lists all vertices in one column and all adjacent vertices in second column. For a digraph, the columns contain the initial vertices and the associated terminal vertices.

An \(m\times n\) matrix \(A\) is a rectangular array of numbers with \(m\) rows and \(n\) columns. The entry in the \(i\)th row and \(j\)th column is indicated by \(A_{i,j}\text{.}\)

The adjacency matrix \(A\) of a graph (respectively, digraph) \(G\) with vertices listed as \(v_1, v_2, \dots, v_n\) is the \(n\times n\) matrix \(A\) whose entry \(A_{i,j}\) in row \(i\) and column \(j\) is the number of edges connecting \(v_i\) and \(v_j\) (respectively, the number of edges from \(v_i\) to \(v_j\)).

Recall that a graph is not determined by a sketch since many sketches give the same graph. It may be hard to recognize from sketches whether two graphs are “essentially” the same even though the vertices may be different points. The notion of isomorphism (same form) gives us a way to deal with this. Two simple graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) are the isomorphic, written \(G_1 \cong G_2\text{,}\) if there is a a bijection \(f:V_1\to V_2\) such that \(\{u,v\}\) is an edge in \(G_1\) if and only if \(\{f(u),f(v)\}\) is an edge in \(G_2\text{.}\) The function \(f\) is called an isomorphism. For digraphs, we require that \((u,v)\) is a directed edge in \(G_1\) if and only if \((f(u),f(v))\) is a directed edge in \(G_2\text{.}\)

Warning! The second method above usually involves much less writing, but be aware that the adjacency matrices may differ in one ordering but agree with a different ordering.

The following theorem likely does not come as a surprise.

A digraph is strongly connected if for each pair of distinct vertices \(u\) and \(v\) there is a (directed) walk from \(u\) to \(v\text{.}\) A digraph is weakly connected if the underlying undirected graph in which the direction of edges is removed is connected. Note that a strongly connected digraph will always be weakly connected. A strongly connected component of a digraph is a maximal strongly connected subgraph.

We now introduce a couple of important circuits that a graph may or may not possess. An Euler circuit in a graph \(G\) is a circuit that contains every edge of the graph. An Euler trail in a graph is a trail that contains every edge of the graph. Note that an Euler circuit is also an Euler trail as well.

Edges can be added to a connected graph in order to cause it to have an Euler circuit (or trail). In particular, an Eulerization of a connected graph is the addition of suitable multiple edges (i.e., duplicate existing edges) to permit an Euler circuit, mimicking what must be done to complete a circuit such as a postal route or other delivery/pick-up route.

A cycle in a graph that passes through every vertex is a Hamilton cycle. This is often called a Hamilton circuit. A Hamilton path is a path in a graph that includes every vertex.

Unfortunately, unlike the situation for Euler circuits, there is no known simple necessary and sufficient condition for a Hamilton cycle to exist in a graph. We can state some simple cases when one cannot exist, and there are some theorems for the existence of a Hamilton cycle, but these do not cover all possibilities.

We now turn our attention to trees. A tree is a connected graph that has no cycles. A forest is a graph in which every connected component is a tree. Trees provide a useful structure for organizing data, for displaying organization, and for decision processes.

A spanning tree of a simple graph \(G\) is a subgraph \(T\) of \(G\) such that \(T\) is a tree contains every vertex of \(G\text{.}\)

In fact, we have the following theorem.

Below, we provide informal descriptions of the depth-first and breadth-first algorithms for identifying a spanning tree in a connected simple graph \(G\) with vertices ordered as \(v_1, v_2, \dots, v_n\text{.}\)

Repeat the steps above (with revised \(v\)’s) as often as needed.

Repeat the above steps as needed.

A weighted graph is a graph with a positive numerical values assigned to each edge of the graph. A minimal spanning tree of a connected weighted graph is a spanning tree that has the smallest possible sum of weights for its edges.

Minimal spanning trees arose in the practical matter of designing an efficient electrical network, and the concept applies to similar network notions in many areas such as transportation, utilities, and others. We will discuss one early, elementary, and effective algorithms for finding a minimal spanning tree in a connected undirected weighted graph.

Prim’s Algorithm is an example of a greedy algorithm.