Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 14.1 Basics and examples

🔗
graph (working definition)
🔗
a diagram consisting of a finite collection of points linked by line segments or arcs
graph (formal definition)
🔗
an ordered pair (V,E), where V is a finite set and E is a finite, unordered list of subsets of V, each of which has exactly 1 or 2 elements
vertex
🔗
a point in a graph (i.e. an element of V)
node
🔗
synonym for vertex
edge
🔗
a line or arc linking two vertices (i.e. an element of E)
empty graph
🔗
the graph (∅,∅), with no vertices and no edges
🔗

Warning 14.1.1.

🔗
The list E is not a set, since duplicate entries in this list have a graphical meaning; see below.
🔗
An element e∈E represents an edge as follows. If e consists of exactly two elements of V, draw a line between these two vertices. If e consists of exactly one element of V, draw a line from this vertex to itself.
🔗

Example 14.1.2. A very basic graph.

🔗
🔗
The graph G=(V,E), where
V={v1,v2,v3},E={{v1,v2},{v1,v3},{v2,v3}},
🔗
has three vertices and three edges.
Diagram illustrating a basic example graph.
Figure 14.1.3. Diagram of the graph G=(V,E).
🔗

Example 14.1.4. A slightly more complicated example graph.

🔗
🔗
The graph G=(V,E), where
V={v1,v2,v3,v4},E={{v1,v2},{v1,v2},{v1,v2},{v3},{v3}},
🔗
has four vertices and five edges.
Diagram illustrating a slightly more complicated example graph.
Figure 14.1.5. Diagram of the graph G=(V,E).
🔗

Worked Example 14.1.6. Using a graph to solve a problem.

🔗
Suppose we have jugs A,B,C with capacities 8,5,3 litres, respectively. Jug A is full of water and jugs B,C are empty. Can we divide the water into two exactly equal parts? If so, find the most efficient pouring sequence.
Solution.
Construct a graph with points labelled by elements (a,b,c)∈N×N×N, where a,b,c are the volumes of water in jugs A,B,C, respectively. Join two points with a line segment if we can obtain one set of volumes from the other in a single pour. We will ignore pours that return us to a configuration previously achievable by fewer pours.
A graph where nodes are jug fill states and edges represent being able to obtain one state from another by a single pour.
Figure 14.1.7. Graph to track possible jug fill states.
Following the left leg of the graph gets us to the desired configuration in 7 pours.
<Prev^TopNext>