Graphs

A graph is a set of a finite number of vertices (also known as nodes) and edges, in which the edges are the links between vertices, and each edge in a graph joins two distinct nodes. Moreover, a graph is a formal mathematical representation of a network, i.e. a graph G is an ordered pair of a set V of vertices and a set E of edges, given as G = (V, E) in formal mathematical notation.

An example of a graph is shown in Figure 9.1:

Figure 9.1: An example of a graph

The graph G = (V, E) in Figure 9.1 can be described as below:

• V = {A, B, C, D, E}
• E = {{A, B}, {A, C}, {B, C}, {B, D}, {C, D}, {D, D}, {B, E}, {D, E}}
• G = (V, E)

Let’s discuss some of the important definitions of a graph:

• Node or vertex: A point or node in a graph is called a vertex. In the preceding diagram, the vertices or nodes are A, B, C, D, and E and are denoted by a dot.
• Edge: This is a connection between two vertices. The line connecting...