Select Page

This assignment focuses on Introductory Discrete Mathematics. There is also description of use of computer as a research tool.

## Introductory Discrete Mathematics : use of computer as a research tool

Main topic and problem for the final project:

The main purpose of the project is to introduce you how to use a computer as a research tool in an Introductory Discrete Mathematics. So, In this project you will asked to find Hamilton Circuit(s) in a graph G.  By implementing Dijkstra’s Algorithm in any programming language.

Hamilton Paths and Circuits:  Recall that we have developed necessary and sufficient conditions  for  the  existence  of  paths  and  circuits  that  contain  every  edge  of  a  multigraph exactly once.  The natural question is that.  Can we do the same for simple paths and circuits that contain every vertex of the graph exactly once?  Also, a simple path in a graph G that passes.

through every vertex exactly once is called a Hamilton path. And a simple circuit in a graph G that passes through every vertex exactly once  called a Hamilton circuit.  Hamilton paths and/or circuits can be used to solve many practical problems.  Finding a Hamilton path or circuit in the appropriate graph model can solve such problems.

#### Introductory Discrete Mathematics : use of computer as a research tool

Shortest-Path Problems and Algorithm:  The famous traveling salesperson problem asks for the shortest route a traveling salesperson should take to visit a set of cities. This problem reduces to finding a Hamilton circuit in a complete graph such that the total weight of its edges is as small as possible(see Section 10.6).  Many problems can be modeled using graphs with weights assigned to their edges.   Graph that have  a  number  assigned to  each  edge  are  called  weighted  graphs.   Determining a  path  of  east  length  between  two vertices in a graph G, let the length of a path in a weighted graph be the sum of the weights of the edges of this path.

The question is:  What is a shortest path, that is, a path of least length, between two given vertices?