Graphs, associated terminology and the adjacency matrix
4 hours
-
Understand the meaning of graph, vertex (node), edge (arc), loop, degree of a vertex, subgraph, simple graph, complete graph, bipartite graph, directed graph (digraph), weighted graph and network.
1 interactive
-
Construct a network diagram to represent practical situations, e.g. tracks connecting camp sites in a national park, a social network, a transport network with one-way streets, the results of a round-robin sporting competition.
-
Construct an adjacency matrix from a given graph or digraph.
1 interactive
-
Construct a graph or digraph from a given adjacency matrix.
Planar graphs, paths and cycles
8 hours
-
Understand the meaning of planar graph and face.
-
Apply Euler’s formula to solve problems relating to planar graphs.
1 interactive
-
+ − = 2 where is number of vertices, is number of faces and is number of edges
-
Understand the meaning of walk, trail, path, open walk, open trail, open path, closed walk, closed trail (circuit), closed path (cycle), connected graph and bridge.
1 interactive
-
Solve practical problems to determine the shortest path between two vertices in a weighted graph (by trial-and-error methods only).
1 interactive
-
Understand the meaning of Eulerian trail, semi-Eulerian graph, Eulerian circuit and Eulerian graph, and the conditions for their existence.
1 interactive
-
Solve practical problems involving semi-Eulerian graphs and Eulerian graphs.
-
Understand the meaning of Hamiltonian path, semi-Hamiltonian graph, Hamiltonian cycle and Hamiltonian graph.
1 interactive
-
Solve practical problems involving semi-Hamiltonian graphs and Hamiltonian graphs (by trial-and-error methods only).