Chapter 4.1

Introduction to Graphs

A graph is a non-linear data structure used to represent relationships between pairs of elements. It is widely used in various applications like social networks, transportation systems, and computer networks.

A graph GGG is defined as:

G=(V,E)G = (V, E)G=(V,E)

Where:

• VVV is a non-empty set of vertices (nodes).

• EEE is a set of edges, where each edge represents a connection between a pair of vertices.

Key Components

1. Vertices (VVV):

   • The points or nodes in the graph.

   • Represent entities in a system (e.g., cities, users, tasks).

2. Edges (EEE):

   • The connections between pairs of vertices.

   • Represent relationships or interactions (e.g., roads, friendships).

---

Types of Graphs

1. Directed Graph (Digraph): Edges have a direction. Example: (A→B)(A \rightarrow B)(A→B) implies a one-way relationship.

2. Undirected Graph: Edges have no direction. Example: (A−B)(A - B)(A−B) implies a two-way relationship.

3. Weighted Graph: Edges have associated weights (e.g., distances, costs). Example: (A−B,w=5)(A - B, w = 5)(A−B,w=5).

4. Unweighted Graph: All edges are equal (no weights).

---

Example

Consider a graph GGG with:

• Vertices: V={A,B,C,D}V = \{A, B, C, D\}V={A,B,C,D}

• Edges: E={(A,B),(B,C),(C,D),(A,D)}E = \{(A, B), (B, C), (C, D), (A, D)\}E={(A,B),(B,C),(C,D),(A,D)}

Graphically, it can be represented as:

• Nodes: Circles representing A,B,C,DA, B, C, DA,B,C,D.

• Edges: Lines connecting the nodes

Basic Terminology of Graphs

Understanding the fundamental terms related to graphs is essential for working with this data structure effectively. Below are the key concepts:

---

1. Vertex (or Node):

• Definition: A vertex is a fundamental unit of a graph. Vertices represent entities such as people, places, or objects in the system being modeled.

• Representation: Vertices are often depicted as circles or dots in visual representations.

• Example: In a social network, each person could be represented as a vertex.

---

2. Edge:

• Definition: An edge represents a connection or relationship between two vertices in a graph.

• Types:

  • Directed Edge: Specifies a direction (e.g., A→BA \rightarrow BA→B).

  • Undirected Edge: Does not specify a direction (e.g., A−BA - BA−B).

  • Weighted Edge: Has an associated value or cost (e.g., distance or time).

  • Unweighted Edge: No value is associated; all edges are treated equally.

• Example: A road connecting two cities could be represented as an edge.

---

3. Degree:

• Definition: The degree of a vertex is the number of edges connected to it.

• Directed Graph:

  • In-degree: Number of edges directed toward the vertex.

  • Out-degree: Number of edges directed away from the vertex.

• Undirected Graph: The degree is simply the count of edges connected to the vertex.

• Example: In a friendship graph, the degree of a person (vertex) is the number of friends (edges) they have.

---

4. Path:

• Definition: A path is a sequence of vertices connected by edges.

• Types:

  • Simple Path: No vertex is repeated.

  • Cycle: A path that starts and ends at the same vertex.

• Example: A route between two cities is a path.

---

5. Cycle:

• Definition: A cycle is a path that begins and ends at the same vertex.

• Example: A→B→C→AA \rightarrow B \rightarrow C \rightarrow AA→B→C→A.

---

6. Connectedness:

• Definition: A graph is connected if there is a path between every pair of vertices.

  • A disconnected graph has one or more components that are isolated from the rest of the graph.

• Example: A computer network where all devices can communicate is a connected graph.

---

7. Component:

• Definition: A component is a connected subgraph of a graph. It consists of vertices and edges that are connected to one another but not to the rest of the graph.

• Example: In a disconnected graph of two social networks, each network is a component.

---

8. Directed Graph:

• Definition: A graph where edges have a specified direction (arcs).

• Example: A task dependency graph showing which tasks must precede others.

---

9. Undirected Graph:

• Definition: A graph where edges have no direction.

• Example: A friendship graph, where friendships are mutual.

---

