Graphs: Introduction

Definition

A graph is a mathematical and data-structural representation of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices.

Formally, a graph can be written as:

G = (V, E)

where:

V

• = set of vertices

E

• = set of edges connecting vertices

Example

If a graph has vertices:

• A, B, C, D

and edges:

• A—B
• A—C
• B—D

then the graph represents connections between these objects.

Basic terminology

Vertex / Node

• : A point in the graph

Edge / Link

• : A connection between two vertices

Path

• : A sequence of edges leading from one vertex to another

Degree

• : Number of edges connected to a vertex

Adjacent vertices

• : Vertices directly connected by an edge

Graphs may be:

Directed

• : edges have direction

Undirected

• : edges have no direction

Weighted

• : edges carry values such as distance, cost, or time

Unweighted

• : edges only indicate connection

---

Main Content

1. Graph Representation

Adjacency Matrix and Adjacency List

A graph can be stored in different ways depending on the number of vertices, number of edges, and the kind of operations needed. Two of the most common representations are:

• Adjacency Matrix: A 2D matrix where cell (i, j) indicates whether an edge exists between vertex i and vertex j, or stores the weight of the edge.
• Adjacency List: Each vertex stores a list of all vertices directly connected to it.

Example of adjacency matrix for 3 vertices A, B, C:

      A B C
    A  0 1 1
    B  1 0 0
    C  1 0 0

This means A is connected to B and C, while B and C are connected only to A.

Choosing the Right Representation

The choice depends on efficiency needs:

• Adjacency matrix is simple and fast for checking whether two vertices are connected.
• Adjacency list is memory-efficient for sparse graphs, where relatively few edges exist.

---

2. Types of Graphs

Directed and Undirected Graphs

In an undirected graph, an edge between two vertices works both ways. For example, if A is connected to B, then B is connected to A.
In a directed graph (digraph), each edge has a direction. For example, A → B means movement is allowed from A to B, but not necessarily from B to A.

Directed graph example:

  A → B → C
  ↑    ↓
  D ←—— 

Weighted and Unweighted Graphs

In a weighted graph, each edge has a numerical value. This value may represent:

• distance
• cost
• time
• capacity

In an unweighted graph, all edges are considered equal. This is often used when only connectivity matters, not the strength or length of the connection.

Example:

• A—B with weight 5
• A—C with weight 2
• B—C with weight 7

Such graphs are common in route planning and network optimization.

---

3. Graph Terminology and Properties

Degree, Path, Cycle, and Connectivity

Important graph properties help describe structure and behavior:

• Degree: number of edges incident to a vertex
• Path: a route from one node to another
• Cycle: a path that starts and ends at the same vertex
• Connected graph: every vertex can be reached from every other vertex
• Disconnected graph: at least one vertex cannot be reached from another

Example of a cycle:

  A — B
  |   |
  D — C

In this square-like graph, you can travel from A to B to C to D and back to A, forming a cycle.

Self-loops and Parallel Edges

Some graphs may contain:

• Self-loop: an edge from a vertex to itself
• Parallel edges: more than one edge between the same pair of vertices

These are often studied in more advanced graph theory, though many basic graph algorithms assume simple graphs without them.

Simple Graphs

A simple graph contains:

• no self-loops
• no multiple edges between the same pair of vertices

Simple graphs are widely used because they are easier to analyze and implement.

---

Working / Process

1. Identify the objects and connections

• First, determine what the vertices and edges represent in the problem.
• Example: In a road map, cities can be vertices and roads can be edges.
• In a social network, people are vertices and friendships are edges.

2. Choose a graph representation

• Decide whether to use an adjacency matrix or adjacency list.
• If the graph has many edges, a matrix may be convenient.
• If the graph is large but sparse, an adjacency list is usually better.

3. Analyze or traverse the graph

• Once the graph is built, algorithms can explore it.
• Common operations include:
  • checking if two nodes are connected
  • finding all neighbors of a node
  • exploring reachable nodes
  • detecting cycles
• Traversals such as BFS and DFS are commonly used to process graph structures.

---

Advantages / Applications

Represents real-world relationships naturally

Graphs are ideal for modeling systems where entities are connected, such as friendships, routes, communication links, and dependencies.

Supports powerful algorithms

Many essential algorithms work on graphs, including shortest path algorithms, minimum spanning tree algorithms, topological sorting, and connectivity checking.

Useful across many domains

Graphs are used in:

• social media networks
• navigation systems
• computer networking
• web page ranking
• project scheduling
• recommendation engines
• circuit design

---

Summary

• A graph is a structure made of vertices and edges.
• It is used to represent relationships and connections.
• Important terms to remember: vertex, edge, path, cycle, degree, directed graph, weighted graph.