Discrete Mathematics - Graph Theory
DMA 25/26 Week 4 - Aarbaz Alam, LSBU
Course References
Chapters referenced: 1 & 2, Chapter 10, Sections 1 - 5.
Graph Theory
Definition of a Graph
A graph $G(V, E)$ is defined as an algebraic structure consisting of:
Two sets:
Vertices/Nodes Set $(V)$:
Denoted as: $V = {v1, v2, v_3, \ldots}$ where $V$ is a non-empty set of vertices.
Edges/Links Set $(E)$:
Denoted as: $E = {e1, e2, e3, \ldots}$ where edges connect pairs of vertices $vi, v_j$.
Graph Representation
Graphs can be represented visually through diagrams.
Example representation:
Vertices: $V = {v1, v2, v3, v4, v_5}$
Edges: $E = {e1, e2, e3, e4, e5, e6, e_7}$
Alternatively can be compactly noted as:
$V = v_i,$ where $1 \leq i \leq 5$
$E = e_j,$ where $1 \leq j \leq 7 $
Graph as a Relation
Definition of a relation:
Given sets:
$S = {a, b, c}$
The Cartesian product $S^2$ generates all possible ordered pairs:
$S^2 = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a), (c, b), (c, c)}$
A subset of this relation forms a graph $G(V,E)$ where:
$V = S$ and $E \subseteq S^2$
Graph Terminologies
Key Definitions
Adjacency:
Two vertices are adjacent if they are endpoints of the same edge:
$\text{adj}(vi, vj) \rightarrow e_{i,j} \in E$
Example: $v1$ & $v2$, $v2$ & $v2$.
Incidence:
An edge is incident to a vertex if it is one of its endpoints:
Example: $v1$ & $e4$, $v2$ & $e1$.
Degree:
The degree of a vertex $vi$, denoted as $ ext{deg}(vi)$, is the number of edges incident to it:
$\text{deg}(vi) = |{vj | \text{adj}(vi, vj)}|$.
Examples: $ ext{deg}(v1) = 3$, $ ext{deg}(v2) = 3$.
Pendent Vertex/Leaf:
A vertex with degree = 1 (e.g., $v_5$).
Isolated Vertex:
A vertex with degree = 0.
Parallel Edges/Chords:
When a pair of adjacent vertices has multiple edges between them:
Example: $\ ext{Parallel Edges: } {e4, e5}$ is parallel between $v1$ & $v3$.
Self Loop:
An edge with identical endpoints:
Example: $e1 = e{2,2}$.
Types of Graphs
Undirected Graph
Graph where edges have no direction.
The connection between any two vertices is bidirectional:
$\text{Edge } (u, v) \equiv (v, u)$.
Example: Friendship networks, where if A is a friend of B, then B is also a friend of A.
Represented as: $G = (V, E)$ where $E$ is a set of unordered pairs.
Directed Graph (Digraph)
Graphs where edges have a specific direction.
Connections are not bidirectional:
Edge $(u, v) \neq (v, u)$ - connection goes from $u$ to $v$ only.
Often depicted with arrows indicating direction.
Example: Following relationships on social platforms, e.g., Instagram follower graph.
Represented as: $G = (V, E)$ where $E$ is a set of ordered pairs.
Graph Types and Properties
Type | Edges | Multiple Edges Allowed? | Loops Allowed? |
|---|---|---|---|
Simple Graph | Undirected | No | No |
Multigraph | Undirected | Yes | No |
Pseudograph | Undirected | Yes | Yes |
Simple Directed Graph | Directed | No | No |
Directed Multigraph | Directed | Yes | Yes |
Mixed Graph | Directed and Undirected | Yes | Yes |
Problem Example: Königsberg Bridge Problem
Problem statement from the historical perspective:
There are 4 islands, labeled $A, B, C, D$, connected by 7 bridges.
Objective:
Find a path that allows one to start from any of the islands, traverse all 7 bridges without repeating any, and return to the start point.
Reference: Königsberg Bridge
Graph Applications in Real Life
Example 1: Google Maps
Graph representation of different locations, roadways, and distances.
Example 2: London Tube
The tube network can be represented as a graph where stations are vertices and the lines are the edges connecting these vertices.
Example 3: Facebook Graph API
Demonstrates the social network as a graph using relationships:
Connections include:
friends, likes, follows, etc.
Example 4: Network Topologies in Computer Science
Utilizing graphs to represent network topologies, routers, and connections in operating systems.
Graph Classifications
Finite & Infinite Graph
A graph $G(V, E)$ is:
Finite Graph: If $V$ and $E$ are both finite sets.
Infinite Graph: If either vertex set or edge set is infinite.
Regular Graph
A graph where all vertices have equal degree.
Null Graph
A graph that has a finite vertex set but does not have any edges:
Example: $G(V, E)$ where $E = \emptyset$ and $V \neq \emptyset$.
Isomorphism in Graphs
Definition and Conditions
Isomorphism:
Two graphs $G1$ and $G2$ are isomorphic ($G1 \approx G2$) if they have:
A one-to-one correspondence between their vertices, edges, and adjacencies.
Necessary Conditions for Isomorphism:
Same number of vertices.
Same number of edges.
Identical sets of vertex degrees.
Testing for Isomorphism
Step 1: Evaluate:
Number of vertices:
$|V1| = 5$ and $|V2| = 5$.
Number of edges:
$E1 = 6$ and $E2 = 6$.
Degree sets:
$D1 = {3, 2, 3, 3, 1}$ and $D2 = {3, 2, 3, 3, 1}$.
Step 2: Test if $G1 \approx G2$.
Properties of Subgraphs
Definition:
$G1(V1, E1)$ is a subgraph of $G2(V2, E2)$ written as $G1 \subseteq G2$ if:
$V1 \subseteq V2$ and $E1 \subseteq E2$.
Properties:
Reflexive: Every graph is a subgraph of itself.
Antisymmetric: Subgraph relation is non-commutative except for isomorphic graphs.
Transitive: A subgraph of a subgraph is also a subgraph.
Every vertex and edge in a graph is trivially considered a subgraph.
Walk, Path, and Circuit Definitions
Walk/Chain
Definition: A finite alternating sequence of vertices and edges beginning and ending with vertices.
No edge appears more than once.
End points are called Terminal Vertices; others are Intermediate Vertices.
Closed Walk: If a vertex is revisited; Open Walk: otherwise.
Path
Definition: An open walk where no redundant vertex exists.
Circuit
Definition: A closed walk, where the terminals are identical.
Denoted as $C_n$ for a circuit of n vertices.
Graph Connectivity
Connected Graph
A graph is connected if there is at least one path between every pair of vertices.
If not, the graph is considered disconnected.
Components: In a disconnected graph, each isolated connected graph is referred to as a component.
Eulerian Path and Circuit
Definitions
Euler Line: A walk that traverses every edge exactly once; an open walk.
Euler Circuit: A closed walk that visits every edge exactly once.
Euler Graph: A graph containing at least one Euler line.
Arbitrarily Traceable Graph: A graph from which an Euler line can be drawn from any origin point.
Hamiltonian Path and Circuit
Definition:
Hamiltonian Path: A walk visiting every vertex exactly once (open walk).
Hamiltonian Circuit: Returns to the starting vertex while visiting every vertex exactly once (closed walk).
Complete Graphs
A complete graph (or mesh or clique) is defined by maximal connectivity:
Number of edges $= \frac{n(n-1)}{2}$ for n vertices.
Denoted as $K_n$.
Graph Colouring Problem
Given a graph $G(V, E)$:
Each vertex is assigned a color such that no two adjacent vertices share the same color.
The minimum number of colors required is known as the Chromatic Number, denoted $\chi(G) \in \mathbb{N}$.
Key Observations:
$\chi(K_n) = n$
$\chi(C_n) = 2$ if n is even;
$\chi(C_n) = 3$ if n is odd (and greater than 1).
Theorems in Graph Theory
For a connected graph, the edge set is bounded by $E \in [n - 1, \frac{n(n-1)}{2}]$.
The sum of the degrees of all vertices is twice the number of edges:
$\sum d(v_i) \in V = 2|E|.$
The sum of degrees of all odd-degree vertices is an even number.
A disconnected graph can be partitioned into components.
There exists a path between pairs of odd-degree vertices in any graph.
A simple graph with n nodes and k components has a maximum of $\frac{(n-k)(n-k+1)}{2}$ edges.
All vertices of an Euler graph have even degrees.
In a complete graph with n vertices, there are $\frac{n-1}{2}$ edge-disjoint Hamiltonian circuits when n is odd and $\geq 3$.
Questions & Thank You
Any questions regarding the lecture content?
Thank you for your attention!