Now we need to figure out how to determine whether a given subset of bridges leaves the two shores connected. You may recall we interpreted this as determining whether there is a path from one shore to the other shore, where the path goes from a location over a remaining bridge to another location, and from that location over a remaining bridge to yet another location, and so forth. Now, in addition to telling bridges apart, we need to tell locations apart.

We call the two shores location 1 and location 2, and we number the islands with 3 through 8. Our map now looks like this:

Also, because where we can get to depends on which bridges in particular remain or are removed, it makes a difference which bridge is which. So we assign numbers to the bridges as well. Now our map is as follows:

Obviously, if the two shores are connected, then there is a path from the top shore, location 1, to the bottom shore, location 2. Similarly, if there is a path from location 1 to location 2, then there is a path from location 2 to location 1, and the shores are connected. So, then, the question of the shores being connected is equivalent to the question of whether there is a path from location 1 to location 2.

We can apply the trick of the trade about generating possibilities here, also. We consider the set of locations we can reach from location 1. Clearly, we can reach location 1 from location 1: this is the first of the sets of possibilities. Now we consider each of the bridges in turn: if it connects a location we know we can reach to a location we do not know we can reach, then we have discovered a new place we can reach. And, finally, if no bridge reaches from a location we know we can reach to a location we do not know we can reach, we are done: we have determined the set of the locations we can reach from location 1. If location 2 is in that set, then the shores are connected; if location 2 is not in that set, the shores are not connected.

In general, this process is called computing the *closure*
of a set under a *relation*.
In this instance, we are computing the closure of location 1 under
connectedness.

If *A* and *B* are sets, then a *relation* *R*
may hold between some elements of A and B.
If the relationship holds between elements *a* of *A* and
*b* of B, we write *aRb*.
For example, the relationship “less than”
(“<”)is defined on the natural numbers and the
natural numbers; we write *a* < *b* if *a* is
less than *b*.
The relationship *R* may equivalently be defined as a subset of
*A*×*B*: *R* = {(*a*, *b*) : *a*
∈ *A*, *b* ∈ *B*, *aRb*}.

We can use matrix algebra to compute closures.
Let *A* be a set, and *R* be a relation on that set and itself.
Let *E*_{0} = (*e*_{0,1}, *e*_{0,2},
..., *e*_{0,n})^{T} indicate an initial
subset of *A*: *e*_{0,i} is 1 if
*a*_{i} is in the initial subset, and 0 otherwise.
Let *B* = (*b*_{i,j}) be the incidence
matrix of the relation *R*: *b*_{i,j} =
1 if *a*_{i}*Ra*_{j} and 0 otherwise.
Now compute the matrix *E*_{k+1} =
*B*^{T}*E*_{k} using the following
boolean operations:

+ | 0 | 1 | × | 0 | 1 | |
---|---|---|---|---|---|---|

0 | 0 | 1 | 0 | 0 | 0 | |

1 | 1 | 1 | 1 | 0 | 1 |

*E*_{1} then indicates the subset of *A* related to the
initial subset *E*_{0}; *E*_{2}, the subset
related to *E*_{1}; and so forth.
The limit of the sequence {*E*_{k}}, if it exists
(and it does for finite n), is the closure of *A* under *R*.

As an example, consider a set of surviving bridges, as follows:

We indicate the locations we know we can reach by coloring them burgundy; initially, we know we can reach location 1, the top shore, as follows:

Now we color bridges leading us to places we do not yet know we can reach as blue, and color the newly known places we can reach burgundy; we do this four times, as follows:

And we see that with this combination of bridges, we can indeed reach location 2, the other shore, and the shores are connected. This combination of bridges would be counted towards the total of combinations leaving the shores connected.

Consider a second combination of bridges, and the progression through the discovery of the reachable locations:

We see this combination of bridges disconnects the two shores, and this combination of bridges would not be counted towards the total.

There are several ways we could program figuring what locations we can reach, given a collection of surviving bridges. We will use the following Trick of the Trade:

A *graph* is a set of vertices and a set of edges where
each edge connects two distinct vertices.
(This sounds an awful lot like locations and bridges.)
A common way of representing an edge of a graph is as a set of
the two edges it connects: so if *v*_{i}
and *v*_{j} are vertices,
{*v*_{i}, *v*_{j}} would
be an edge connecting them.

Sets are unordered, so the set {*v*_{i},
*v*_{j}} is the same as the set
{*v*_{j}, *v*_{i}}.

A *multigraph* extends a graph in two ways: it permits
multiple edges to connect the same two vertices, and it lets a
vertex connect to itself.
A *directed graph* extends a graph by letting the edges
be ordered pairs, rather than sets: an edge
(*v*_{i}, *v*_{j}) connects
vertex *v*_{i} to vertex *v*_{j},
but not vice-versa.
A directed graph would be useful for modeling a set of roads
that included one-way streets.

Bridge 1, for example, connects location 1 and 3; so we associate the set {1,3} with bridge 1. Similarly, we associated {1,4} with bridge 2, {1,5} with bridge 3, {3,4} with bridge 4, and so on. For each bridge, we will store in a list the pair of locations it connects. Each element of a list can store only one value, though; how will we do this? We use another trick of the trade:

A single variable can hold several values, if the values to be
held are small enough.
Remember from elementary arithmetic that the result of a division
of one positive integer by another, *a*÷*b*, is
an non-negative integer quotient *q* and a non-negative integer
remainder *r*.
Also, the remainder *r* is in the range 0 to *b*-1.

Suppose we have two non-negative values, *x* and *y*, to
store, and we know the value *x* is never as large as some
value *m*.
Then we can combine *x* and *y* as *my* + *x*;
and from this, we can recover the individual values *x*
and *y*.
We recover the values by dividing by *m*: the value of *y*
is the quotient, and the value of *x* is the remainder.
We can repeat this to hold as many values as desired: the value
*y* may be a combined value as well, and so forth.
If we have several values *x*_{1}, *x*_{2},
..., *x*_{k} to store, which never reach value
*m*_{1}, *m*_{2}, ...,
*m*_{k}, the range of the combined value is
between 0 and
*m*_{1}*m*_{2}...*m*_{k}.

Note that the value *m* must *exceed* the maximum possible
value for *x*.

We will represent the set {*a*, *b*}, and hence the edge from
location *a* to location *b*, by the value 1000*a* +
*b*: {1,3}, for example, would appear as 1003.
We can easily recover the individual values by taking the integer
portion of the quotient after dividing the combined value by 1000,
and the remainder after dividing the value by 1000.

Is there anything more to plan? Apparently not; time to code, then!

[ Previous page | Top of page | Next page ]

Copyright © 2002 Brian Hetrick

Page last updated 10 April 2006.