The Project | About Us | Contribute | Donations | License
HOME My courses Completed
◄ Previous
◄

Introduction to Graphs

Next ►
►

Graphs are a fundamental data structure in computer science, used to model pairwise relations between objects. They are widely used in various fields such as social networks, transportation networks, and computer networks. In this section, we will introduce the basic concepts of graphs, their components, and their types.

Key Concepts

  1. Definition of a Graph

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

  • \( V \) is a set of vertices (or nodes).
  • \( E \) is a set of edges (or arcs), where each edge connects a pair of vertices.

  1. Components of a Graph

  • Vertices (Nodes): The fundamental units of a graph.
  • Edges (Arcs): The connections between the vertices.

  1. Types of Graphs

  • Undirected Graph: A graph in which edges have no direction. The edge \( (u, v) \) is identical to \( (v, u) \).
  • Directed Graph (Digraph): A graph in which edges have a direction. The edge \( (u, v) \) is not identical to \( (v, u) \).
  • Weighted Graph: A graph in which edges have weights (or costs) associated with them.
  • Unweighted Graph: A graph in which edges do not have weights.

  1. Graph Terminology

  • Adjacent Vertices: Two vertices are adjacent if they are connected by an edge.
  • Degree of a Vertex: The number of edges incident to a vertex. In a directed graph, we distinguish between in-degree and out-degree.
  • Path: A sequence of vertices where each adjacent pair is connected by an edge.
  • Cycle: A path that starts and ends at the same vertex.
  • Connected Graph: A graph in which there is a path between every pair of vertices.
  • Subgraph: A graph formed from a subset of the vertices and edges of another graph.

Examples

Example 1: Undirected Graph

Consider the following undirected graph:

    A
   / \
  B---C
   \ /
    D
  • Vertices: \( V = {A, B, C, D} \)
  • Edges: \( E = {(A, B), (A, C), (B, C), (B, D), (C, D)} \)

Example 2: Directed Graph

Consider the following directed graph:

    A → B
    ↓   ↓
    C ← D
  • Vertices: \( V = {A, B, C, D} \)
  • Edges: \( E = {(A, B), (A, C), (B, D), (D, C)} \)

Practical Example: Graph Representation in Python

Graphs can be represented in various ways in programming. Two common representations are the adjacency matrix and the adjacency list.

Adjacency Matrix

An adjacency matrix is a 2D array of size \( V \times V \) where \( V \) is the number of vertices. The element at row \( i \) and column \( j \) is 1 if there is an edge from vertex \( i \) to vertex \( j \), and 0 otherwise.

# Example of an adjacency matrix for an undirected graph
graph = [
    [0, 1, 1, 0],  # Connections for vertex A
    [1, 0, 1, 1],  # Connections for vertex B
    [1, 1, 0, 1],  # Connections for vertex C
    [0, 1, 1, 0]   # Connections for vertex D
]

Adjacency List

An adjacency list is an array of lists. The index of the array represents a vertex, and the list at each index contains the vertices adjacent to it.

# Example of an adjacency list for an undirected graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

Practical Exercise

Exercise 1: Create a Graph

Create a graph using both adjacency matrix and adjacency list representations for the following undirected graph:

    1
   / \
  2---3
   \ /
    4

Solution

Adjacency Matrix

# Adjacency matrix representation
graph_matrix = [
    [0, 1, 1, 0],  # Connections for vertex 1
    [1, 0, 1, 1],  # Connections for vertex 2
    [1, 1, 0, 1],  # Connections for vertex 3
    [0, 1, 1, 0]   # Connections for vertex 4
]

Adjacency List

# Adjacency list representation
graph_list = {
    1: [2, 3],
    2: [1, 3, 4],
    3: [1, 2, 4],
    4: [2, 3]
}

Common Mistakes and Tips

  • Mistake: Confusing directed and undirected graphs. Remember that in directed graphs, the direction of edges matters.
  • Tip: Always double-check the connections when creating adjacency matrices or lists to ensure accuracy.

Conclusion

In this section, we introduced the basic concepts of graphs, including their components and types. We also explored how to represent graphs using adjacency matrices and lists. Understanding these fundamentals is crucial for working with more advanced graph algorithms and applications, which we will cover in subsequent sections.

◄ Previous
◄
Next ►
►
The Project | About Us | Contribute | Donations | License
© Copyright 2024. All rights reserved