The History of Flight and Some Mathematical Application

by
Hermine Smikle


Contents:

Teaching in New Haven: Table of Contents | Yale-New Haven Teachers Institute


I. Introduction

Today’s mathematics curricula and education goals should reflect the importance of mathematical literacy. Therefore this unit will attempt to reflect some of these new directions both in the content and the method of teaching.

The new direction can be summarized in the following statements:1

Students should learn the value of mathematics.
To reduce math anxiety, students should become more confident in their abilities to do the subject.
Students should become more confident and develop skills as mathematic problem solvers.
Students learn to communicate and reason mathematically.
Students should be able to think of diverse ways to solve a problem.
The mathematics curriculum should also reflect the mathematical needs of the next decade. Today’s students will be working with tools and in an environment that will need an understanding of more complex thinking skills. Teachers and curriculum planners must understand and anticipate the changing needs of industries and the society.

Henry Pollak2 (1987) summarized the mathematical needs and expectations for employers in the industrial sector of the future.

1. The ability to set up problems with the appropriate operations.
2. Knowledge of a variety of techniques to approach and work on problems.
3. Understanding the underlying mathematical features of a problem
4. The ability to work with others on a problem.
5. The ability to see the applicability of mathematical ideas to common and complex problems.
6. Preparation for open problem situation since most real life problems are not well formulated.
7. The belief in the utility and the value of mathematics.

II. Rationale and General Objectives of the Unit

The study of aerodynamics has assisted in providing the world with the most efficient mode of transportation. As a result of these achievements a large industry has arisen that needs to be kept supplied with qualified personnel both skilled and unskilled.

Most of the high school curriculum today has placed great emphasis on the four-year-college-bound student; but there is a growing demand for workers who are literate in mathematics in all sectors of the society.

This unit in aerodynamics will attempt to find the mathematical concepts that are essential to flight with special interest in the concepts that relate to path problems.

The development of this unit will be justified by the emphasis placed on making mathematics relevant, practical and meaningful to the student, thus providing them with answers to “Why do I need to do this?” or “Where in the real world would I ever use this?”

The theme behind the development of this unit is to present mathematical concepts that are not usually taught in the curriculum of students that are labeled low achievers, and to present these topics using flight as the major focus.

It has been a challenge to teach students in the lower mathematics classes. These students have been accustomed to failing the traditional topics such as fractions and decimals; and in high school they find mathematics difficult, boring and impractical. They have been kept out of the mainstream of mathematics because of their inability to pass the proficiency tests.

In my quest to present these students with mathematics concepts that would otherwise be outside their curriculum, I have attempted to present these topics differently by relating them directly to flight, thus forging a connection between the historical concepts and some of the mathematics that can be applied to it.

The teaching approach would be to expose these students to the readings of the historical development. This could be done as a class project or individual students could do research on different areas. The mathematical concepts could be introduced from the view point of students planning a flight in an aircraft then considering the logistics of the flight. Navigation, and spherical geometry could be applied here with the theme: “Planning a Journey.”

The introduction of graph theory could be introduced as a tool to solving problems that relate to the activities that present themselves during the flight: loading and unloading the aircraft; the job activities of the air hostess; even the time line of activities for passengers. Students could brainstorm and develop their own problems.

I share the beliefs presented in the Mathematics Standards prepared by the N.T.C.M.,3 that mathematics should be made relevant, that its application should be shown across subject areas, and that all students can be successful in mathematics.

General Objectives of the Unit

The unit will be designed to help students:
a) To acquire knowledge about the historical development of the industry.
b) To develop the ability to apply their knowledge in math to the task of problem solving.
c) To apply specific graphing skills to solving problems.
d) To use Graph Theory to solve problems related to paths.
e) Introduce students to Spherical Geometry as a link between Geography and Geometry.

III. Historical Overview of the Development of Aircraft4

A. Developments before the Wright Brothers

Men had always wondered why it was impossible for them to attain the art of flying. They questioned the ability of birds to fly. As a result of their fascination for flying, stories of man’s ability to fly have been embedded in the Greek myths of Daedalus and his son, Icarus.

The stories were centered around his escape from the island of Crete where he was imprisoned. They described how they fastened wings with wax to their bodies and flew through the air; Icarus flew too near the sun, the wax melted and he fell to his death in the sea.

Man’s idea about flying was thus centered on the imitation of birds; as a result various medieval people fastened wings to their bodies and tried to fly. Many fell to their most unfortunate fates.

(figure available in print form)

Finally men gave up the idea of strapping a pair of wings to their bodies to enable them to fly. It was replaced by the concept of wings which were flapped up and down by some mechanical mechanism. Powered by some type of human arm, leg or some other body movement. These were the ornithopters.

Leonardo da Vinci designed a number of these. Above is a sketch of his ornithopter.5

Ornithopters did not accomplish any successful flight; therefore they made no contribution to the advancement of flight.

It was not until November 21, 1783 that human efforts to fly were accomplished. This was done when the balloon flown by the Marquis d’Ariandes went up in the air and flew 5 miles to Paris.

(figure available in print form)

