Introduction of Graphs

Degree of a Vertex

The number of edges incident on a vertex v determines its degree. For example, in the image shown below degree for vertex ‘c’ is 2.

                           Source: source

Adjacent Vertices

Two vertices, 'U' and 'V,' are said to be adjacent in a graph 'G' if they are the endpoints of an edge. For example, in the image shown above, ‘A’ and ‘B’ are adjacent vertices.

Path

A path of length n is a graph's sequence of n+1 vertices, with each pair of vertices acting as an edge. We can also segregate paths on the basis of how they connect.

1. Simple Path: A simple path is one in which no edge repeats itself, i.e., all of the vertices are distinct except for the beginning vertex, which is equivalent to the last vertex.
    
2. Elementary path: An elementary path is one in which no vertex is repeated throughout the path, i.e., all vertices are distinct.
    
3. Circuit or Closed Path: A circuit or closed path is one that begins and ends at the same vertex, v0=vn.
    
4. Simple Circuit Path: A simple circuit is a circuit with a simple path.

Now let's talk a little about connectivity.

Connectivity

Cut Vertix

Let's call the graph 'G' a connected graph. If 'G-V' (Delete 'V' from 'G') results in a disconnected graph, a vertex’ V-G’ is called a cut vertex of 'G.' When a cut vertex is removed from a graph, it splits into two or more graphs In the image below we can say that the vertex ‘e’ and ‘c’ are cut vertices.

                                                  Source: source

Cut Edge (Bridge)

Let's call the graph 'G' a connected graph. If 'U-V' results in a disconnected graph, then the edge an edge 'U-V'is called a cut edge.

A Cut Edge occurs when an edge in a graph is removed, resulting in two or more graphs. In the example shown below, the edge {c-e} is a cut edge.

                                                  Source: source

Special Graphs

Complete Graphs

A complete graph is a simple graph with 'N' vertices and exactly one edge between each pair of vertices.   The total number of edges in the complete graph is N*(N-1)/2, with 'N' vertices. You can understand this better from the image given below.

                                Source: source

Cycles

As the name suggests, graphs that form cycles are called cycles graphs for example.

                                                           Source: source

Bipartite Graph

A bipartite graph (or bigraph) has vertices that may be separated into two disjoint and independent sets, {U} and {V}, with every edge connecting a vertex in {U} to one in {V}.  A bipartite graph, on the other hand, is a graph that does not contain any odd-length cycles.

The two sets, {U} and {V}, can be thought of as a two-color coloring of the graph: if all nodes in {U}  are blue, and all nodes in{V} are green, each edge will have endpoints of different colors, as required in the graph coloring problem.

            Set representation

            Source: source

               Bipartite Graph

               Source: source

Wheels

A wheel is similar to a cycle, but it has one extra vertex that is connected to every other vertex.In a wheel graph with 'N' vertices, the total number of edges is 2*(N-1). Below illustration will make things more clear.

Source: source

Hypercube

The N-cube, also known as the Hypercube, is a graph with 2^ N vertices, each of which is represented by an N-bit string. Edges connect vertices that differ by no more than one bit. In a cube graph, the total number of edges is N * 2 ^ N - 1, with 2 ^N vertices.

Source: source

FAQs

1. What is a Graph?
   A graph is a non-linear data structure made up of nodes and edges. The edges represent some correlation between the nodes. Nodes are sometimes known as vertices, while edges are lines or arcs that connect any two nodes in the network.
    
2. How do directed and undirected graphs differ?
   The directed graph contains ordered pairs of vertices, while the undirected contains unordered pairs of vertices. In a directed graph, edges represent the direction Of vertices, while edges do not represent the direction of vertices. 
    
3. What is the maximum number of edges in the undirected graph of Nodes N? 
   Each node can have an edge with every other N-1 node in an undirected graph. Thus, the total number of edges possible will be N * (N - 1), but here, in the undirected graph, the two edges between two nodes will be the same. So we need to remove one of them. Therefore the total number of edges possible are N * (N - 1)/2.
    
4. How can we Implement BFS?
   BFS can be implemented using a queue. We keep adding the nodes present at the same level into the queue and pop out the nodes of the previous level from the queue. When we finish traversing one level, all the next level’s nodes are there in the queue at that time.
    
5. Is there any other Data Structures and Algorithms content in Coding Ninjas Studio?
   Yes, Coding Ninjas Studio allows you to practice coding as well as answer frequently asked interview questions. The more we practice, the more likely we are to acquire a job at our dream company.

Key Takeaways

Recommended Problems:

• Graph Bridge
• Longest Path In Graph
• Graph Valid Tree
• Detect cycle in an undirected graph
• Aggressive Cows
   

We introduced you to the world of graphs and discussed the basic terminologies regarding it. After reading the theory, it’s time to head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!