Graphs and its Types

---

Graphs and Their Types

---

A graph is a mathematical structure used to model pairwise relationships between objects. It consists of a set of vertices (also called nodes) and a set of edges that connect these vertices. Graphs are used in many areas, including computer science, social network analysis, transport systems, and more.

1. Basic Definition of a Graph

A graph $G$ is defined as a pair $G = (V, E)$, where:

• $V$ is the set of vertices (also called nodes).
• $E$ is the set of edges (also called arcs or links) that connect pairs of vertices.

Example:

If we have 3 vertices $A, B, C$, and 2 edges connecting $A$ to $B$ and $B$ to $C$, the graph is represented as:

$$G = (\{A, B, C\}, \{(A, B), (B, C)\})$$

---

2. Types of Graphs

Graphs can be classified into different types based on their properties. Some common types of graphs include:

---

a) Simple Graph

A simple graph is a graph that has:

• No loops (edges that connect a vertex to itself).
• No multiple edges (more than one edge between the same pair of vertices).

In a simple graph, each pair of vertices is connected by at most one edge.

• Example:
  Consider a graph with vertices $A, B, C$, and edges $(A, B), (B, C), (C, A)$. This is a simple graph because it has no loops or multiple edges.

---

b) Multigraph

A multigraph allows multiple edges between the same pair of vertices. These are graphs where there can be more than one edge between two vertices (parallel edges). Multigraphs can also have loops.

• Example:
  A graph with vertices $A, B, C$ and edges $(A, B), (A, B), (B, C)$ is a multigraph because the edge $(A, B)$ appears twice.

---

c) Directed Graph (Digraph)

A directed graph (or digraph) is a graph in which edges have a direction. Each edge is represented as an ordered pair $(u, v)$, meaning there is a directed edge from vertex $u$ to vertex $v$.

• Example:
  A directed graph with vertices $A, B, C$ and edges $(A, B), (B, C)$ indicates that there is an edge from $A$ to $B$ and from $B$ to $C$, but not the reverse.

---

d) Undirected Graph

An undirected graph is a graph in which the edges have no direction. Each edge is simply a set of two vertices $\{u, v\}$, meaning the edge connects vertex $u$ to vertex $v$, and there is no direction from one to the other.

• Example:
  A graph with vertices $A, B, C$ and edges $\{A, B\}, \{B, C\}$ is undirected because there is no direction associated with the edges.

---

e) Weighted Graph

A weighted graph is a graph in which each edge has a weight (or cost) associated with it. The weight can represent anything like distance, time, or cost, and is typically represented by a number.

• Example:
  A weighted graph with vertices $A, B, C$ and edges $(A, B, 5), (B, C, 3)$ means the edge between $A$ and $B$ has a weight of 5, and the edge between $B$ and $C$ has a weight of 3.

---

f) Complete Graph

A complete graph is a graph in which there is an edge between every pair of distinct vertices. In a complete graph with $n$ vertices, there are $\frac{n(n-1)}{2}$ edges in an undirected complete graph.

• Example:
  A complete graph with 3 vertices $A, B, C$ would have edges $(A, B), (B, C), (A, C)$.

---

g) Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other set. In other words, there are no edges between vertices within the same set.

• Example:
  A graph with sets $U = \{A, B\}$ and $V = \{C, D\}$, and edges $(A, C), (B, D)$, is bipartite because all edges connect vertices from set $U$ to set $V$.

---

h) Tree

A tree is a connected graph with no cycles. It is a special type of graph that is acyclic and has exactly $n - 1$ edges if there are $n$ vertices.

• Example:
  A tree with 4 vertices $A, B, C, D$ and edges $(A, B), (B, C), (C, D)$ is a tree because there are no cycles, and it is connected.

---

i) Forest

A forest is a collection of disjoint trees. It is essentially a graph that is acyclic but not necessarily connected.

• Example:
  A forest with two trees, one with vertices $A, B$ and edge $(A, B)$, and the other with vertices $C, D, E$ and edges $(C, D), (D, E)$, is a forest because it consists of multiple disjoint trees.

---

j) Planar Graph

A planar graph is a graph that can be drawn on a plane without any edges crossing. In other words, the graph can be embedded in the plane such that no edges intersect except at their endpoints.

• Example:
  The graph representing a triangle is planar because it can be drawn in a plane without any edges crossing.

---

k) Subgraph

A subgraph is a graph formed by selecting a subset of the vertices and edges of another graph. If a graph $G$ contains a graph $H$, then $H$ is a subgraph of $G$.

• Example:
  A subgraph of a complete graph with vertices $A, B, C$ and edges $(A, B), (B, C), (A, C)$ could be a graph with vertices $A$ and $B$ and the edge $(A, B)$.

---

3. Special Types of Graphs in Theory

• Cyclic Graph: A graph that contains at least one cycle (a closed loop of edges and vertices).
• Acyclic Graph: A graph that does not contain any cycles. A Directed Acyclic Graph (DAG) is one where edges have a direction, and there are no directed cycles.
• Hamiltonian Graph: A graph that contains a Hamiltonian cycle (a cycle that visits every vertex exactly once and returns to the starting point).
• Eulerian Graph: A graph that contains an Eulerian cycle (a cycle that uses every edge exactly once).

---

4. Summary of Graph Types

• Simple Graph: No loops or multiple edges.
• Multigraph: Multiple edges between the same pair of vertices are allowed.
• Directed Graph (Digraph): Edges have directions.
• Undirected Graph: Edges do not have directions.
• Weighted Graph: Each edge has a weight or cost associated with it.
• Complete Graph: Every pair of vertices is connected by an edge.
• Bipartite Graph: Vertices are divided into two sets, with edges only between the sets.
• Tree: A connected, acyclic graph.
• Forest: A collection of disjoint trees.
• Planar Graph: A graph that can be drawn without edge crossings.

---

Graphs are incredibly versatile structures and serve as the backbone for various problems in computer science, network theory, operations research, and many other fields. Understanding these different types of graphs and their properties allows for efficient problem-solving and algorithm development.