This balloon was inflated and buoyed up by hot air coming from a fire beneath it.

The Montgolfier brothers thought of the lifting power of hot air and its ability to lift a person from the earth. They experimented with different materials (bags made with linen in which hot air was trapped). They had several public demonstrations and fi nally the flight of November 1783.

The flight served its purpose by triggering the public’s interest in the ability of man to fly.

It was not until the advent of Sir George Casley (1773-1857) that the concept to include a fixed wing for generating lift and a separate mechanism for propulsion was originated. He envisioned paddles and a horizontal and vertical tail for stability. These ideas were inscribed on a silver disc.

(figure available in print form)

With these ideas Cayley introduced the concept that lift was different from propulsion and therefore set the stage for the developments that took place later.

He devoted a life of study to aerodynamics. In 1804 he built a whirling arm apparatus for testing airfoils; this was a lifting surface mounted on the end of a long rod, which was rotated at some speed to generate a flow of air over the airfoils. This is analogous to the wind tunnels today. It was an important development because it allowed the measurement of aerodynamic forces and the center of pressure on the lifting surface. These developments can be considered the first step in aerodynamic testing.

In 1804 he designed, built and flew a small model glider.

(figure available in print form)

He documented his developments in a paper entitled “On Aerial Navigation.” This was published in 1809. In 1849 he built and tested a full size airplane by which a ten year old boy was carried along and lifted several meters from the ground.

He had the concept of stacking several wings on top of each other (biplanes and triplanes); he had the fear that a single wing would fail. This idea was carried down into the twentieth century. It was only in the 1930s that the monoplane became the dominant airplane configuration.

(figure available in print form)

It was sometime in 1853 that Cayley built and flew the world’s first human-carrying glider. The configuration is unknown; it could have been a triplane and looked like the boy carrier.

After Cayley’s death in 1857, not many inventions took place for the next fifty years.

Other landmark discoveries

William Samuel Henson (1812-1888): he published a design for a fixed wing airplane powered by a steam engine driving two propellers. This was called the aerial steam carriage.

This design was a direct result of Cayley’s ideas and research in aeronautics.

John Stringfellow, a friend of Henson, built several small steam engines and attempted to power some model monoplanes off the ground. He was not very successful. His most recognized work appeared in the form of a steam powered triplane. His triplane was the main bridge between Cayley’s work and modern aeronautics.

Felix Du Temple (1857-1858) flew the first successful powered model airplane. It was a monoplane; it had wings and was powered by clockwork.

The second airplane (1874) had the first powered takeoff by a piloted full sized airplane. It had wings and was powered by hot air engine. The machine was launched down an inclined plane.

Alexander F. Mozhaiski was a Russian; in July 1884 he designed an aerial steam carriage. It was launched down a ski ramp and flew for a few seconds.

These attempts did not satisfy the criteria of sustained flight, but could be considered assisted powered takeoffs.

B. The age of the glider

Otto Lilienthal was one of the giants in aeronautical engineering. He designed and flew the first successful controlled glider in history.

Because of his interest in flight, he studied the structure and types of birds’ wings and applied this information to the design of mechanical flight.

In 1889 and again in 1890, he designed and flew gliders, but both were unsuccessful. In 1891 he had his first successful glider flight from a hill in Germany.

The general configuration of this monoplane glider was one of a birdlike platform of the wing. He used chambered airfoil shape on the wing and used vertical and horizontal tail planes in the back for stability. These machines are the forerunners of the hangliders today. Flight control was exercised by shifting one’s center of gravity.

Lilienthal can be classified as an airman in contrast to those who were called chauffeurs. The distinction was drawn between those who were concerned with thrust and lift, and the airmen who were concerned with flight in the air.

Lilienthal made about 2000 successful glider flights. His aerodynamic data were widely read. He died during a glider flight in Germany on August 9, 1896.

Percy Pilcher studied with Lilienthal and under his guidance made several glides. He could be classified as an airman; he understood the need for understanding natural flight, before engaging in machine powered flights. He built a machine called the Hawk in 1896. It was powered by a 4 hp engine weighing 40 lbs. He died while flying this machine.

C. Aeronautics in the United States

Most of the advances that had been made in heavier than air flying machines were made in Britain and in Europe. These developments were taking place during the time when the United States was more concerned with land expansion and the consolidation of a new government; aeronautical developments had no impact.

This interest in flying was taken by Octave Chanute (1832-1910). He collected and studied all the aeronautical information available. He later published his book Progress in Flying Machines. In his book he summarized all the important progress in aviation. He could be considered the first aviation historian.

He designed hang gliders and produced a biplane glider. He bridged the gap between Stringfellow’s triplane and the successful powered flights of 1903.

Samuel Pierpont Langley (1834-1906) designed and built a series of powered aircrafts, which resulted in piloted flights in 1903.

Langley followed in the tradition of Cayley and therefore built a large whirling arm, powered by a steam engine. This he used to make tests on steam airfoils.

In 1896 Langley was successful when one of powered models made a free flight of 3300 ft and later another flew over 3/4 mile. These “Aerodromes,” as he called them, were tandem winged vehicles, driven by two propellers between the wings that were powered by a 1 hp steam engine.

