mat3gt graph theory

GRAPH THEORY

MAT3GT

2016

Credit points: 15

Subject outline

Graph theory is a part of discrete mathematics which deals with the interrelationships between a group of objects - in this context a graph is simply a set of nodes together with lines connecting some of them. In addition to their intrinsic interest, graphs are used to model structures as diverse as molecules, sentences, communications networks, and social networks. We will explore these models as well as the underlying mathematical structures. Algorithms are fundamental to the subject, for example, communications networks rely heavily on algorithms which minimise costs or maximise efficiency. Particular applications will depend on the interests of the class. This subject is especially suitable for computing, mathematics, and engineering students. It is offered at 2nd and 3rd year levels: the 3rd year level is a core subject in the Mathematics and Statistics major in Bendigo.

SchoolSchool Engineering&Mathematical Sciences

Credit points15

Subject Co-ordinatorChristopher Lenard

Available to Study Abroad StudentsYes

Subject year levelYear Level 3 - UG

Exchange StudentsYes

Subject particulars

Subject rules

Prerequisites MAT1CA or MAT1NLA or MAT1CDE

Co-requisitesN/A

Incompatible subjects MAT2GT, MAT2NAG, MAT3NAG

Equivalent subjectsN/A

Special conditionsN/A

Graduate capabilities & intended learning outcomes

01. Identify basic types of graphs, and explain the meaning of basic graph theory terms.

Activities:
Examples are introduced and discussed in lectures and concepts reinforced in assignments and tutorials.
Related graduate capabilities and elements:
Writing(Writing)
Critical Thinking(Critical Thinking)
Quantitative Literacy/ Numeracy(Quantitative Literacy/ Numeracy)
Discipline-specific GCs(Discipline-specific GCs)

02. Apply fundamental theorems and algorithms of graph theory.

Activities:
Examples are introduced and discussed in lectures and concepts reinforced in assignments and tutorials.
Related graduate capabilities and elements:
Critical Thinking(Critical Thinking)
Discipline-specific GCs(Discipline-specific GCs)
Quantitative Literacy/ Numeracy(Quantitative Literacy/ Numeracy)
Writing(Writing)

03. Explain the relevance of graph theory to various canonical applications.

Activities:
Examples are introduced and discussed in lectures and concepts reinforced in assignments and tutorials.
Related graduate capabilities and elements:
Writing(Writing)
Discipline-specific GCs(Discipline-specific GCs)
Inquiry/ Research(Inquiry/ Research)
Quantitative Literacy/ Numeracy(Quantitative Literacy/ Numeracy)
Critical Thinking(Critical Thinking)

04. Demonstrate, with examples, the uses of graphs as models in non-mathematical disciplines.

Activities:
Examples presented in class; one assignment is devoted to an essay on applications.
Related graduate capabilities and elements:
Creative Problem-solving(Creative Problem-solving)
Quantitative Literacy/ Numeracy(Quantitative Literacy/ Numeracy)
Writing(Writing)
Discipline-specific GCs(Discipline-specific GCs)
Inquiry/ Research(Inquiry/ Research)
Critical Thinking(Critical Thinking)

05. Solve complex problems by synthesising simpler concepts, ideas, and techniques.

Activities:
Assignments and tutorials. Special emphasis is given to feedback, in class, on recently completed assignments.
Related graduate capabilities and elements:
Creative Problem-solving(Creative Problem-solving)
Critical Thinking(Critical Thinking)
Discipline-specific GCs(Discipline-specific GCs)

06. Construct simple proofs and critique the validity of proofs.

Activities:
Assignments and tutorials. Special emphasis is given to feedback, in class, on recently completed assignments.
Related graduate capabilities and elements:
Creative Problem-solving(Creative Problem-solving)
Discipline-specific GCs(Discipline-specific GCs)
Quantitative Literacy/ Numeracy(Quantitative Literacy/ Numeracy)
Inquiry/ Research(Inquiry/ Research)
Critical Thinking(Critical Thinking)
Writing(Writing)

07. Write solutions to problems in a clear and logical fashion using correct terminology and supported by appropriate explanations.

Activities:
Assignments and tutorials. Special emphasis is given to feedback, in class, on recently completed assignments.
Related graduate capabilities and elements:
Writing(Writing)
Discipline-specific GCs(Discipline-specific GCs)
Critical Thinking(Critical Thinking)

Subject options

Select to view your study options…

Start date between: and    Key dates

Bendigo, 2016, Semester 1, Day

Overview

Online enrolmentYes

Maximum enrolment sizeN/A

Enrolment information

Subject Instance Co-ordinatorChristopher Lenard

Class requirements

LectureWeek: 10 - 22
Three 1.0 hours lecture per week on weekdays during the day from week 10 to week 22 and delivered via face-to-face.

TutorialWeek: 10 - 22
One 1.0 hours tutorial per week on weekdays during the day from week 10 to week 22 and delivered via face-to-face.

Assessments

Assessment elementComments%ILO*
Five problem-based assignments. Each is typically completed in 5-8 pages.(Assignment 1-15%, Assignment 2-15%, Assignment 3-15%, Assignment 4-20%, Assignment 5-15%)8001, 02, 03, 04, 05, 06, 07
One essay-based assignment of 500-1000 words.2001, 02, 03, 04, 05, 06, 07