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

# Matchings in Graphs

Top
 Sub Topics 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

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.