After studying Stringfellow’s work he set out to design a better engine. In 1898, the war department commissioned him to build a machine for passengers. He decided that a gasoline fueled engine would be best for use on an aircraft. A 52.4 hp engine result ed from his efforts. He used a 3.2 hp gasoline fueled engine to have a successful flight with a 1/4 scale model. With this encouragement he started to design a full scale airplane. He mounted this aircraft on a catapult in order to provide an assisted tak e off; this contraption was placed on top of a houseboat on the Potomac River.

On October of 1903, with his companion Charles Manley at the controls, he made his first attempt at flying. The aircraft fell into the water soon after launch. They tried again on December 8, 1903 but had the same consequences.

Langley abandoned his attempt at human flight after his failures and the criticisms from the press.

Critics of Langley classified him as a chauffeur because he had not paid much attention to the aspect of flight control; he did, however, leave a legacy by the contributions he made to aeronautics.

D. The Wright Brothers

The Wright brothers drew on the rich heritage in aeronautical experiences left them by their predecessors. They became interested in aviation after the flight of Otto Lilienthal in 1896. They took up the study of birds as a guide to mechanical flight; fro m their study they concluded that birds regain their lateral balance when partly overturned by a gust of wind. This emerged as the single most important development in aviation history, the use of wings’ twist to control airplane in rolling motion. They c oined the phase “wing warping.”

They read all the available literature on the advancements in aeronautics, then set out to experiment with wing warping. To test this concept they built a biplane with a wing span of 5 ft. that was controlled from the ground with strings. This concept worked.

Encouraged, the Wright brothers decided to test this concept, but not before gaining experience as “airmen.” They made their first 17 ft wing span by September 1900 and flew it from Kitty Hawk on October of that year.

With this success they proceeded to build a second glider from their new headquarters at Kill Devil Hills 4 miles to the south of Kitty Hawk; it was tested in July and August of 1901. This new glider was larger than the previous one. It had a wing span of 22 ft.

The Wrights were very suspicious of the existing data from the literature, especially those generated by Lilienthal and Langley. They built their own wind tunnel and did their own investigations. From these researches they built the number three glider. This was flown in December 1902 and provided much information on the impact of wind tunnels.

During 1902, they made more than 1000 perfect flights and set a distance record of 26 seconds. The brothers had become experienced and skillful pilots, and with all the theoretical and practical problems solved, they felt that they could construct a machine whose stability and control in the air depended on the pilot’s skill. The only diffficulty was to find an existing engine capable of powering the aircraft. They could not find such an engine; therefore they designed and built their own. It was 12 hp, water cooled, and weighed only 200 lbs. They also built their own propeller; thus they produced their first powered machine the “Flyer” in the summer of 1903.

They returned to their camp to find it in disarray. They repaired the number 3 glider and practiced. Finally overcoming all setbacks (weather, mechanical breakdowns), they were ready to test the Flyer. It was a biplane of 40 ft with a wing area of 510 square feet and used a double rudder behind the wings and a double elevator in front of the wings.

With conditions favorable, they called five witnesses, and with a camera set up for pictures the Flyer made its first historic flight. (Orville was at the controls.)

They did not stop with Flyer 1. In May 1904 they flew their second powered machine, Flyer 2. They made improvements with a smaller wing camber. By 1905 Flyer 3 was ready. It was described as the world’s first practical powered aeroplane, justified by the sturdiness of its structure. With their combined contribution, research and inventions, the world was on the threshold of a new form of vehicle for public transportation.

E. The emergence of the aircraft as a valuable means of transportation

During 1909 the aeroplane had become accepted as the world’s new practical vehicle. Louis Bleriot’s crossing of the Channel on July 25, and the first air meeting at Rheims in August were significant signs. With the Wrights’ achievements and techniques to follow, European airmen came into their own; so during the first half of the 1900s there was a growing number of aviators, designers and amateurs, and the forms of their aircraft began to multiply. The dominant types of aircraft became more efficient and reliable. The message of powered flying began spreading over the world and the beginnings of an aircraft industry, as well as governments’ concerns with aviation, became evident.

There were some diffficulties to be overcome to make the aeroplane more efficient.

l. The development of an engine with enough horse power to lift an aircraft off the ground. This was solved with the development of gasoline fueled internal combustion engines (the Wright brothers were pioneers in this area). The automobile industry then led the development of new engines.
2. The development and the search for aeroplanes that could fly faster and higher. This problem was solved partly by the introduction of competitions; this prompted and advanced development of high speed aircraft. One notable competition was the Schneider race.

Military aviation became a serious concern of leading European nations. As a result military and naval flying schools were established.

When the First World War was declared, the aeroplane’s duties were as aerial intelligence agents or scouts for visual and photographic reconnaissance. During the war years the aircraft industry in Europe and the United States expanded from a handful of machines in 1914 to 3300 in use by 1918. It also provided many jobs, from a few hundred in 1914 to nearly 350,000 workers in 1918.

