2,005
12
Essay, 3 pages (650 words)

Example of math 136 essay

Graph Theory Assignment

– The sum of the degrees of all vertices of the graph = (2×3) + (6×4) = 30
– The edges in this graph are: AC, AF, AD, AB, CF, CD, BD, BF, BE, DH, EG, EH, FG, FH and GH. Therefore the total number of edges = 15
– Relationship between the sum of degrees of vertices and the number of edges in the graph:
Sum of degrees of vertices = 2 (number of edges)
2)
– No. An Euler path does not exist for a graph with more than 2 odd vertices, by Euler’s Theorem. The explanation is as follows: Assume there are 400 odd vertices with three edges each then, every time a vertex is approached by an edge, there will be two other edges that need to be covered. If one of them is covered first, and the other later, the second time there will be no other edge to go to that hasn’t already been covered. Hence there will be no way to trail an Euler path.
– With similar reasoning, there can be no Euler circuit as well, again by Euler’s theorem.
3)
– Similarly there can be no Euler circuit for this graph, by Euler’s theorem.
4)
– Euler Circuit: If there is closed a path that crosses every edge of a graph exactly once, then such a path is called an Euler circuit.
– Hamilton Circuit: If there is closed a path that crosses every vertex of a graph exactly once, then such a path is called a Hamilton circuit.
– The basic difference between an Euler circuit and a Hamilton circuit is that the former travels through every edge of the graph exactly once before reaching to the initial point, while the latter travels every vertex of the graph (except the initial vertex) exactly once before reaching the initial vertex.
5)
a) Steps involved in the Brute Force method to find optimal solution for the traveling salesman problems:
– Draw a complete, weighted graph to represent the given problem.
– Identify all possible Hamilton circuits in the graph.
– Calculate the cost associated with each Hamilton circuit identified in step 2.
– Choose that circuit which offers the minimum cost or distance, according to the problem. This is the optimal solution.
b) Steps involved in the nearest neighbor method to find approximate optimal solution for the traveling salesman problems:
– Draw a complete, weighted graph to represent the given problem.
– Start from any one vertex. Traverse to a neighboring vertex through an edge that has the smallest weight attached to it.
– Continue doing this till a Hamilton circuit is established. This circuit gives the approximate optimum solution.
6)
A connected graph in which every edge is a bridge is called a tree graph. In a graph which is not a tree, there can be edges which are not bridges. If two distinct vertices are connected by an edge, then it is a tree graph. This is because the only edge in the graph is a bridge. In other words, without that edge, the graph becomes disconnected.
7)
In a graph which is not a tree, edges are removed such that a path to every vertex still exists. In other words redundant edges are removed. This becomes a spanning tree.
8)

Steps involved in finding the minimum cost spanning tree from a complete, weighted graph:

– Choose the edge that has the smallest weight. If there are multiple such edges, choose any one.
– Next choose the edge with the second smallest cost such that the previous edge and this edge do not form a circuit.
– Similarly find other minimum cost edges one by one such that they do not form circuit with the previous ones.
– The process stops when a spanning tree is formed. This is the solution for the minimum cost spanning tree.

Thank's for Your Vote!
Example of math 136 essay. Page 1
Example of math 136 essay. Page 2
Example of math 136 essay. Page 3
Example of math 136 essay. Page 4

This work, titled "Example of math 136 essay" was written and willingly shared by a fellow student. This sample can be utilized as a research and reference resource to aid in the writing of your own work. Any use of the work that does not include an appropriate citation is banned.

If you are the owner of this work and don’t want it to be published on AssignBuster, request its removal.

Request Removal
Cite this Essay

References

AssignBuster. (2022) 'Example of math 136 essay'. 29 September.

Reference

AssignBuster. (2022, September 29). Example of math 136 essay. Retrieved from https://assignbuster.com/example-of-math-136-essay/

References

AssignBuster. 2022. "Example of math 136 essay." September 29, 2022. https://assignbuster.com/example-of-math-136-essay/.

1. AssignBuster. "Example of math 136 essay." September 29, 2022. https://assignbuster.com/example-of-math-136-essay/.


Bibliography


AssignBuster. "Example of math 136 essay." September 29, 2022. https://assignbuster.com/example-of-math-136-essay/.

Work Cited

"Example of math 136 essay." AssignBuster, 29 Sept. 2022, assignbuster.com/example-of-math-136-essay/.

Get in Touch

Please, let us know if you have any ideas on improving Example of math 136 essay, or our service. We will be happy to hear what you think: [email protected]