GRAPH THEORY

MAT3GT

2020

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.

School: Engineering and Mathematical Sciences (Pre 2022)

Credit points: 15

Subject Co-ordinator: Michael Payne

Available to Study Abroad/Exchange Students: Yes

Subject year level: Year Level 3 - UG

Exchange Students: No

Available as Elective: No

Learning Activities: N/A

Capstone subject: Yes

Subject particulars

Subject rules

Prerequisites: MAT1CDE OR MAT1NLA OR MAT1CA

Co-requisites: N/A

Incompatible subjects: MAT2GT OR MAT3NAG OR MAT2NAG

Equivalent subjects: N/A

Quota Management Strategy: N/A

Quota-conditions or rules: N/A

Special conditions: N/A

Minimum credit point requirement: N/A

Assumed knowledge: N/A

Career Ready

Career-focused: No

Work-based learning: No

Self sourced or Uni sourced: N/A

Entire subject or partial subject: N/A

Total hours/days required: N/A

Location of WBL activity (region): N/A

WBL addtional requirements: N/A

Graduate capabilities & intended learning outcomes

Graduate Capabilities

COMMUNICATION - Communicating and Influencing

INQUIRY AND ANALYSIS - Research and Evidence-Based Inquiry

Intended Learning Outcomes

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

02. Apply fundamental theorems and algorithms of graph theory.

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

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

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

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

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

Bendigo, 2020, Semester 1, Day

Overview

Online enrolment: Yes

Maximum enrolment size: N/A

Enrolment information: N/A

Subject Instance Co-ordinator: Christopher Lenard

Class requirements

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

LectureWeek: 10 - 22
One 1.00 hour lecture per week on weekdays during the day from week 10 to week 22 and delivered via face-to-face.

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

Assessments

Assessment element	Comments	Category	Contribution	Hurdle	%	ILO*
Five problem-based assignments. (700 words equivalent each, 3500 words total)Each is typically completed in 5-8 pages. (Assignment 1-15%, Assignment 2-15%, Assignment 3-15%, Assignment 4-20%, Assignment 5-15%)	N/A	N/A	N/A	No	80	SILO1, SILO2, SILO3, SILO4, SILO5, SILO6, SILO7
One essay-based assignment of 500-1000 words.	N/A	N/A	N/A	No	20	SILO1, SILO2, SILO3, SILO4, SILO5, SILO6, SILO7