After the war there was more technical progress made and the acceptance of the importance of flying was extended in the public’s mind, and air transport became a means of public transportation. As Cayley predicted, “We shall be able to transport ourselves and our families and their goods and chattels, more securely by air than by water.”

With the far reaching developments of combat aircraft, and the various equipment for flying and communicating, comparable developments were taking place in the aircraft for civil transport.

After the war years, the non-military sphere of flying saw the most dramatic developments. In 1919, the first air transport with scheduled airlines started in Europe. The first civil airline for passengers began in Germany February 8, 1919, with service between Berlin, Leipzig and Vienna.

The machines used in France, England and America as transport planes were wartime bombers adapted to passenger planes.

One important landmark in the air transport and private flying was the solo flight direct from New York to Paris on May 20-21, 1927. It helped to transform the entire travel industry and made the public more air-minded.

It was in the United States that the first modern type airliner was the Boeing 247, flown in February 1933. The second was Douglas DC-1 flown in July 1933.

These are a few of the airliners that emerged as a result of the developments in aerodynamics and the demand for passenger planes.

With the advent of the Second World War, there were enormous developments in aviation and in aeroplane engines and all the types of equipment used in flying. This period saw the jet propelled aeroplane and the production of helicopters and long ranged rockets. After the war the industry turned its attention to transport production.

The leader in developing light and medium transports was the United States. Aircraft were developed that set the style for modern heavy transports with the Douglas Dakota (DC-3). This aircraft monopolized the traffic on the world’s long haul airlines after the war.

Following is a list of the aircraft that were developed and their passenger capabilities.

1. Douglas Dakota (DC-3), USA
2. Junkers Ja 52, Germany
3. Douglas DC-4 Skymaster (Military C-54): February 1942. It had a crew of six and 42 passengers.
4. Douglas DC-6: February 1946, into airline service 1947.
5. Lockheed 049 (C-69): Jan 1943, carried 52 passengers.
6. Stratocruiser: November 1944.
The preceding pages do not cover all the developments of the types of aircraft that came into existence, but they do show that the stage was set for the use of the aircraft as a public transport system. The need was met as a result of the inventions that arose, so that the aircraft could be viable in the war years. After that, technology was directed towards passenger travel.

The years after the wars also saw the research in aerodynamics directed to rocketry and the aerospace industry.

From the developments described in the previous pages, one can point to many fruitful instances of applied mathematics. The following sections will attempt to present some of the mathematical topics that can be brought to bear on the history of flight.


IV. The Mathematical Application

A. Geometry

1) Introduction to Vectors to Represent a Journey

If a displacement has taken place, this movement can be written as a displacement vector.

The position of the plane in the picture relative to the airport can be described as 5 miles, bearing 053 degrees.

(figure available in print form)

The position of the plane could be described as 4 miles east and 3 miles north. Instead of saying 4 miles east and 3 miles north we could write (4/3). This is a vector representation of the position of the plane. The distance to the east is written first followed by the distance to the north.

If the plane moves from position S to position Q and the movement is 2 miles east and 6 miles north the total journey can be represented as a sum (4/3) + (2/6) = (6/9). Vectors can be added by adding the top components 4 + 2 and the bottom components 3 + 6.

2) Angles and Bearings

Bearings are measured from the north line, the line or axis about which the earth rotates. It cuts the surface of the earth at what are called the north and south poles. The pole star is almost on this line and so appears to be fixed in the heavens, while other stars seem to rotate about the axis. The pole star gives a fixed direction from which navigators used to set their course. Today the magnetic compass, which points in approximately the same direction, is used to set a course.

To set the bearing

i) always start from the north line and
ii) always measure the angle clockwise.

The following example will be used to demonstrate how to draw a model of a journey.

A pilot on an aircraft made a two stage journey.
Stage A: 500 miles, bearing 060 degrees
Stage B: 300 miles, bearing 150 degrees

1st step: Draw the north line (NA), and measure the 060 degrees angle clockwise from the north line. Draw a line to represent 500 miles from the point A to B. This represents the first leg of the joumey.

2nd step: At point B draw another north line, measure the angle of 150 degrees, and draw the length 300 miles.

(figure available in print form)

If the pilot had flown from A to C, we could measure the bearing of C from A and measure the length of the line segment AC. The stages of this journey can also be written as a displacement vector. (500, 060 degrees) followed by (300, 150 degrees).

(figure available in print form)

3) Navigation and Spherical Geometry

The following topic is being introduced with the intent of providing an enrichment topic for students in the higher mathematics courses, since some experience with trigonometry, logarithms and rotational symmetry would be required.

There are several methods of navigation: Pilotage is the method of flying an aircraft from one point to another by the observation of landmarks either already known or recognized from a map. This method has limitations, because if the flight is over poorly mapped country, over large bodies of water, or at night when visibility is poor, it is difficult to use the landmarks. This method is most efficient when used with other forms of navigation.

The method Dead Reckoning is the basic method of navigation. It uses known or established factors such as wind direction, wind velocity, and air speed to compute a position from a known position. Lindbergh used Dead Reckoning on his flight from New York to Paris.

Radio Navigation is method of directing an aircraft from one point to another by radio waves. Its major feature is that one does not wait to see the ground to make approaches and landings.

