Show/hide contentOpenClose All
Curricular information is subject to change
After successful completion of the course, a student should:1. be able to determine whether or not certain sequences belong to simple graphs;2. be able to construct a graph, given a graphic sequence;3. be able to perform simple mutations of a graph, such as constructing its subgraphs, its complement and its dual where one exists;4. know basic results about acyclic graphs (trees)5. be able to compute minimal weight spanning trees (Prim & Kruskal algorithms);6. be able to compute the Pruefer sequence of a labelled tree;7. be able to identify Eulerian graphs and find Euler circuits (Fleury's algorithm);8. know some necessary and suffcient conditions for a graph to be Hamiltonian and be able to apply these to arbitrary graphs;9. be familar with Euler's polyhedral formula and apply it to establish non-planarity;10. be able to determine isomorphisms for small graphs;11. be familiar with the min-cut max flow theorem;12. be able to apply the Ford-Fulkersen algorithm for the construction of a maximal flow.
| Student Effort Type | Hours |
|---|---|
| Lectures | 18 |
| Tutorial | 12 |
| Specified Learning Activities | 24 |
| Autonomous Student Learning | 50 |
| Total | 104 |
Basic Discrete Mathematics and Combinatorics
| Description | Timing | Component Scale | % of Final Grade | ||
|---|---|---|---|---|---|
| Examination: End of trimester exam. | 2 hour End of Trimester Exam | No | Standard conversion grade scale 40% | No | 70 |
| Examination: Midterm exam. The timing of the midterm can be slightly changed in order to accommodate as many people as possible. | Week 7 | No | Standard conversion grade scale 40% | No | 30 |
| Resit In | Terminal Exam |
|---|---|
| Spring | Yes - 2 Hour |
• Group/class feedback, post-assessment
Not yet recorded.
| Name | Role |
|---|---|
| Dr Carl Bracken | Lecturer / Co-Lecturer |