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.

스크린샷 2025-08-01 오전 6.30.17.png

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.

Graphs

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.

Directed Graphs

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.