Graph Theory

Graph Theory is a branch of mathematics that is concerned with the study of graphs. In the case of graph theory, a graph is defined as a collection of vertices connected via edges.

Definition of Graph

A graph is an ordered pair $G=(V, E)$ where $V$ represents a set of vertices or nodes and $E$ represents a list of pairs say $(x,y)$ where $x,y$ are elements of $V$.

Example 1

In the above example, the black lines represent the edges of the graph while the blue circles with labels A to E represent the nodes. The graph can also be represented in mathematical notation as follows:

$$G=(V,E)\\ V=\{A, B, C, D, E\}\\ E=[(A, B), (A, A), (A, D), (A, C),\\ (C, B), (B, E), (D, E) ]$$

Terminologies

1. Edge: An edge is the line or the link between any two vertices of the graph.
2. Vertex: A vertex or node is a point or location that can be connected via edges.
3. Walk: A walk is an alternating sequence of edges and vertices in which both edges and vertices can be repeated.
4. Trail: A trail is a walk in which edges are not repeated.
5. Path: A path is a walk in which both edges and vertices are not repeated.
6. Cycle: A cycle is a walk in which the starting and ending vertex are the same but the edges and vertices in between are unique and don't repeat.
7. Loop: A loop is an edge with the same starting and ending vertex. In example 1, $A\leftrightarrow A$ is a loop.
8. Weight of an Edge: Any extra properties assigned to an edge are called its weight. Weight can be length, duration or any other measurable quantity or quantities. Weights are represented as a label for the edge.

Types of Graphs

Directed Graph

A graph in which the edges have direction is called a directed graph. For directed graphs, edge $(A, B)$ is not the same as $(B, A)$. A real-world example of a directed graph is cities connected by one-way roads. An example of a directed graph is as follows:

Example 2

$$V=\{A,B,C\}\\ E=[(A,B),(C,B),(A,C),(A,C),(C,A)]$$

Undirected Graph

A graph in which the edges don't have direction is called an undirected graph. For undirected graphs, edge $(A, B)$ is the same as $(B, A)$. In other words, all the edges are bi-directional for undirected graphs. A real-world example of an undirected graph is cities connected by only two-way roads. An example of an undirected graph is as follows:

Example 3

$$V=\{A,B,C\}\\ E=[(A,B),(A,C),(B,C)]$$

Connected Graph

A graph that has at least one path between every pair of vertices is called a connected graph. For example:

Disconnected Graph

A graph that doesn't have any path between one or more pairs of vertices is called a disconnected graph. Following is an example of a disconnected graph as we can't reach from vertex A to D.

Weighted Graph

Graphs whose edges have a weight associated with them are called weighted graphs. In the real world, most graphs are weighted, if we take the example of cities connected by roads as a graph, the length of the roads, the traffic congestion etc act as the weight for the edge. A weighted graph may be represented as follows, the weight is generally represented as a label for the edge.

Unweighted Graph

A graph in which all the edges don't have any weight is called an unweighted graph. An unweighted graph can also be supposed as a graph in which all the edges have equal weight so that any walk with an equal number of edges has the same cost.

Null Graph

An edgeless graph is called a null graph. Null graphs may or may not have vertices.

Simple Graph

An undirected, unweighted graph without any loops and multiple edges between any two nodes, is called a simple graph. A simple graph may or may not have cycles. Example:

Multi Graph

A graph that may have multiple edges between any two nodes and/or loops is called a multi graph. Example:

Complete Graph

A graph in which each vertex is connected to every other vertex is called a complete graph. Example:

Planar Graph

A graph that can be drawn in a plane without any intersecting edges is called a planar graph.