Sales Toll Free No: 1-855-666-7446

Matchings in Graphs

Top

Matching in graphs is complete Set of edges which is without the common vertices. Matching graph theory can be an entire graph without the common vertices wholly consisting of edges. The maximum matching is a matching which has the largest possible edges. There is another type of matching which is a perfect matching which matches all the vertices of graph. Complete matching is the term which is used for the perfect matching. Hence each and every perfect matching is maximum.

One more type of matching is near- Perfect matching this is a matching where exactly one vertex remains unmatched. This situation takes place when a graph has an odd number of vertices and such matching occurs is a maximum. If in each and every vertex of the graph consist of near perfect matching which hides or omit that vertex, and then the graph is also known to be the factor-critical.

Some of the properties of the matching graph theory are:
Those graphs which are without isolated vertices have sum of its matching number and those with the edge covering number stand equals with the equal number of vertices.

After that if there is a perfect matching then the both of the matching number and the edge cover number will be |V| / 2.
Now let’s have a brief theory about the maximum matching the graph which is not bipartite is used to find the maximum weight matching in a polynomial time algorithm this is due to the Edmond's algorithm. The generalization of the Edmond's algorithm technique is also used to find the maximum independent Sets. A maximum matching is also known as the maximal matching so that it makes easier to find the largest maximal matching in polynomial time. This is all about matchings in graphs.

Hamiltonian cycles

Back to Top
Hamiltonian cycle is a cyclic graph which involves all nodes or vertices of the graph from which it is created. It is also called as Hamiltonian circuit. Actually, Hamiltonian cycle is a closed loop. Graph which contains a Hamiltonian cycle is known as Hamiltonian graph. Probabilistic algorithm can be useful to find Hamiltonian cycles and paths. Following platonic solids are examples of Hamiltonian cycle. Various Hamiltonian Cycles are shown below.
Let’s consider G as a finite graph with V, the Set of vertices and E, the set of edges. The Hamiltonian cycle ‘C’ of graph G is the cycle which visits each of the vertices once.
Let’s consider the following graph to understand Hamiltonian Cycle.
Since all vertices are at least visited once by the cycle that’s why cycle ABCDEF is called as Hamiltonian cycle. Although there are many other cycles which are not Hamiltonian. For instance, cycles AFEA and BEAB are not Hamiltonian. For Hamiltonian cycle problems, always use an unweighted graph G as input. Hamiltonian cycle problems are some what similar to Traveling Salesman problem. In both problems common thing that each vertex is visited exactly once. Traveling salesman problem uses weighted graphs while Hamiltonian cycle works on unweighted graphs. Actual reduction from Hamiltonian cycle problem to traveling salesman problem is very simple just by translating an unweighted graph to weighted graph. If a graph G has a Hamiltonian cycle A,…..A n, then there will be 'n' edges in E, each with weight 1. Therefore, this gives a Traveling salesman problem tour of G of weight exactly 'n'.
A quick algorithm for TSP will show a quick algorithm for Hamiltonian cycle while a hard Hamiltonian cycle would show traveling salesman problem is hard.

Hamiltonian Cycles Algorithm

Back to Top
Concept of Hamiltonian cycle algorithm was given by Sir William Rowan Hamilton in 1989, it is a closed loop formed by visiting each vertex of graph. Path by which graph is connected is called Hamilton path. Graph is called Hamilton connected graph if there is a Hamilton path between all its vertices.

So we can say that a graph is Hamiltonian if a Hamiltonian cycle (HC) exists. If we remove one edge from Hamilton cycle then it is called as Hamilton path.
These types of problems are considered as NP complete problems. To check whether there exists Hamilton cycle or not there are some theorems using which we can easily check that Hamilton cycle exist or not:- Bondy - Chvatal theorem, Dirac, Ore, Ghouila - Houiri, Meyniel.
Hamiltonian path algorithm: Suppose there is a graph G, which has 'n' vertices . N = 1, 2, 3……n and degree (d) of this graph is given in descending order means degree = d(1) ≥ d(2) ≥ d(3)………. ≥ d(n), here we will perform this for initial vertex u = v1, so

STEP 1: Initialization: select initial vertex u = v1.
STEP 2:- Iteration: Suppose our last visited vertex is vr. So our path of visited vertex is v1 …vr.
Unvisited vertices means neighbor of vr is denoted by 'w', so we have to compute all unvisited neighbors N(w), means vr+1 = w. Now extend the path of visited vertices to v1, ….vr…vr+1.
STEP 3:- Termination: - We will continue this process until last selected vertex is visited.
STEP 4:- Result: - Path p(0) visiting vertices u = v1 …. vk 0, vk0 has no unvisited neighbor.
We will continuous this process until all vertices are visited.