Graphs, Diagraphs & Networks

Unit Outline (Higher Education)

Level of Unit in Course

AQF Level(s) of Course

Level of Unit in Course

Introductory

Intermediate

Effective Term:

2024/20

Institute / School :

Institute of Innovation, Science & Sustainability

Unit Title:

Graphs, Diagraphs & Networks

Unit ID:

MATHS2012

Credit Points:

15.00

Prerequisite(s):

Nil

Co-requisite(s):

Nil

Exclusion(s):

Nil

ASCED:

010101

Other Change:

Brief description of the Unit

The focus of this unit will be on studying the fundamentals of Graph Theory and on modelling real world problems using both directed and undirected graphs. Students will study the structure and properties of graphs, as well as the techniques to analyse a variety of applications.

Grade Scheme:

Graded (HD, D, C, P, MF, F, XF)

Work Experience Indicator:

Placement Component: No

Supplementary Assessment:

Where supplementary assessment is available a student must have failed overall in the Unit but gained a final mark of 45 per cent or above, has completed all major assessment tasks (including all sub-components where a task has multiple parts) as specified in the Unit Description and is not eligible for any other form of supplementary assessment

Course Level:

Learning Outcomes:

The focus of this unit will be on studying the fundamentals of Graph Theory and on modelling real world problems using graphs, both directed and undirected. In the situations that will be investigated, students will select those features that can be represented as graphs (directed graphs) or networks (weighted graphs and digraphs). After successfully completing this course, students should be able to:

Knowledge:

K1.	demonstrate an understanding of the fundamentals of Graph Theory

Skills:

S1.	investigate properties of graphs such as degree sequence, diameter, radius, and adjacency matrix

S2.	solve graph-theoretic problems

S3.	design simple graph algorithms

S4.	apply graph-theoretic models to a range of real world situations

Application of knowledge and skills:

A1.	recognise real world problems, which can be modelled as graphs, digraphs or networks

A2.	use appropriate technology to assist in the solution and investigation of real world problems

Unit Content:

Topics may include:
1. Graphs, basic properties of graphs, subgraphs
2. Eulerian and Hamiltonian graphs
3. Directed graphs
4. Matrix representations
5. Tree structures, counting trees
6. Greedy algorithms, path algorithms
7. Paths and connectivity
8. Menger`s theorem
9. Planar graphs, Euler formula, planarity testing
10. Applications

Graduate Attributes:

	Learning Outcomes Assessed	Assessment Tasks	Assessment Type	Weighting
1.	K1, S1-4, A1,A2	Individual and/or group exploration in solving problems presented as graphs	Projects / Assignments / Presentation	30 - 50%
2.	K1, S1-4	Review and skills practice	Tests / Examinations	50 - 70%

Adopted Reference Style:

APA

Professional Standards / Competencies:

Standard / Competency

Threshold Learning Outcomes - Mathematics: Initial

Attribute			Assessed	Level
1 Understanding
	1.1 Demonstrate a coherent understanding of the mathematical sciences.
		1.1.1 Ability to construct logical, clearly presented and justified arguments incorporating deductive reasoning.	Yes	Introductory
		1.1.2 Understanding of the breadth of the discipline, its role in other fields, and the way other fields contribute to development of the mathematical sciences.	Yes	Introductory
2 Knowledge
	2.1 Exhibit depth and breadth of knowledge in the mathematical sciences.
		2.1.2 Well-developed knowledge in at least one sub-discipline of the mathematical sciences.	Yes	Introductory
3 Inquiry and Problem Solving
	3.1 Investigating and solving problems using mathematical and statistical methods.
		3.1.1 Ability to formulate and model practical and abstract problems in mathematical and / or statistical terms using a variety of methods.	Yes	Introductory
		3.1.2 Ability to apply mathematical and / or statistical principles, concepts, techniques and technology to solve practical and abstract problems and interpret results critically.	Yes	Introductory
5 Responsibility
	5.1 Demonstrate personal, professional and social responsibility.
		5.1.2 Ability to work effectively and responsibly in an individual or team context.	Yes	Introductory