Celestial Navigation is the oldest method of navigation. This is the determination of an aircraft by the observation of the celestial bodies to determine position.

Using a globe is the only accurate means of representing the spherical surface of the earth.9 To make a mathematical model of the earth choose the diameter NS passing through the north and south poles as axis of rotation. If O is the midpoint of NS, and OQ is perpendicular to NS then the locus of Q is the equator.

(figure available in print form)

To make a two-dimensional diagram of a sphere, the equator and the parallels of latitude and the meridians are drawn.

4) Latitude and Longitude. The coordinates used to describe points on the Earth’s surface.

The position of a point A on the surface can be determined by stating:

a) Which circular section perpendicular to NS contains A.
b) Which position of the semi-circle rotating about NS contains A.

These pieces of information are given by specifying

i) the latitude and
ii) the longitude of A.

Figure III shows the equator and the circles, or parallels of latitude 60 degrees N and 50 degrees S. The range of latitude is from 0 degrees to 90 degrees north or south of the equator.

(figure available in print form)

Figure IV shows the equator, the Greenwich meridian NGS and the semicircles, or meridian of longitude 40 degrees W and 20 degrees E. The range of longitude is from 0 degrees to 180 degrees East and West of Greenwich.

Figure V shows point A with latitude t degrees N, and longitude g degrees W.

(figure available in print form)

Figure VI shows the point P with latitude 60 degrees N and longitude 50 degrees W. Figure VII shows the point Q with latitude 30 degrees S and longitude 50 degrees E.

(figure available in print form)

The solution of right spherical triangles

A spherical angle is formed by intersecting arcs of two great circles. The three important properties of spherical triangles are:
a) the sum of the lengths of any two sides exceeds the length of the third side;
b) the sum of the lengths of the three sides is less than 360 degrees;
c) the sum of the angles is greater than 180 degrees but less than 540 degrees.
To find the great circle distance between two points A and B, the triangle of reference is constructed as follows:

i) The great circle joining A and B form one side of the triangle;
ii) The meridians through both A and B form the other two sides.

(figure available in print form) Two such triangles are formed and either can be used to obtain the great circle distance from A to B. Example: Suppose A has latitude 60 degrees N, longitude 55 degrees E, and B has latitude 60 degrees N, longitude 13 degrees W. The length of arc AB can be calculated as follows.

(figure available in print form)

* The radius of a circle of latitude t degrees = R cos t degrees where R the radius of the earth is 6400 km.

(figure available in print form)

If a plane or ship follows a great circle path, its course is the angle the path makes with the meridian of the ship and is measured from north through east to the path of the ship.

B. An Introduction to Graph Theory

The concept of drawing a graph to represent information has been used extensively in mathematics. These ideas have been used to plot the routes of the mailman, and of various delivery companies. These ideas are also extended to the airline industry. They have been used in determining routes between cities, and in providing a time line for doing various activities that enable the efficient disembarkation and unloading of baggage on an aircraft.

Just as model aircraft are used to represent the real thing, models in this section will be used as a representation of something else. The model or graph will be used to give us an idea of what reality is.

A graph is a finite set of points, called vertices, together with a finite set of curved or straight connecting lines called edges, each of which joins a pair of vertices. These vertices and edges satisfy the condition that no edge begins or ends at the same vertex. Graphs without edges are called null graphs.

(figure available in print form)

The figure in c) is not a graph because it violates the condition that no end may join a vertex to itself. When a graph has two or more different edges joining the same pair of vertices, these edges are called multiple edges.

(figure available in print form)

The edge of a graph can be identified by using a letter to name it, and the vertices (endpoints) can also be named. The edge E can be named (X1, X2).

Graphs are important tools in representing a vast number of real world problems. Graphs that are used to represent the layout of streets are called street networks. In this instance the edges of the graph can have a direction indicated by arrow. These graphs are called digraphs. A digraph is a finite, non-empty set of points called vertices, together with some directed edges joining these points. These edges are subjected to one restriction. The initial and terminal vertices of a directed edge may not be the same.

(figure available in print form)

1) Graphs and Matrices: Matrices from Drawings

Matrices are presented as a means of storing information in which the position of the information is very important. The direct route matrix is used since it enables us to predict properties of more complicated networks without reproducing them.

The figure shows a network of roads:

A direct route is the journey which does not pass through another endpoint.

One way of describing a direct route linking endpoints is to use an arrow diagram.

(figure available in print form)

Another way of describing this is to use a table where zero means no direct route, 1 means 1 direct route, 2 means two direct routes, etc.

(figure available in print form)

The rectangular array of numbers from the table can be represented in a matrix:

(figure available in print form)

Instead of talking about endpoints or vertices and edges these ideas can be applied to real life situations. The vertices or endpoints can be referred to as towns or cities and the edges can be called routes or roads.

The diagram shows a network of roads between several towns with their direct routes.

(figure available in print form)

One way of showing the direct routes linking the towns is to draw the arrow diagram.

(figure available in print form)

Directed Maps: A map of a one-way system is called a directed map because arrows are placed on the roads to show in which directions to go.

