Introduction To Graphs - YashasKamath/IECSE-Summer-Bootcamp-2022 GitHub Wiki

Graphs are one of the most important data structures in the domain of algorithms. Graphs are used to solve a lot of important problems like networking, social connections, reducing costs on building roads, etc. For example, Facebook uses graphs to implement the social network. They denote every person with a node in the graph and an edge between two nodes represent a friendship. A graph can be roughly put as a collection of nodes and edges. The edges signify relations between nodes in the graph.

More formally, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense related. These objects correspond to mathematical abstractions called vertices. The related pairs are called edges. The graph is represented as a set of vertices and edges.

where V is the set of all vertices and E is the set containing all the edges or the relations between pairs of nodes.

The above is a graph with six nodes and 7 edges. The sets will be,

V = {1,2,3,4,5,6} E = {(1,2),(2,3),(3,4),(4,5),(5,1),(5,2),(4,6)}

You'll notice that the edges contain the nodes in random order. Do the order of the nodes matter in determining the graph? Let's look at when it will and when it won't.

The class of graphs is classified into two different types of graphs,

  • Undirected Graphs
  • Directed Graphs

Undirected graphs have no specific direction in the edges. That is if (u,v) exists in the edge set, then we can automatically assume that (v,u) also exists. Whereas, in Directed graphs, there are directions to the edges. That is if (u,v) exists in the edge set, then there exists an edge from the node u to node v.

The above graph is an undirected graph with 3 vertices and 3 edges.

If we add directions, we get a directed graph with 3 vertices and 3 edges.

Sometimes, edges are assigned values/weights. Those graphs are called Weighted Graphs. Weighted graphs can be both directed or undirected.

The above is a weighted undirected graph.

Important Terminologies

  • Loops are defined as self-edges or an edge which is of the form (a, a) where a is a node in the graph.

  • Parallel Edges are edges of the same type with the same end-vertices.

  • Degree of a vertex is defined as the number of incident edges.

  • In-Degree is the number of incoming edges. It is defined only for a digraph.

  • ** Out-Degree** is the number of outgoing edges. It is defined only for a digraph.

  • Simple Graphs are defined as the class of graphs that do not have loops or any parallel edges.

  • Path is defined as a sequence of vertices such that every consecutive pair of vertices is connected by an edge.

  • Cycle is a path that starts and ends at the same vertex.

  • Simple Path is a path with distinct vertices.

  • Directed Path is a path of directed edges.

  • Directed Cycle is a cycle of directed edges

  • Sub Graph is a subset of vertices and Edges.

  • Spanning Sub Graph is a sub-graph that contains all vertices.

  • Connected Graph is a graph that has all the pairs of vertices connected, i.e, a path exists between any two nodes in the graph.

  • Connected Component is the maximally connected sub-graph of an unconnected graph.

  • Forest is a graph without cycles.

  • Tree is a connected forest.

  • Spanning Tree is spanning sub-graph that is also a tree.

We will look into representations of graphs in the next tutorial.