SiMON FRASER
MEMORANDUM
UNIVERSITY
?
-40
,
To ...... ...... ...........................................
.From ...
Senate .Commite.e..on..Under.graduate
Studies
Subject.
?
.
Course
..
.
?
Date. .. .19.8G-.0 3-27
..................................
Action taken by the Senate Committee on Undergraduate Studies
at its meeting of March 25, 1980, gives rise to the following
motion:
MOTION
That Senate approve and recommend approval to the Board
of Governors as set forth in paper S80_
40
, the proposed
new course MATH 445-3 (Introduction to Graph Theory) with
adjustment to the syllabus for MATH 443-4 (Combinatorial
Theory) to exclude topics on graph theory.
NOTE
MATH 443-4 is currently offered once each year. It and the
proposed new course MATH 445-3 will each be offered once every
S ?
two years. Thus the increase in courses is accommodated by a
reduction in the frequency of offering.
SiMON FRASER UNIVERSITY
MEMORANDUM
Sc
(J6-
0...HM........vans........................................................................................
....
Re.gis.tr.a.r...and...S..cje.t.a.r.y
....................................................
Senate Committee Undergraduat Studies
Subject ... N.e.w..
.C.our.s.e...P.r.op.o.sa.1...MATH...44573
.........................
From.....
N...He.ath ...................................................
Administrative ... .As.sistan.t
Faculty of Science
Date....
l.9..O .... 0.3.
?
.1.3...................................................
Yesterday, the Faculty of Science approved the following
motion:
"That the proposed new course MATH 445-3, Introduction to
Graph Theory... be approved and forwarded to SC!JS t Senate for
consideration and approval."
The supporting documentation is attached, together with
memoranda relating to the questions of course overlap and library
resources.
N. Heath
/rw
att.
--0
SENATE COMMITTEE ON UNDERGRADUATE STUDIES
COURSE PROPOSAL FORM
Calendar Information
Abbreviation Code:
MATH
Course Number:
445
Department:
Credit Hours:
MATHEMATICS
3 ?
Vector:
3-0-0
.
Title of Course: ?
INTRODUCTION TO GRAPH THEORY
Calendar Description of Course:
Connectivity, Eulerian graphs, Hamiltonian graphs, planar graphs, matchings,
vertex coloring, and applications of graphs.
Nature of Course
LECTURE
Prerequisites (or special instructions):
MATH 243-3 or CMPT 205 -3
What course (courses), if any, is being dropped from the calendar if this course is
approved: ?
NONE
2. Scheduling
How frequently will the course be offered?
Once every two years (see attachment)
Semester in which the course will first be offered?
SPRING 1981
Which of your present faculty would be available to make the proposed offering
possible:
B. Aispach and T. Brown
Objectives of the Course
(See attached)
4.
Budgetary and Space Requirements (for information only)
What additional resources will be required in the following areas:
Faculty\
?
MATH 445-3 is to be offered once every two
Staff ?
years with Math 443-4, Combinatorial Theory,
(which is currently offered once each year)
Library ?
alternating with the same frequency of
Audio Visual (
?
NONE ?
offering as Math 445-3.
Space
Equipment
5.
Approval
?
/
R
Date: ?
January 28, 1980
?
/ ?
)
?
25 10
A
Department thairfnan
?
an
?
Chairman, SCUS
S
Su-6S 73-34b:- (When completing this fc4in, for instructions see Memorandum SCUS 73-34a.
Attach course outline).
MATH 445-3
S
?
INTRODUCTION TO GRAPH THEORY
1.
Graphs and subgraphs
Isomorphism, subgraphs, adjacency matrix, paths, cycles and vertex degrees
2.
Trees
Cut-vertices, cut-edges and Cayley's formula.
3. Connectivity
Blocks and applications of connectivity.
4. Eulerian graphs
Euler tours, Hamiltonian cycles and applications.
5. Matchings
Matchings, coverings and the assignment problem.
6.
Edge and vertex colorings
Chromatic number, Vizing's Theorem, Brook's Theorem and chromatic polynomials.
7. Independence
Independent sets, cliques, Ramsey's Theorem and applications.
8.
Planar graphs
Plane and planar graphs, dual graphs, Euler's formula and Kuratowski's Theorem.
PREREQUISITE: MATH 243-3 or CMPT 205-3
SUGGESTED TEXTBOOK: GRAPH THEORY WITH APPLICATIONS
by Bondy and Murty
Published by MacMillan Press
10/79
0
SIMON FRASER UNIVERSITY
?
MEMORANDUM
o ?
Dr. A. G.
o an ?
.From .....
F ?
G.A.C. Graham, Chairman
Faculty of Science Undergraduate Curricu urn
..
?
Undergraduate Stuies Committee
Departmen
?
... ..
?
...... Mathernatic.
Subject. ?
445•,•
?
TS
1O1.
.t9 .
h•
.çrap
.T!.94Y
Date
......January
(3-0-01
At its meeting held on January 28, 1980 the Department of Mathematics
approved the int
r
oduction of the course
MATH 445-3, Introduction to Graph Theory (3-0-0)
with the proviso that the syllabus for Math 443-4, Combinatorial Theory, be
rewritten so as to exclude topics on Graph Theory.
Math 445-3 is to be offered once every two years with Math 443-4 (which
is currently offered once each year) alternating with the same frequency of
offering as Math 445-3.
The proposal may now be taken before your committee.
Also, I am taking this opportunity to circulate the new course proposal
to the other Faculties for the purposes of course overlap.
4.
G.Aft. Graham'
End: Course proposal form and
syllabus for Math 445-3
cc: ?
Dr. E.W. Roberts, Chairman, Faculty of Arts LJCC
Dr. M. Wideen, Chairman, Faculty of Education UCC
Dr. J. Dickinson, Chairman, Fids 11CC
Mr. Nick Heath, Dean of Science Office
1100,
S
Dr. M. Singh, Chairman, Mathematics
0
Ru'!' LONAIh' FOR / R()f'OStI) COURSE' INTRODUCTION TO (;RAI'lI TiIlORY
0 ?
Oh jcct ivcsof the course
'!'hcrv are two principal reasons for projx,siny this course. The first
:'cason deals with our own graduate program. We now have a graduate level
course (Math 820) in graph theory. This is due to the fact that there is
considerable interest in our graduate program in discrete mathematics.
Last Pji1 seven students took Math 820 and this Pall twelve students (ten
for credit and two audits) are taking Math 820. Last Pall five of the seven
students had never had a course in graph theory and of the twelve students
this Pall, eleven have never had a course in graph theory. I shall leave
it up to the reader's imagination the kinds of problems produced by this
situation. It should be rectified.
The second reason deals with the increasing importance of graph theory
as a subject worth studying. Basic ideas of the subject are being employed
in a variety of other disciplines. It should be pointed out that of the
twelve students taking Math 820 this Fall, six are graduate students from
Computing Science. This is strong evidence that an undergraduate course in
Cr1
ph Theory would attract Computing Science students as well as mathematics
students
written by
Brian Aispach
• -
A
?
SIMON FRASER UNIVERSITY
MEMORANDUM
4000
46 "'
S `* - - -
Mr. Larry Thomas
Library
Subject.. ?
MATh 445-3, Introduction to
Graph Theory (3-0-0)
From
G.A.C. Graham, Chairman
?
.
Undergraduate Studies Committee
Mathematics Department
Date ?
January 29, 1980
The Department of Mathematics has approved the introduction of the course
MATH 445-3, Introduction to Graph Theory (3-0-0).
This represents the extension to a full course of material that has previously
been partly covered in MATH 443-4, Combinatorial Theory and in future the latter
course will exclude topics in Graph Theory. I believe that the Library resources
are adequate to meet the needs of the new course. Would you please confirm this.
Thank you.
.4
(i
End: Course proposal form and ?
G.A.C. Graham
syllabus for Math 445-3
cc: ?
Nick Heath, Dean of Science Office
.
•1
I ?
JAN 3 980
S
SiMON FRASER UNIVERSITY
?
U ,.
foe!^
MEMORANDUM
10,.o .........
.
A..
1 .iYifla.
?
.
From ...................Weinstein
?
.
Undergraduate Studies Committee
M ?
rpti
0 . Pprmenz
?
Li.brry. .-. .$cJ.ç
nce s.
Ojvi 519n
Subject .....
MTR
44e5-3
..........................
?
...
.
D ate .......... .
8Q/02f0
This is to confirm that present library resources are
adequate to support the following new course:
MATH
445-3,
Introduction to Graph Theory (3-0-0)
4.4
ah
'S
.5
[1
?
FEB11
r) ?
'L
This is to indicate that there is no overlap between the course proposal
Math 445-3 and any courses offered by the Faculty of Education.
MFW: kg
.
0
