Your Practice Set – Applications and Interpretation for IBDP Mathematics
SUMMARY POINTs
� |
Eulerian trails and circuits : |
1 . |
Trail : A sequence of edges that passes through any edge at most once |
2 . |
Circuit : A trail that the starting vertex is the end vertex |
3 . |
Eulerian trail : A trail that passes through all edges of a graph |
4 . |
Eulerian circuit : A circuit that passes through all edges of a graph |
5 . |
An Eulerian trail exists if there exists two and only two vertices of odd |
degree |
6 . |
An Eulerian circuit exists if all vertices are of even degree |
7 . |
Chinese postman problem can be used to find the route of minimum |
weight that covers all edges of a graph |
� Hamiltonian paths and cycles : 1 . Complete graph : A graph that there exists an edge for any pair of two vertices 2 . Hamiltonian path : A path that passes through all vertices of a graph 3 . Hamiltonian cycle : A cycle that passes through all vertices of a graph
� Travelling Salesman problem : 1 . Travelling Salesman problem can be used to find the cycle of minimum weight that passes through all vertices of a graph 2 . Nearest neighbour algorithm can be used to find the upper bound of the solution of a travelling salesman problem 3 . Deleted vertex algorithm can be used to find the lower bound of the solution of a travelling salesman problem
Solutions of Chapter 9
124
SE Production Limited