|
Course No: MA04242
Credit: 4 Periods: 80
Graph
Theory
Required
Textbook: Junming
Xu, Theory and Application of Graphs.
The Press of University of Science and Technology of China, January, 1998
Background
of Course:
A
graph consists of a set of elements together with a binary relation defined on
the set. A graph can be represented by a diagram in which the elements are shown
as points and the binary relation as lines joining pairs of points. It is this
representation which gives graph theory its name and much of its appeal.
However, the true importance of graphs is that, as basic mathematical
structures, they arise in diverse contexts, both theoretical and applied. The
concepts of a graph was known already to Euler in the eighteenth century, but it
was the notorious Four-Color Problem, posed by F. Guthrie in the mid-nineteenth
century, that spurred the development of this simple concept into a flourishing
theory. In the twentieth century, interaction between graph theory and linear
algebra, probability theory, number theory, group theory, geometry, topology,
and other branches of mathematics have led to further developments in the
subject. In recent decade, its fundamental links with operation research and
computer science have resulted in the fast growth and greatly increased
prominence of graph theory.
Course
Description: This
course, in a modern point of view, provides the most basic concepts of graph
theory and what we believe to be the most interesting and important theoretical
result in the field, and types of applications to real-world problems that can
be modeled by graphs as well as efficient algorithms for their solutions. The
course covers basic concepts of graph, tree and
graphic space, plane graph and planar graph, network flow and connectivity,
matching and independent set, coloring theory, graph and group.
Audience: Beginning graduate Students
(Masters)
Preparatory
Courses: Combinatorics
Test
Form: Written
Examination
Reading
List: 1.
Bondy, J. A. and Murty, U. S. R., Graph Theory with Applications. The MaCmillan
Press ltd, London and Basingstoke,1976.
2.
Chartrand,
G, and Lesniak, L., Graphs and Digraphs (Second Edition).
Wadsworth, Inc, Belmont and California, 1986.
Suggestions
for Further Reading: 1.
Bollobas, B, Modern Graph Theory. Springer-Verlag New Yorks, Inc.,1998.
2.
Diestel,
R., GraphTheory
(Electronic Edition),
pringer-Verlag
New Yorks, Inc.,2000.
|
|
