Graph Theory Assignment
- The sum of the degrees of all vertices of the graph = (2x3) + (6x4) = 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.
