In this blog post will study what is a graph data structure, types and applications of graphs.

Definition

Terminologies

• Directed edge: Ordered pair of vertices (u,v) where u the edge starts from u and ends at v.
  For ex: One way road.
• Undirected edge: Unordered pair of vertices (u,v) where the edge is from u to v & vice versa.
  For ex: Railway lines.
• When an edge connects two vertices, the vertices are said to be adjacent to each other and the edge is incident on both vertices.
• Self loop: An edge that connects a vertex to itself i.e the pair (u,u).
• Degree of a vertex: The number of edges incident on a given vertex.
• Subgraph: A subset of a graph’s edges (with associated vertices) that form a graph.
• Path: It is a sequence of adjacent vertices. Simple path is a path with no repeated vertices.
• Cycle: A path where the first and last vertices are the same.
• We say that one vertex is connected to another if there is a path that contains both of them.

Types

1. Directed Graph(Digraph): A graph with only directed edges.
2. Undirected Graph: A graph with only undirected edges.
3. Directed Acyclic Graph(DAG or Diagraph): A directed graph with no cycles.
4. Bipartite Graph: A bipartite graph is a graph whose vertices can be divided into two sets such that all edges connect a vertex in one set with a vertex in the other set.
5. Complete Graph: It is a graph with all edges present. A bipartite graph in which all the edges are present is called as Complete Bipartite Graph.
6. Connected Graph: A graph is said to be a connected graph if there is a path from every vertex to every other vertex. If a graph is not connected then it consists of a set of connected components.

Applications

• Representing relationships between components in electronic circuits.
• Transportation networks: Highway network, Flight network.
• Computer networks: Local area network, Internet, Web.
• Databases: For representing ER (Entity Relationship) diagrams in databases, for representing dependency of tables in databases