Showing posts with label MCS-033. Show all posts
Showing posts with label MCS-033. Show all posts
SEE the MCS-033 Study material
Block 1
Page no. 27
Example 4
Block 1
Page no. 27
Example 4
Ore's theorem is a result in graph theory proved in 1960 by Norwegian mathematician Øystein Ore. It gives a sufficient condition for a graph to be Hamiltonian, essentially stating that a graph with "sufficiently many edges" must contain a Hamilton cycle. Specifically, the theorem considers the sum of the degrees of any two non-adjacent vertices: if this sum is always at least equal to the total number of vertices in the graph, then the graph is Hamiltonian.
Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if
deg v + deg w ≥ n for every pair of non-adjacent vertices v and w of G (*)
then G is Hamiltonian.
Suppose it were possible to construct a graph that fulfils condition (*) which is not Hamiltonian. According to this supposition, let G be a graph on n ≥ 3 vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all n-vertex non-Hamiltonian graphs that satisfy property (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v1v2...vn, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v1 cannot be adjacent to vn, for otherwise v1v2...vn would be a Hamiltonian cycle. By property (*), deg v1 + deg vn ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, vi is adjacent to v1 and vi − 1 is adjacent to vn. But the cycle v1v2...vi − 1vnvn − 1...vi is then a Hamilton cycle. This contradiction yields the result.
Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.
Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps:
Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether vj and vj + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices vi and vi + 1 would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n2), matching the number of edges in the input graph.
Formal statement
Let G be a (finite and simple) graph with n ≥ 3 vertices. We denote by deg v the degree of a vertex v in G, i.e. the number of incident edges in G to v. Then, Ore's theorem states that if
deg v + deg w ≥ n for every pair of non-adjacent vertices v and w of G (*)
then G is Hamiltonian.
Proof
Suppose it were possible to construct a graph that fulfils condition (*) which is not Hamiltonian. According to this supposition, let G be a graph on n ≥ 3 vertices that satisfies property (*), is not Hamiltonian, and has the maximum possible number of edges among all n-vertex non-Hamiltonian graphs that satisfy property (*). Because the number of edges was chosen to be maximal, G must contain a Hamiltonian path v1v2...vn, for otherwise it would be possible to add edges to G without breaching property (*). Since G is not Hamiltonian, v1 cannot be adjacent to vn, for otherwise v1v2...vn would be a Hamiltonian cycle. By property (*), deg v1 + deg vn ≥ n, and the pigeon hole principle implies that for some i in the range 2 ≤ i ≤ n − 1, vi is adjacent to v1 and vi − 1 is adjacent to vn. But the cycle v1v2...vi − 1vnvn − 1...vi is then a Hamilton cycle. This contradiction yields the result.
Algorithm
Palmer (1997) describes the following simple algorithm for constructing a Hamiltonian cycle in a graph meeting Ore's condition.
Arrange the vertices arbitrarily into a cycle, ignoring adjacencies in the graph.
While the cycle contains two consecutive vertices vi and vi + 1 that are not adjacent in the graph, perform the following two steps:
Search for an index j such that the four vertices vi, vi + 1, vj, and vj + 1 are all distinct and such that the graph contains edges from vi to vj and from vj + 1 to vi + 1
Reverse the part of the cycle between vi + 1 and vj (inclusive).
Each step increases the number of consecutive pairs in the cycle that are adjacent in the graph, by one or two pairs (depending on whether vj and vj + 1 are already adjacent), so the outer loop can only happen at most n times before the algorithm terminates, where n is the number of vertices in the given graph. By an argument similar to the one in the proof of the theorem, the desired index j must exist, or else the nonadjacent vertices vi and vi + 1 would have too small a total degree. Finding i and j, and reversing part of the cycle, can all be accomplished in time O(n). Therefore, the total time for the algorithm is O(n2), matching the number of edges in the input graph.
See second block of your study material
What are the practical application of Hamilton path& circuit? State Dirac’s and Ore’s theorems for a Hamilton circuit.
Abstract: Multi-threshold CMOS (MTCMOS) is currently the most popular methodology in industry for implementing a power gating design, which can effectively reduce the leakage power by turning off inactive circuit domains. However, large peak current may be consumed in a power-gated domain during its sleep-to-active mode transition. As a result, major IC foundries recommend turning on power switches one by one to reduce the peak current during the mode transition, which requires a Hamiltonian-cycle routing to serially connect all the power switches. ...
- Another """application""" (note the triple quotes :-) is puzzle games ... for example in the game RoundTrip (a.k.a. GrandTour) you must find an Hamiltonian circuit in a grid of points in which some of the edges are given.
But there are many other puzzles/videogames that are directly inspired by the Hamiltonian circuit/path problem: Inertia, Pearl, Rolling Cube Puzzles, Slither,...
... and the "hardness" of HC makes them addictive: even small instances can be very hard to solve for our brain!!!
The population of tigers increases 4 percent per year. In 2000 the population was 15000. What was the population 30 years back i.e in year 1970?
Write whether or not each recurrence relation in the following problems is a linear homogeneous with constant coefficient.. Also show the order of each linear homogeneous recurrence relation.
Write generic formulae for a linear homogenous recurrence relation
of order K with constant coefficient. Write all thesteps for solving
this type of a recurrence relation.
of order K with constant coefficient. Write all thesteps for solving
this type of a recurrence relation.