(figure available in print form)

The matrix of a directed map is different from the matrix of an undirected map since it is not symmetrical and it is also possible to have odd elements on the leading diagonals.

2) Finding the Shortest Path

A graph or network is defined by two sets of symbols, nodes and arcs. Nodes are the set of points or vertices, arcs consists of an ordered pair of vertices and represents a possible direction of motion that may occur between vertices.

(figure available in print form)

Arcs can be considered as one-way roads. For shortest path problems it will be assumed that each arc in the network has a length associated with it. The problem of finding the shortest path is the minimum length from one node to any other node in the network.

Dijkstra’s Algorithm:10 This algorithm for finding the shortest path between a pair of nodes requires that all the arcs in the network have non-negative arc length.

The algorithm uses this method:

1. Designate node one as the starting point.
2. Find the node closest to node one.
3. Find the second closest node to node one.
4. Find the third closest node to node one.
5. Continue until all the paths are used.

Let us use this method in the following example.
(figure available in print form)

The distances can be summarized in a table:

4 + 2 = 6

PATH LENGTH OF PATH
1. Determination of the second closest node to node 1.
The arc (1,2) 4
The shortest path from node 1
to node 3 + arc (3,5) 3 + 3 = 6
2. Determination of the third closest node to node 1
The shortest path from 1 to 3
+ arc (3,5) 3 + 3 = 6
Shortest path from 1 to 2
Shortest path from 1 to 2
+ arc (2,5) 4 + 3 = 7
3. Determination of the fourth closest node to node 1
Shortest path from 1 to 2
+ arc (2,4) 4 + 3 = 7
Shortest path from 1 to 5
+ arc (5,6) 6 + 2 = 8
4. Determination of the fifth shortest path from node 1
Shortest path from 1 to 4
+ arc (5,6) 7 + 2 = 9
Shortest path from 1 to 5
+ arc (5,6) 6 + 2 = 8
Summary of shortest path
Nodes Closest nodes to Node 1 Path from Node 1 to the nth closest node Length of path
0 1
1 3 1-3 3
2 2 1-2 4
3 5 1-2-5 or 1-3-5 6
4 4 1-2-4 7
5 6 1-3-5-6 or 1-2-5-6 8
The shortest path from node 1 to node 6 is either 1-2-5-6 or 1-3-5-6; both have length 8.

The digraph can also be used to solve complicated problems. Consider this problem: We wish to minimize the time an aircraft spends at an airport. The component activities can be placed in a table:

A1 Disembark passengers 1/2 hr.
A2 Unload baggage 1 hr.
A3 Clean the plane 1/2 hr.
A4 Take on new passengers 1 hr.
A5 Load new baggage 1 hr.
We could simply sum all the numbers of hours but some of these tasks can be done simultaneously and some operations are independent of others. A good way to proceed is to draw a model called “The Activity Analysis Digraph.”

An Activity Analysis Digraph is constructed in the following way.

1. Represent each activity by a node A1, A2, . . . An with the time required for the activity.
2. Create two additional nodes each labeled with the number zero, one representing the job’s beginning and the other the job’s end.
3. Draw a directed edge from one activity to the next only if the first activity precedes the second.
Now that we have drawn a model, the problem is to determine the shortest time for the completion of the whole job. We can proceed as follows:
1. Denote time t measured from starting point B; t = 0
2. Rephrase the problem; given an Activity Analysis Digraph for a project. What will be the shortest time at which E, the end, can be completed?
3. Add the times for all activities on the path up to but not including E (There may be more than one path from B to E).
The critical path is the path of longest time from B to E. To determine the most efficient schedule in the problem is the critical path B, A2, A4, which has length of two hours and this gives the minimum time for the whole job to be completed.

To explain, the activities A1 and A2 can both be started at time zero (passengers can disembark and luggage be taken off at the same time).

The activity A3 cannot be started until all the passengers are taken off; the activity A4 cannot be started until A3 is completed but can be made to overlap with A5; we cannot arrive at E until both A4 and A5 are completed.


V. Sample Lesson Plans

Sample Lesson Plan 1

Topic Introduction to Graph Theory.

Objectives Students will be able

a) to define a graph, and a null graph.
b) to differentiate between graphs, null graphs and drawings that are not graphs.
c) to identify the parts of a graph.
d) to identify a digraph.
e) to use a graph to represent a problem.
Prerequisites
a) Plot points
b) Draw straight lines.
Skills and Concepts Presented
a) Plotting and joining points
b) organizing information.
Developments
1. Develop a dialogue that would show the students the importance that drawing a diagram (in this case graphs) has in solving problems.
2. Point out that graphs are considered as models and therefore can be used to represent a situation.
3. Introduce the airline problem from the content.
4. Introduce and explain each step:
i) how to organize the information in a table.
ii) introduce vertex or nodes and edges.
iii) give examples of null graphs, graphs, and drawings that are not graphs
5. Formally define graphs and digraphs.
6. Present drill and practice for students to use the information discussed.