10. Weighted Graph:

• Definition: A graph where edges are assigned a weight or value.

• Example: A transportation graph where weights represent distances.

---

11. Adjacent Vertices:

• Definition: Two vertices are adjacent if they are directly connected by an edge.

• Example: AAA and BBB are adjacent if there is an edge (A−B)(A - B)(A−B).

---

12. Incidence:

• Definition: A vertex is said to be incident on an edge if it is one of the edge's endpoints.

• Example: In (A−B)(A - B)(A−B), both AAA and BBB are incident on the edge.

---

13. Subgraph:

• Definition: A subgraph is a smaller graph formed from a subset of the vertices and edges of a larger graph.

• Example: Removing some vertices and edges from a graph to analyze a specific part.

---

14. Complete Graph:

• Definition: A graph where every vertex is connected to every other vertex by an edge.

• Example: For n=4n = 4n=4, a complete graph would have 666 edges, connecting all 444 vertices.

Graph Representation in Data Structures

Graphs can be represented in multiple ways based on their structure and the requirements of the application. The two primary methods are Adjacency Matrix and Adjacency List.

---

1. Adjacency Matrix

• Definition: An adjacency matrix is a 2D array or matrix where:

  • Each row and column corresponds to a vertex in the graph.

  • The value at position (i,j)(i, j)(i,j):

    • 111: There is an edge between vertex iii and vertex jjj.

    • 000: No edge exists between vertex iii and vertex jjj.

• Use Case: Best suited for dense graphs, where the number of edges is close to the maximum possible.

• Advantages:

  • Easy to implement and query if an edge exists between two vertices.

  • Simple to represent weighted graphs by replacing 111 with the weight of the edge.

• Disadvantages:

  • Inefficient for sparse graphs due to wasted space.

  • Takes O(V2)O(V^2)O(V2) space, where VVV is the number of vertices.

• Example: For a graph with vertices A,B,CA, B, CA,B,C and edges A→B,A→C,B→CA \rightarrow B, A \rightarrow C, B \rightarrow CA→B,A→C,B→C:

  Adjacency Matrix:

  [011001000]\begin{bmatrix} 0 & 1 & 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end{bmatrix}​000​100​110​​

  Here, 111 in row AAA and column BBB indicates an edge from AAA to BBB.

---

2. Adjacency List

• Definition: An adjacency list uses a list of lists or a dictionary where:

  • Each vertex is a key.

  • Its value is a list of adjacent vertices.

• Use Case: Best suited for sparse graphs, where the number of edges is much smaller than the maximum possible.

• Advantages:

  • Space-efficient for sparse graphs.

  • Easy to iterate through neighbors of a vertex.

• Disadvantages:

  • Slower to check if a specific edge exists compared to an adjacency matrix.

• Example: For the same graph with vertices A,B,CA, B, CA,B,C and edges A→B,A→C,B→CA \rightarrow B, A \rightarrow C, B \rightarrow CA→B,A→C,B→C:

  Adjacency List:

  pythonCopy code{
      'A': ['B', 'C'],
      'B': ['C'],
      'C': []
  }

---

Comparison of Adjacency Matrix vs Adjacency List

Aspect	Adjacency Matrix	Adjacency List
Space Complexity	O(V2)O(V^2)O(V2)	O(V+E)O(V + E)O(V+E)
Edge Lookup	O(1)O(1)O(1)	O(V)O(V)O(V) in worst case
Best for Graph Type	Dense Graphs	Sparse Graphs
Ease of Traversal	Moderate	Efficient for neighbors

---

Simplified Example in Python

1. Adjacency Matrix Implementation:

   pythonCopy code# Graph with vertices A, B, C
   adjacency_matrix = [
       [0, 1, 1],  # A -> B, A -> C
       [0, 0, 1],  # B -> C
       [0, 0, 0]   # C -> None
   ]
   print(adjacency_matrix)

2. Adjacency List Implementation:

   pythonCopy code# Graph with vertices A, B, C
   adjacency_list = {
       'A': ['B', 'C'],
       'B': ['C'],
       'C': []
   }
   print(adjacency_list)