What is Adjacency Matrix Graph Representation? Adjacency Matrix is a graph data structure. It is a technique to store graphs. The adjacency matrix is a 2D boolean array of size V2 where V is the number of vertices in the graph. The adjacency matrix contains V rows and V columns. The i-th row and j-th …
Advantages and Disadvantages of Adjacency Matrix Graph Representation Read More »
In this article, we will explain how we can check if a given graph is bipartite or not in detail. Basic Terminologies Bipartite Graph: A simple graph G(V, E) is called Bipartite Graph if it’s vertices can be partitioned into two disjoint sets – V1 and V2, such that no edge connects vertices belonging to …
Program to check whether a given graph is Bipartite Read More »
Before proof, we will define some basic terminologies. Bipartite Graph: A graph whose vertices can be divided into 2 disjoint sets such that no two vertices in the same set are adjacent to each other is called Bipartite Graph. Proof We can prove the given statement by contradiction. Suppose you have a bipartite graph G. …
Prove that a graph which contains a triangle cannot be bipartite Read More »
First we will define some basic terminologies. Bipartite Graph: A graph is bipartite if we can spit the vertices of the graph in two distinct sets V1 and V2 such that no edge connects vertices belonging to the same set. Hamiltonian Graph: A graph is hamiltonian if it contains a hamiltonian circuit. Hamiltonian circuit is …
Prove that a bipartite graph with an odd number of vertices is not hamiltonian Read More »
In this post, we will be show how every 2-connected graph contains atleast one cycle. First, we will discuss what exactly is a 2-connected graph. A connected graph is said to be 2-connected if it contains more than 2 vertices and the graph remains connected if fewer than 2 vertices are removed from the graph. …
Prove that Every 2-Connected Graph Contains at least One Cycle Read More »
A wheel graph is obtained by connecting a vertex to all the vertices of a cycle graph. It is denoted by Wn, for n > 3 where n is the number of vertices in the graph. A wheel graph of n vertices contains a cycle graph of order n – 1 and all the vertices …
Hierholzer’s algorithm is another algorithm to find the Euler Path or Euler circuit in a graph. It’s time complexity is O(E).
Fleury’s algorithm is used to find a Euler Path/Circuit in a connected graph. It is based on the principle that the bridge edge is visited in last.
A circuit that visits every edge exactly once is known as Euler Circuit. A path that visits every edge of a graph exactly once is known as Euler Path.
A simple graph is called Bipartite if it’s vertices can be partitioned into two disjoint sets, such that no edge connects vertices of same set.