Basic Concepts of Graphs

Basic Concepts of Graphs

A graph is a mathematical structure used to model pairwise relationships between objects. A graph consists of two main components: vertices (or nodes) and edges (or links). Vertices represent the objects, while edges represent the connections between these objects.

Definition of a Graph

A graph G can be defined as an ordered pair G = (V, E), where:

• V is a set of vertices.
• E is a set of edges, which are 2-element subsets of V.

For example, consider a graph with vertices V = {A, B, C} and edges E = {{A, B}, {B, C}}. This graph has three vertices and two edges.

Types of Graphs

Graphs can be classified into various types based on their properties:

• Undirected Graphs: In an undirected graph, the edges have no direction. The edge {A, B} is the same as the edge {B, A}.
• Directed Graphs (Digraphs): In a directed graph, the edges have a direction. The edge (A, B) is not the same as (B, A).
• Weighted Graphs: In weighted graphs, edges carry weights (or costs). For example, an edge between two vertices may represent a distance or a cost.
• Simple Graphs: A simple graph does not contain multiple edges between the same pair of vertices and does not contain loops (edges that connect a vertex to itself).

Graph Representation

Graphs can be represented in various ways, including:

• Adjacency Matrix: A square matrix used to represent a graph. The element at row i and column j indicates the presence or absence of an edge between vertices i and j.
• Adjacency List: A collection of lists. Each vertex has a list of the vertices it is connected to.

Adjacency Matrix Example

Consider a simple undirected graph G with vertices V = {A, B, C} and edges E = {{A, B}, {B, C}}. The adjacency matrix for this graph is:

    A  B  C
A [ 0, 1, 0 ]
B [ 1, 0, 1 ]
C [ 0, 1, 0 ]

In this matrix:

• The rows and columns represent the vertices.
• A value of 1 indicates that there is an edge between the corresponding vertices.
• A value of 0 indicates no edge exists.

Adjacency List Example

The same graph can be represented as an adjacency list:

A: B
B: A, C
C: B

In this representation:

• Each line represents a vertex.
• After the colon, the connected vertices are listed.

Degree of a Vertex

The degree of a vertex is the number of edges connected to it. For directed graphs, we distinguish between:

• In-degree: The number of incoming edges to a vertex.
• Out-degree: The number of outgoing edges from a vertex.

For example, consider a directed graph with vertices V = {A, B, C} and edges E = {(A, B), (B, C), (C, A), (A, C)}. The degrees are as follows:

• Vertex A: Out-degree = 2 (edges to B and C), In-degree = 1 (edge from C).
• Vertex B: Out-degree = 1 (edge to C), In-degree = 1 (edge from A).
• Vertex C: Out-degree = 1 (edge to A), In-degree = 2 (edges from B and A).

Connected Graphs

A graph is connected if there is a path between any two vertices. In a directed graph, it is strongly connected if there is a directed path from each vertex to every other vertex.

Paths and Cycles

A path is a sequence of vertices where each adjacent pair is connected by an edge. A cycle is a path that starts and ends at the same vertex, with at least one edge. For example, in the graph with vertices V = {A, B, C} and edges E = {{A, B}, {B, C}, {C, A}}, the sequence A → B → C → A forms a cycle.

Graph Traversal

Graph traversal refers to the process of visiting all the vertices in a graph. There are two common methods of graph traversal:

• Depth-First Search (DFS): This method explores as far as possible along each branch before backtracking.
• Breadth-First Search (BFS): This method explores all the neighbour vertices at the present depth before moving on to vertices at the next depth level.

Depth-First Search Example

Consider the following undirected graph:

  A
 / \
B   C
 \ / 
 D

Starting from vertex A, a possible DFS traversal order could be A → B → D → C.

Breadth-First Search Example

Using the same graph, a possible BFS traversal order starting from vertex A could be A → B → C → D.

Applications of Graphs

Graphs are widely used in various fields, including:

• Computer Networks: To model connections between computers.
• Social Networks: To represent relationships between individuals.
• Transportation: To model routes between locations.
• Biology: To represent relationships between species in ecological studies.

Summary

• A graph consists of vertices and edges.
• Graphs can be undirected or directed, weighted or unweighted, and simple or complex.
• Graphs can be represented using adjacency matrices or adjacency lists.
• The degree of a vertex is the number of edges connected to it.
• A path is a sequence of edges connecting vertices, while a cycle is a path that starts and ends at the same vertex.
• Graph traversal methods include depth-first search and breadth-first search.

Check your understanding

1. Define a graph and its components.
2. What is the difference between an undirected graph and a directed graph?
3. How would you represent a graph using an adjacency list?
4. What is the degree of a vertex and how is it calculated?