Possible Problems for Discussion
1. In the following sketches identify the vertices and the edges.
(figure available in print form)
2. Identify each of the following as graphs or not a graph.
(figure available in print form)
3a. Draw a complete graph with six vertices.
3b. How many edges are there?
4. Draw a null graph with eight vertices.
5. Draw a graph to show the friendship relation among four individuals.

Extension Activities
1. Have students suggest possible problems from which they can produce a graph.
2. Have students draw a digraph of friendship relation in the classroom.
3. The following are dependent statements (implications exist between them):
a) The Wright brothers’ first flight.
b) Better aircrafts invented.
c) More jobs provided.
d) Standard of living improved.
e) More people take trips on airplanes.
Draw a digraph to show the relationship between the statements.

Sample Lesson Plan 2

Topic The airplane problem revisited.

Objectives Students will be able
a) to draw a model for the problem.
b) to identify a critical path.
c) to find a solution for the problem.

Prerequisites
a) to draw a graph or a digraph.

Skills and Concepts Presented
a) Organization of data.
b) Constructing an Activity Analysis Digraph.
c) Finding the critical path.

Developments
1. Review nodes, vertices and edges.
2. Review drawing graphs.
3. Re-introduce the airplane problem.
4. Organize the information in a table.
5. Discuss the reasons for a starting and ending position.
6. Introduce the method of making “The Activity Analysis Digraph.”
7. Draw a graph from the information (have students suggest possible order in which the activities can be done).
8. Introduce the words critical paths. Discuss all the possible paths.
9. Have students suggest possible answers.

Extension Activities
1. Have students suggest tasks that they would like to represent using an activity digraph.
2. Draw an activity digraph for a person getting ready to go on vacation.
3. Draw an activity digraph for the activities of the air hostesses during the flight.
4. A group of girls decided to cook lunch for some friends. The activities were:

A. Clean house 30 mins
B. Decide on menu 15 mins
C. Purchase food 60 mins
D. Cook food 50 mins
E. Set table 10 mins
F. Place cooked food on table 5 mins

Draw an activity analysis digraph for this job. Find the shortest possible time that these tasks will take.

Sample Lesson Plan 3

Topic Vectors as a means of representing a journey.

Objectives Students will be able

a) to read a network.
b) to identify direct routes.
c) to identify direct routes in an arrow diagram.
d) to use a table and a matrix to show direct routes.
Prerequisites
a) The ability to read and draw graph and digraphs.
Skills and Concepts Presented
a) Drawing and reading networks.
b) Identifying direct routes.
c) Drawing arrow diagrams.
d) Representing direct routes on a table.
e) Writing simple matrices.
Developments
1. Review drawing graphs.
2. Discussion of the network of streets in their towns.
3. Use a map of flights between cities to show a network (ads in newspapers showing connections).
4. Use a simple network to show key points
a) towns represented by a dot (vertices)
b) routes represented by edges.
5. Define direct routes. Have students identify direct routes on map shown.
6. Introduce the arrow diagrams as one way of representing direct routes.
7. Introduce the table as another way of representing routes.
8. Introduce the matrix as a short cut to writing the routes.
9. Discuss and define the matrix.
10. Discussion and Questions from the matrix.
a) Deduce important features from the matrix.
i) The leading diagonal.
ii) Is the matrix symmetrical with respect to the leading diagonal?
iii) The diagonal in a directed matrix versus an undirected matrix.
b) Provide drill and practice.
Sample Problems
1. Copy the figure and draw the arrow diagram.
(figure available in print form)

2. Complete the table.

(figure available in print form)

Questions

1. Why are there three routes from A to C?
2. Why are there 2 routes from A to B?
3. Show the leading diagonal.
4. Is the table symmetrical about the leading diagonal?
Extension Activities
1. Find the Matrix which describes these networks:
(figure available in print form)
2. Find the matrices which describe the following network, then write a statement to describe the matrices.
(figure available in print form)
3. Given the matrix, can you draw the network? (work backwards)

Sample Lesson Plan 4

Topic Introduction to Vectors as a means of representing a distance.
Objectives Students will be able to
a) Describe a position relative to a point.
b) Write the coordinate of a point in the coordinate plane.
c) Write the coordinate as a vector.
Prerequisites
1. To plot points in the coordinate plane.
2. To use a protractor to measure an angle.
3. To draw to scale.
Skills and Concepts Presented
1. Drawing angle bearing.
2. Writing coordinates with distance and angles.
3. Plotting a position in the coordinate plane using direction East and North.
4. Reading and writing the position as an ordered pair (length, angle) and as a vector (East, North).
Development
1. Review angle measure (bearing).
2. Introduce the use of a scale (model drawing).
3. Using the picture in the content, have students give the position of the boat using the format (length, angle). Have students draw other positions using variation of the angles and lengths.
4. From the coordinate system shown have students give the position of the ship using ordered pairs (East, North).
5. Introduce Vectors as a means of writing a displacement.
6. Work with students in writing the displacements. For example, suppose the ship moved from position S and its movement is (2/6), then its position relative to the port will be (4/3) + (2/6) = (6/9). Have students represent this position on their gra ph paper.

Sample Problems For Class Discussion

