Skip to content

Chapter 9: Graphs – Basic Concepts

(TB1 Ch.5, Article 1)

1. Definition of a Graph

A graph (G) is a pair: [ G = (V, E) ]

  • (V) = set of vertices (nodes)
  • (E) = set of edges (connections between vertices)

Edges may be:

  • Undirected: connection has no direction
  • Directed: connection has a direction (arc)

Example 1: Undirected Graph

[ V = {A, B, C}, \quad E = {{A,B}, {B,C}, {C,A}} ]

Graph: triangle connecting A, B, C

Example 2: Directed Graph (Digraph)

[ V = {1,2,3}, \quad E = {(1,2), (2,3)} ]

  • Edge (1,2) is from 1 to 2
  • Edge (2,3) is from 2 to 3

2. Types of Graphs

  1. Simple Graph: No loops or multiple edges
  2. Multigraph: Multiple edges allowed
  3. Pseudograph: Loops and multiple edges allowed
  4. Directed Graph (Digraph): Edges have direction
  5. Weighted Graph: Each edge has a weight/cost

3. Degree of a Vertex

Undirected Graph

[ \text{deg}(v) = \text{number of edges incident on } v ]

Handshake Lemma: [ \sum_{v \in V} \text{deg}(v) = 2|E| ]

Directed Graph

  • In-degree ((\deg^-(v))): number of edges ending at v
  • Out-degree ((\deg^+(v))): number of edges starting from v

[ \sum_{v \in V} \deg^-(v) = \sum_{v \in V} \deg^+(v) = |E| ]

Example

Undirected graph: V = {A,B,C}, E = {{A,B},{B,C},{C,A}}

  • deg(A) = 2, deg(B) = 2, deg(C) = 2
  • Sum = 6 = 2 * |E| ✅

4. Special Graphs

  1. Complete Graph (K_n): Every vertex connected to every other vertex

  2. Edges: (|E| = \frac{n(n-1)}{2})

  3. Null Graph: No edges

  4. Cycle Graph (C_n): Forms a single cycle connecting all vertices

  5. Path Graph (P_n): Vertices connected in a single line

5. Graph Representation Methods

  1. Adjacency Matrix

  2. (n \times n) matrix (A) for (n) vertices

  3. (A[i][j] = 1) if edge exists, else 0

  4. Adjacency List

  5. For each vertex, store list of adjacent vertices

  6. More memory-efficient for sparse graphs

Example

Graph: V = {1,2,3}, E = {(1,2),(2,3)}

Adjacency Matrix: [ \begin{bmatrix} 0 & 1 & 0 \ 1 & 0 & 1 \ 0 & 1 & 0 \end{bmatrix} ]

Adjacency List:

  • 1: 2
  • 2: 1,3
  • 3: 2

6. Graph Terminology

  • Walk: Sequence of vertices where consecutive vertices are connected
  • Path: Walk with no repeated vertices
  • Cycle: Path that starts and ends at the same vertex
  • Connected Graph: Path exists between every pair of vertices
  • Disconnected Graph: Not connected

Example

V = {A,B,C,D}, E = {{A,B},{B,C}}

  • Walk: A → B → C
  • Path: A → B → C
  • Cycle: None (graph not cyclic)
  • Connected? No, D is isolated

7. Applications in CS

  • Networking (routers & connections)
  • Shortest path algorithms (Dijkstra, Bellman-Ford)
  • Task scheduling (dependency graphs)
  • Social networks (friend connections)
  • Compiler analysis (control flow graphs)

Comments