State University College at Buffalo

Department of Mathematics

Request for Course

I. Number and title of course.

Mathematics 370-APPLIED NETWORKS

II. Reasons for additon to the present curriculum.

A. To, provide a sound background in graph theory for applications in computer science and computational mathematics.

B. To provide experience in network applications to the various areas of decision making in social sciences and operations research.

C. To provide secondary education majors with experience in an emerging branch of mathematics which contains much material within the scope of secondary level students.

III. Major objectives of the course
A. To introduce the student to the most common graph configurations and more significant properties which may be satisfied by graphs.

B. To familiarize the Students with technical features of graphs which are important to computational mathematics.

C. To emphasize the applications of graph theory in social science and operations research, as well as in electrical networks.

IV. Behavioral Objectives.

The following is a minimal list. The student will be expected to:

A. Recognize common graph types of configurations and to be aware of distinguishing properties.

B. Recognize various independent graph theoretic properties which may or may not apply to all types of graph.

C. Perform algorithms such as the finding of maximum flow, minimum spanning tree, shortest distance, diameter, and matchings when these exist.

D. Relate various broad areas of applications to reach of the common graph theoretic properties.

V. Topical outline:
A.Basic Concepts

1. Varieties of graphs

2. Directed graphs

3. Adjacency and incidence matrix of a graph

4. Paths and circuits.

5. Trees and tree properties

6. Separating sets and connecting: s

7. Graphs as relations

B. Graph Theoretic Topics and Application Areas.

(The following partial list is a minimal list and is not intended to exclude further important applications.)

V. Topical outline (continued)
B.

1. Maximum flow networks optimization and maximum capacity of flow of transportation and communication; and assignment problems.-

2. Minimum distance, renters, radials: paths, rotating , location of services, communications.

3. Hall's Matching theorem: assignment problems.

4. Planar graphs: routes, cross-overs.

5. Hamiltonian and Euclerian graphs: paths, routing of services.

6. Coloring problems: location of essential services,inventory.

VI. Bibliography, Texts, Readings.
Busackerj R.G. and T. L. Saatz. Finite Graphs and Networks. New York: McGraw-Hill, 1965.

Christofides, N. Graph Theory-An Algorithmic Approach. New York: Academic Press, 1975.

Ford, L.K., Jr. and D. R. Fulkerson. Flows in Networks. Princeton: Princeton University Press, 1962.

Harary R. Graph Theory. Reading, Mass.:Addison-Wesley, 1969.

Maki, D.P. and M.T. Thompson. Mathematical Models and Applications . Englewood Cliffs, N.J.: Prentice-Hall, 1973.

Mayeda, W. Graph Theory. New York: Wiley Interscience, 1972.

Pearl, M. Matrix Theory and Finite Mathematics. New York: McGraw-Hill, 1973.

Roberts, F.S. Discrete Mathematical Morsels. linglew<>od Cliffs, N.J., Prentice Hall, 1975.

Wilson, R. Introduction to Graph Theory. New York: Academic Press 1972.

VII. Presentation and Evaluation.
A. Presentation by lecture and classroom discussion.

B. Evaluation by examination, written homework, and class participation.

VIII. prerequisites

Mathematics 202-Introduction to linear algebra.

IX. Credit.

3 semester hours.

X. Catalog Description.

MAT 370-APPLIED NETWORKS Introduction to network and graph theoretic concepts. Considers properties with application in computational mathematics, social science,decision making, and physical science.

XI. Statement of Approval.

This course outline was examined in accord with recommended procedures and approved by the Department of mathematics.

__________(Date) _______________________(Chairman)
X. Statement of qualification of faculty who will teach the course.
A master's degree in mathematics is a minimum formal -education. In addition the instructor should have an interest in and experience with the application of graph theory. The fulfillment of the second requirement is best judged by the department chairman. Two people: presently in the department who meet both requirements are:

Michael W. Boyd, Assistant Professor of Mathematics, Ph.D. State University of New York at Binghamton, 1974

Alwin C. Green, Assistant Professor of Mathematics, Ph.D. Syracuse University, 1972