1. Write down the vectors that represent the following journeys:
a) from A to B b) from C to D c) from E to F d) from G to H.
(figure available in print form)

2. The following shows a map of an island:

(figure available in print form)

a) Write the stages of the journey using vectors.
b) How many stages are there?
c) Add up the vectors of the journey.
d) Show the journey from Port Charles to Jacob’s point via the lighthouse.
e) Give your partner some vectors and have him (her) give your destination.
Extension Activities: Using Bearings and Scale Drawing
1. A pilot wants to fly from city C to a city B, a distance of 1200 miles. The city B is on a bearing of 082° from C. Due to a pending storm, the pilot makes a detour and refuels at city A. The distance of A from C is 700 miles and the bearing is 175 degrees. Find the distance of A to B, and the bearing the pilot has to take.
2. (500 miles, 090°) is a journey taken by an aircraft. Find the single journey represented by (500, 090 degrees) followed by (375, 250 degrees).
3. A pilot is to make a round trip from New York calling at three airports (Dulles, Washington International; Atlanta, Georgia; and Cleveland, Ohio.)
a) Plot the path of the aircraft. (Use an atlas to get the bearing).
b) What bearing must the pilot take to return straight to New York from Cleveland?
4. Use any three cities of your choice (select some foreign cities).
a) Draw a graph of the path between them.
b) Give the bearing the pilot will take for the return trip.
Latitude and Longitude
1. Draw a large sketch of the earth, marking in the center, the North and South poles, the equator, and Greenwich meridian.
2. On a sketch of the earth draw in the following.
a) the 50 degrees N circle of latitude.
b) the 30 degrees W longitude line.
c) the 60 degrees E longitude line.
d) the point A with latitude 40 degrees N and longitude 30 degrees W.
e) the point with latitude 20 degrees S longitude 10 degrees E.
3. Use a map to locate various cities and write their latitude and longitude as a vector (latitude, longitude).

Notes

1National Council of Teachers of Mathematics, “Curriculum and Evaluation Standards for School Mathematics,” 6-7.

2National Council of Teachers of Mathematics, “Curriculum and Evaluation Standards.”

3National Council of Teachers of Mathematics, “Curriculum and Evaluation Standards.”

4John D. Anderson, Jr. Introduction To Flight. Second edition. New York: McGraw Hill, 1985. This book gives a concise history of the development of flight, along with illustrations.

5This picture and others taken from Anderson, John D., Jr., Introduction To Flight. Second edition. New York: McGraw Hill, 1985, Chapter 1.

6This picture and others taken from Anderson, John D., Jr., Introduction To Flight. Second edition. New York: McGraw Hill, 1985, Chapter 1.

7This picture and others taken from Anderson, John D., Jr., Introduction To Flight. Second edition. New York: McGraw Hill, 1985, Chapter 1.

8This picture and others taken from Anderson, John D., Jr., Introduction To Flight. Second edition. New York: McGraw Hill, 1985, Chapter 1.

9C. A. Congleton and L. E. Broome, “A Module in Spherical Trigonometry,” School Science and Mathematics 80, 103-108. This article has presented the topic of spherical geometry in three areas. The article was written as an enrichment lesson for high school students that have trigonometry and possible calculus in their background.

10Wayne L. Winston, “Operations Research: Applications and Algorithms,” 314-317.


Bibliography

Mathematics

Congleton, C. A. and L. E. Broome. “A Module in Spherical Trigonometry.” School Science and Mathematics 80: 103-108. This article has presented the topic of spherical geometry in three areas. The article was written as an enrichment lesson for high school students that have trigonometry and possible calculus in their background.

Growney, Joanne Simpson. Mathematics In Daily Life. Making Decisions and Solving Problems. New York: McGraw Hill, 1986. This text presents different ways that students can learn to solve problems. It placed emphasis on using the graph as a tool for problem solving.

Malkevitch, Joseph and Walter Meyer. Graphs, Models, Finite Mathematics. Englewood Cliffs, New Jersey: Prentice Hall, Inc.

The School Mathematics Project. Books B, C, and D. Cambridge: Cambridge University Press, 1970. These books have presented the topic of network, matrices and vectors in a form that can be presented to any group of students. For examples and teaching guide the reader is encouraged to consult these books.

Scottish Mathematics Group. Modern Mathematics for School. Book 7. Glasgow and London: Blackie, 1966. 252-255. This book has presented a section in spherical geometry that is suitable for high school students.

Winston, Wayne L. Operation Research: Applications and Algorithms. Boston: P.W.S. Publishers, 1987. Chapter 7.

History of Flight
Anderson, John D. Jr. Introduction To Flight. Second edition. New York: McGraw Hill, 1985. This book gives a concise history of the development of flight, along with illustrations.

Deventer, Van C. N. An Introduction to General Aeronautics. Great Britain: American Technical Society, 1965.

Gibbs-Smith, Charles Harvard. Aviation: An Historical Survey. London: Her Majesty’s Stationary Office, 1970.

Wegener, Peter P. What Makes Airplanes Fly? History, Science and Applications of Aerodynamics. New York: Springer Verlag Inc., 1990.