Nets

views updated

Nets

Nets are two-dimensional representations of three-dimensional shapes. German painter Albrecht Dürer (1471–1536) probably had fishing nets in mind when he first used the term net to name these two-dimensional figures that may be "folded" to form three-dimensional solids. Some of the nets of a cube are shown in the figure below. Although they are each formed with six squares, they are different nets of a cube.

Each of these nets may be folded along its edges to form a cube.

Any solid with polygons for faces, called a polyhedron, may be unfolded to form a net. The polyhedron known as a square pyramid has several different nets. Some of them are shown below. Each of these nets can be folded up to form a square pyramid.

Nets are used to study the properties of various polyhedrons. A more valuable use of nets is in the field of networks. A network is a series of segments, or edges, that joins a given number of vertex points, also called nodes. The network below contains four vertex points and six edges.

The Bridges of Königsburg

The first mathematician to make a study of networks was Swiss mathematician Leonhard Euler (1707–1783). His interest in networks was sparked by the town of Königsburg, in Prussia. This town was built on the banks of the Pregel River, near two islands. Seven bridges joined the islands to each other and to the river banks. A favorite Sunday afternoon recreation for the citizens of Königsburg was to try to cross all seven bridges without walking across the same bridge twice. No one could find a route that would take them across each bridge, once and only once.*

*A path in which a person travels upon each segment once and only once is called a Euler Walk in honor of the eighteenth-century mathematician, Leonhard Euler.

The diagram below shows an eight-segment Euler Walk. Starting at Point C, the network may be toured by the path CBECDBAED. This tour travels every path once and only once. It also returns to the departing point. Such a path is called a "closed" Euler Walk.

When Euler began to study the problem of crossing the seven bridges of Königsburg, he made an abstract model of the seven bridges.

In Euler's simplified diagram, the riverbanks are represented by Point A and Point B, and the two islands in the river are represented by Point C and Point D. Each of the lines connecting the vertex points represents the bridges, seven in all. After some study of the problem, Euler concluded it was impossible to cross each bridge once and only once. The problem was with how the islands and the river banks were connected by the bridges. Euler used the term "valence" to describe how many paths or edges met at a single vertex point. In the diagram, Point D has a valence of 3, and Point C has a valence of 5.

Euler stated that the network formed by the bridges was impossible to travel so that each bridge was crossed only once, because of the valence of the points. Euler discovered that only networks with all even valance points or exactly two odd valence points could form an Euler Walk. The reason is that if a vertex has an odd number of paths terminating at that point, then one of the paths must be used to either start or finish a journey.

In Euler's simplified diagram, three paths terminate at vertex A. If the Sunday walk began at point C and continued to Point A, then to Point D, that would leave one path still terminating at vertex A. The walk that started at Point B would have to eventually stop at Point A in order to travel along the remaining path that terminates at Point A. If the walk began at Point A and traveled to Point B, then there would be two paths left terminating at Point A. Sometime later in the walk, one path could be taken to Point A, and the remaining path could be used to leave Point A. If there were five paths terminating at Point A, then the additional two paths could be used to arrive at, and then depart from, Point A. Thus any vertex with an odd number of paths could be used only as the starting point or as the ending point of an Euler Walk.

The Königsburg bridges formed four vertex points, each with an odd number of terminating paths. According to Euler it was impossible to travel across each and every bridge once and only once. Although Euler's discovery may be used to determine if it is possible to travel each path in a network once and only once, there is no algorithm for determining the shortest path that will travel across all the edges in a network with a large number of vertex points.

Euler's discovery has been helpful for a variety of real-life situations. The route for a snow plow, a postal deliverer, or a utility meter reader requires that all roads or paths in a network be traveled once. The best tour for each of these situations is a Euler Walk that maps a route over each road once and only once. But a Euler Walk is possible only if there are either two vertex points or no vertex points with an odd valence.

In 1875 an eighth bridge was built across the Pregel River, joining Point A and Point D in Euler's diagram. This combination of eight bridges left only two vertex points with an odd valence, Point B and Point C. The new bridge made it possible to cross all eight bridges once and only once. The resulting walk is called an open Euler Walk because it does not end at the starting point.

The Hamilton Walk. A network problem related to the Euler Walk involves visiting all the vertex points in a network once and only once. Irish mathematician William Rowan Hamilton (1805–1865) studied such networks. A path that visits all vertex points once and only once is called a Hamilton Walk. The network below shows a Hamilton Walk. One Hamilton Walk for this network is FCBAEDF. This path visits each vertex once and only once, and ends up at the starting point. It is called a closed Hamilton Walk.

Like the Euler Walk, the Hamilton Walk also has applications in real-life activities. A salesperson visiting various business sites or a delivery service vehicle follows a route that requires visiting individual locations or vertex points. However, as with a Euler Walk, it is not possible mathematically to determine the shortest Hamilton Walk for a large number of vertex points.