Imagine an organization that wants to set up teams of three to work on some projects.
In order to maximize the number of people on each team who had previous experience working
together successfully, the director asked the members to provide names of their previous partners.
This information is displayed below both in a table and in a diagram.
From the diagram, it is easy to see that Bev, Cai, and Flo are a group of three previous partners, and so it would be reasonable for them to form one of these teams. • This drawing shows that placing Hal on the same team as Ed would leave Gia and Ira on a team where they would not have a previous partner.
Drawings such as these are known as a graph.
– The edges may be straight or curved and should either connect one vertex to another or a vertex to itself
In general, a graph consists of a set of vertices and a set of edges connecting various pairs of vertices.
The vertices are usually labeled with v’s and the edges with e’s.
When an edge connects a vertex to itself (e5), it is called a loop.
When two edges connect the same pair of vertices (e2 and e3), they are said to be parallel.
It is quite possible for a vertex to be unconnected by an edge to any other vertex in the graph (v5), and in that case the vertex is said to be isolated.
We have discussed the directed graph of a binary relation on a set.
A directed graph is like an (undirected) graph except that each edge is associated with an
ordered pair of vertices rather than a set of vertices.