Module Code - Title:

MS4117 - DISCRETE MATHEMATICS 2

Year Last Offered:

2025/6

Hours Per Week:

Lecture

2

Lab

1

Tutorial

1

Other

0

Private

6

Credits

6

Grading Type:

N

Prerequisite Modules:

MS4111

Rationale and Purpose of the Module:

To give the student an understanding of the mathematics and apllications of Graph Theory. The applications to networks and to algorithms in Computer Science will be emphasised.

Syllabus:

Graphs, directed graphs and their computer representation. Planar, Hamiltonian and Eulerian graphs. Graph algorithms (Kruskal, Dijkstra, DFS, BFS etc) Graph coluring with applications to scheduling. Network flows and matchings. Other topics will be covered from time to time: Ramsey Theory, random graphs, Huffman codes, graph drawing, Petri nets.

Learning Outcomes:

Cognitive (Knowledge, Understanding, Application, Analysis, Evaluation, Synthesis)

1. The student will be able to recognise and identify different types of graphs such as bipartite/complete/regular/planar/Eulerian/Hamiltonian. The student will know different ways of describing such a graph using matrices. 2. The student will be able to carry out standard algorithms on graphs such as Dijkstra, BFS, DFS, Kruskal. 3. The student will be able to formulate a problem as a graph colouring problem and be able to solve it efficiently. 4. The student will be able to solve a maximal flow problem on a network by more than one method e.g. augmenting path, layered network, pre-flow push. 5. The student will be able to use his knowledge to solve on his own a graph theoretic problem and write up his solution in a project report. 6. The student will become aware of a more advanced topic such as Ramsey Theory, Huffman Codes, Random Graphs which the lecturer may choose to introduce.

Affective (Attitudes and Values)

none

Psychomotor (Physical Skills)

none

How the Module will be Taught and what will be the Learning Experiences of the Students:

Research Findings Incorporated in to the Syllabus (If Relevant):

Prime Texts:

Chartrand, G and Zhang, P (2005) Introduction to Graph Theory , McGraw-Hill

Other Relevant Texts:

Gross, J and Yellen, J (1998) Graph Theory and its Applications , CRC

West, DB (1996) Introduction to Graph Theory , Prentice-Hall

Programme(s) in which this Module is Offered:

Semester(s) Module is Offered:

Module Leader:

Clifford.Nolan@ul.ie