Learnitweb

Introduction to Graph

—

by

Editorial Team
in

1. Introduction

In this short tutorial, we’ll discuss Graph. We’ll discuss the terms related to graphs. Graphs are studied in Graph Theory.

2. What is Graph Theory?

Graph theory is a branch of mathematics that studies the properties and applications of graphs, which are structures made up of vertices (nodes) connected by edges (links).

It explores how these vertices and edges can be arranged and connected, providing insights into various problems in computer science, biology, social sciences, and more. Key concepts include paths, cycles, connectivity, and coloring, with practical applications ranging from network design and analysis to solving puzzles like the famous Seven Bridges of Königsberg. Graph theory is essential for optimizing network flows, analyzing social dynamics, and developing efficient algorithms for a wide range of applications.

3. What is a Graph?

We can represent the given graphs with the help of vertices (V) and Edges (E). A graph G(V,E) is made up of V nodes (vertices) that are connected by E edges (links).

Vertices (or Nodes): These are the individual objects or points in the graph. Each vertex represents a unique entity within the graph.

Edges (or Links): These are the connections between pairs of vertices. Each edge connects two vertices, indicating a relationship or interaction between them.

In the following example of graph, there are 4 vertices or nodes: A, B, C and D. These vertices are connected with 4 edges. These are directed edges as the edges have direction, for example from from node A to C.

4. Types of Graph

There are two types of graphs:

  • Undirected graph
  • Directed graph

4.1 Undirected graph

An undirected graph G(V,E) is a set of vertices and edges where the edges are bidirectional. It means that edge (u,v) is identical to the edge (v,u). Note that the edges may have weights as well. In simple words, undirected graphs have edges that do not have a direction.

Characteristics of an undirected graph:

  • Edges are bidirectional.
  • In an undirected graph, there is no concept of “parent” and “child” as edges do not have any direction.
  • It is possible for an undirected graph to have loops.

Following is an undirected graph.

4.3 Directed Graph

A directed graph G (V, E) is a set of vertices and edges where the edges have direction. It means that edge (u,v) is not identical to the edge (u,v).

Characteristics of a directed graph:

  • In a directed graph, edges have a direction associated with them. This indicates a one-way relationship between vertices.
  • A path between vertices in a directed graph follow the direction of the edges. Path can be used to check the reachability between vertices.
  • A directed graph can contain cycles.

5. Tree

A tree is an undirected graph in which any two vertices are connected by exactly one path. The elements of trees are called their nodes and the edges of the tree are called branches. A tree with n vertices has (n-1) edges.

6. Forest

Forest is an undirected graph where connected components are trees(disjoint union of trees). In other words, a forest is a graph that has no cycles and is not necessarily connected. Each connected component of a forest is a tree.

  • If a forest has only one component, it is a tree.
  • A forest with n vertices and k components has exactly n−k edges.

7. Directed Acyclic graph (DAG)

It is a finite directed graph with no directed cycles. That is, it consists of vertices and edges (also called arcs), with each edge directed from one vertex to another, such that following those directions will never form a closed loop.

8. Complete graph

In complete graph, every single pair of vertices (nodes) are connected. A complete graph is a graph in which each vertex is connected to every other vertex. That is, a complete graph is an undirected graph where every pair of distinct vertices is connected by a unique edge.

9. Weight of an edge

The weight of an edge is often referred as the “cost” of an edge. In a graph, weight af an edge may be a measure of the length of a route, the energy required to move between locations between two nodes etc.

10. How to represent a graph in a programming language

Let us now see how to represent a G(V, E) graph in programming language. There are two ways to represent a graph in programming language.

  • Adjacency list representation
  • Adjacency matrix representation

10.1 Adjacency list representation

In adjacency list representation a data structure (array) is assigned to every single vertex (node) in the graph that stores the edge information accordingly. The list size is equal to the number of vertex(n).

Adjacency list representation is space efficient when dealing with sparse graphs but inefficient with dense graphs. Iterating over all the edges is efficient. Edge weight lookup is slow O(E) because we have to find in linear time.

Let’s assume the list of size n as Adjlist[n].

Adjlist[0] will have all the nodes which are connected to vertex 0.
Adjlist[1] will have all the nodes which are connected to vertex 1 and so on.

10.2 Adjacency matrix representation

An adjacency matrix is a way of representing a graph as a matrix of boolean (or weights). Let’s assume there are n vertices in the graph So, create a 2D matrix adjMat[n][n] having dimension n x n.

If there is an edge from vertex i to j, mark adjMat[i][j] as 1 or the weight of the edge.

If there is no edge from vertex i to j, mark adjMat[i][j] as 0.

11. Application of graphs

Graphs are helpful in solving various problems and used in various algorithms. Following are some examples of such algorithms and problems:

  • Shortest path algorithms: Shorted path algorithms are used on a daily basis in various application like Google Maps.
    Dijkstra’s shorted path algorithm can be used to find the shorted path between two locations.
    Bellman-Ford algorithm can be used to find arbitrage opportunities on the FOREX.
    Open Shortest Path First (OSPF) routing protocol in computer networks is used to navigate packages on the web.
  • Google’s page rank algorithm: Graph traversal algorithms are used to crawl the web and index the pages.
  • Software project management tools such as Maven and Gradle use the cycle detection and Directed Acyclic Grpahs (DAGs) to compile dependencies and also check the cyclic dependencies.
  • Optimization problems: Most of the quadratic optimization problems can be transformed into a graph theory problems. Following are some examples:
    Vehicle routing problem
    Airline scheduling problem
    maximum flow problem

12. Conclusion

In this tutorial, we have explored the fundamental concepts of graphs, a vital structure in computer science and discrete mathematics.