On this page & study actions
Assessed progress
Sign in and complete the verified MCQs to track mastery.
Unit 6: Graphs6 min read
Graph theory is one of the most vital branches of discrete mathematics, providing the structural framework for modeling pairwise relations between objects. Whether analyzing social networks, routing internet packets, or compiling dependencies in a program, graphs serve as the fundamental language of complex systems connectivity.
A graph is formally defined as an ordered pair:
where:
Undirected Edge: Directed Edge:
(u)-------(v) (u)------->(v)Different applications require different structural limitations on how edges behave. We classify graphs based on these constraints:
Simple Graph: Multigraph: Pseudograph (with Loops):
(A)---(B) (A)=====(B) (A)---(B)
| | | | | ) |
(C)---(D) (C)-----(D) (C)---(D)The behavior of individual vertices determines the structural dynamics of the entire graph.
In simple digraphs, the set of edges defines a binary relation on . We can classify these relationships using set-theoretic properties:
The converse (or dual or reversal) of a digraph is a digraph where:
Two graphs and are () if there exists a bijective function such that for any , if and only if .
A graph invariant is a property that remains unchanged under isomorphism. Examples include:
A major application of graph theory is route navigation and traversal.
Walk (Path): An alternating sequence of vertices and edges starting at and ending at :
The distance metric satisfies the following mathematical axioms:
Determining how components of a graph communicate is critical for assessing network reliability.
The reachable set of a node in a digraph is the set of all nodes such that a path exists from to .
A node base of a digraph is a minimal subset of vertices such that every vertex in is reachable from at least one vertex in .
Connectivity is classified into different levels of strength:
Weakly Connected Unilaterally Connected Strongly Connected
(Ignore directions) (At least one path) (Mutual paths)
(A)--->(B)--->(C) (A)--->(B)--->(C) (A)<==>(B)<==>(C)To process graphs programmatically, we map their topological structures to algebraic matrices.
For a graph with vertices, the adjacency matrix is an matrix where:
1 & \text{if there is an edge from vertex } i \text{ to vertex } j \\ 0 & \text{otherwise} \end{cases}$$ Key algebraic properties of $A$: * For undirected graphs, $A$ is symmetric ($A = A^T$). * The sum of elements in row $i$ of a digraph's adjacency matrix yields the outdegree of vertex $i$: $$\deg^+(i) = \sum_{j=1}^n a_{ij}$$ * The sum of elements in column $j$ yields the indegree of vertex $j$: $$\deg^-(j) = \sum_{i=1}^n a_{ij}$$ ### Path Computations If we compute the matrix power $A^k$ using standard matrix multiplication, the entry at row $i$ and column $j$ represents the **number of paths of length $k$** from vertex $i$ to vertex $j$. The **path matrix** $P$ (or reachability matrix) is a Boolean matrix indicating connectivity: $$p_{ij} = \begin{cases} 1 & \text{if there is a path of any length from } i \text{ to } j \\ 0 & \text{otherwise} \end{cases}$$ It can be computed using Boolean operations: $$P = A \lor A^{(2)} \lor A^{(3)} \dots \lor A^{(n)}$$ where $A^{(k)}$ denotes the Boolean product $A \land A^{(k-1)}$. Alternatively, we can define the path count matrix up to length $n$ as: $$B_n = \sum_{k=1}^n A^k$$ ### Incidence Matrix For an undirected graph with $V$ vertices and $E$ edges, the **incidence matrix** $M$ is a $V \times E$ matrix where: $$m_{ij} = \begin{cases} 1 & \text{if vertex } i \text{ is incident to edge } j \\ 0 & \text{otherwise} \end{cases}$$ ### Trade-offs: Matrices vs. Lists * **Adjacency Matrix**: Efficient ($O(1)$ lookup time) for dense graphs where $|E| \approx |V|^2$. Requires $O(|V|^2)$ memory. * **Adjacency List**: Efficient for sparse graphs where $|E| \ll |V|^2$. Requires $O(|V| + |E|)$ memory. Here is a practical Python implementation showing how to represent a graph using both formats and calculate vertex degrees: ```python class GraphRepresentation: def __init__(self, num_vertices): self.V = num_vertices # Initialize an empty Adjacency Matrix self.adj_matrix = [[0] * num_vertices for _ in range(num_vertices)] # Initialize an empty Adjacency List self.adj_list = {i: [] for i in range(num_vertices)} def add_edge(self, u, v, directed=False): # Update Adjacency Matrix self.adj_matrix[u][v] = 1 if not directed: self.adj_matrix[v][u] = 1 # Update Adjacency List self.adj_list[u].append(v) if not directed: self.adj_list[v].append(u) def get_degrees(self, directed=False): degrees = {} for i in range(self.V): if directed: # Sum of row i gives outdegree out_deg = sum(self.adj_matrix[i]) # Sum of column i gives indegree in_deg = sum(self.adj_matrix[j][i] for j in range(self.V)) degrees[i] = {"indegree": in_deg, "outdegree": out_deg} else: deg = sum(self.adj_matrix[i]) degrees[i] = {"degree": deg} return degrees # Example instantiation g = GraphRepresentation(4) g.add_edge(0, 1) g.add_edge(0, 2) g.add_edge(1, 2) g.add_edge(2, 3) print("Degrees in Undirected Graph:", g.get_degrees()) ``` --- ## 7. Structural Classes: Trees and Forests Trees are a foundational subset of graphs used to establish hierarchical order. ```text Tree (Acyclic & Connected) Forest (Disconnected Trees) (A) (A) (D) / \ / \ / \ (B) (C) (B) (C) (E) (F) ``` ### Definitions * **Tree**: A connected, undirected simple graph containing no cycles. * **Forest**: A collection of one or more disjoint trees. * **Rooted Tree**: A tree where one designated vertex is identified as the **root**, and all edges are implicitly directed away from it. ### Hierarchical Vocabulary * **Parent**: The vertex immediately preceding another on the path from the root. * **Child**: The vertex immediately following a parent node. * **Siblings**: Vertices that share the same parent node. * **Ancestors**: All vertices on the path from the root down to a given vertex. * **Descendants**: All vertices reachable from a given vertex. * **Leaf (Terminal Node)**: A vertex with no children. * **Internal Vertex (Branch Node)**: A vertex containing at least one child. * **Subtree**: A subgraph consisting of a designated node, all its descendants, and their incident edges. * **Level**: The path length from the root to a designated vertex. ### Tree Theorems 1. An undirected graph is a tree if and only if there is a **unique simple path** between any two of its vertices. 2. A tree with $n$ vertices always contains exactly $n - 1$ edges. ### Special Rooted Trees * **m-ary Tree**: A rooted tree where every internal node has at most $m$ children. * **Full m-ary Tree**: Every internal node has exactly $m$ children. * **Binary Tree**: A 2-ary tree (each internal node has at most two children: a left child and a right child). ### Tree Traversals Systematic traversal algorithms ensure that every node of an ordered rooted tree is visited exactly once: * **Preorder**: Visit root, then recursively traverse left subtree, then traverse right subtree. * **Inorder**: Recursively traverse left subtree, visit root, then traverse right subtree. * **Postorder**: Recursively traverse left subtree, traverse right subtree, and then visit root. --- ## 8. Classical Graph Theorems Several mathematical principles govern the paths and traversals within general graphs. ### Complete Graphs A **complete graph** $K_n$ is an undirected simple graph containing $n$ vertices where every distinct pair of vertices is connected by a unique edge. The total number of edges in $K_n$ is: $$E(K_n) = \frac{n(n-1)}{2}$$ ### Euler Paths and Circuits * **Euler Path**: A path that traverses every edge in a graph exactly once. * **Euler Circuit**: An Euler path that starts and ends at the exact same vertex. #### Existence Theorems * A connected multigraph has an **Euler circuit** if and only if every vertex in the graph has an **even degree**. * A connected multigraph has an **Euler path** (but not circuit) if and only if it has **exactly two vertices of odd degree**. These two vertices serve as the start and end points of the path. ### Hamilton Paths and Circuits * **Hamilton Path**: A simple path visiting every vertex in the graph exactly once. * **Hamilton Circuit**: A simple cycle visiting every vertex in the graph exactly once and returning to the start. #### Existence Theorems Unlike Euler paths, finding Hamilton circuits is an NP-complete problem. However, we have several key sufficient conditions: * **Dirac's Theorem**: If $G$ is a simple graph with $n \ge 3$ vertices, and every vertex $v \in G$ satisfies: $$\deg(v) \ge \frac{n}{2}$$ then $G$ contains a Hamilton circuit. * **Ore's Theorem**: If $G$ is a simple graph with $n \ge 3$ vertices, and for every pair of non-adjacent vertices $u$ and $v$: $$\deg(u) + \deg(v) \ge n$$ then $G$ contains a Hamilton circuit. > **Practical Application**: **Gray codes** represent a sequence of binary numbers where successive values differ by only one bit. This represents a Hamilton circuit on a hypercube graph $Q_n$. --- ## 9. Planar Graphs and Spatial Embedding A graph's topology can also be analyzed based on how it is drawn in physical space. ### Definitions * **Planar Graph**: A graph that can be drawn on a plane such that no two edges intersect except at their common endpoints. Such a drawing is a **planar representation**. * **Regions (Faces)**: A planar representation divides the plane into distinct geometric regions, including one unbounded outer region. ```text Planar Representation of K4: (A) / | \ / | \ (B) | (C) \ | / \ | / (D) (All edges drawn without crossings) ``` ### Euler's Formula For any connected planar simple graph with $v$ vertices, $e$ edges, and $r$ regions: $$r = e - v + 2$$ #### Corollaries for Non-planarity Proofs * **Corollary 1**: For a connected planar simple graph with $v \ge 3$ vertices, the number of edges is bounded by: $$e \le 3v - 6$$ * **Corollary 2**: If a connected planar simple graph has no cycles of length 3 (e.g., bipartite graphs) and $v \ge 3$: $$e \le 2v - 4$$ These corollaries help prove that the complete graph $K_5$ and the complete utility graph $K_{3,3}$ are **nonplanar**. ### Homeomorphism and Kuratowski's Theorem * **Elementary Subdivision**: The process of deleting an edge $\{u, v\}$ and replacing it with a new vertex $w$ and two edges $\{u, w\}$ and $\{w, v\}$. * **Homeomorphic Graphs**: Two graphs are homeomorphic if they can be obtained from the same graph by a sequence of elementary subdivisions. ```text Original Edge: Subdivided Edge: (u)-----------(v) (u)-----(w)-----(v) ``` * **Kuratowski's Theorem**: A graph is planar if and only if it does not contain a subgraph that is homeomorphic to $K_5$ or $K_{3,3}$. --- ## 10. Engineering and Computing Applications Graph theory is central to many systems and software engineering designs: * **Job Assignment and Matching**: Bipartite graphs match employees to tasks. Finding a complete matching ensures optimal resource allocation. * **Local Area Network (LAN) Topologies**: Network layouts (Star, Ring, Mesh, Hybrid) are analyzed as graph systems to evaluate fault tolerance, latency, and routing paths. * **Parallel Computation**: Processors are modeled as nodes and high-speed data buses as edges. Graph diameter and connectivity help determine the throughput of parallel algorithms (e.g., linear arrays, hypercubes, mesh networks). * **Chemical Structure Analysis**: Molecules (such as saturated hydrocarbons) are modeled as graphs where vertices are atoms and edges are chemical bonds. Isomer identification is mathematically equivalent to solving graph isomorphism problems. --- ## Summary * **Graphs** $G = (V, E)$ consist of **vertices** connected by **directed** or **undirected** edges. * **Simple graphs** contain no **loops** or **parallel edges**, whereas **multigraphs** allow parallel connections. * **Strong connectivity** in digraphs requires bidirectional path reachability between all vertex pairs, while **weak connectivity** only requires connectivity when edge directions are ignored. * **Adjacency matrices** represent topological connections algebraically; computing $A^k$ yields the number of paths of length $k$ between vertices. * **Trees** are connected, acyclic undirected graphs. A tree with $n$ vertices always contains $n-1$ edges. * **Euler circuits** require all vertices to have an **even degree**, while **Hamilton circuits** visit every vertex exactly once. * **Planar graphs** can be drawn in two dimensions without intersecting edges. They are bounded by Euler's Formula: $r = e - v + 2$. Non-planarity can be verified using **Kuratowski's Theorem** via subdivisions of $K_5$ and $K_{3,3}$.A graph is a mathematical structure consisting of vertices connected by edges, which can be directed or undirected.
The structural strength of a graph based on the existence of paths between its vertices, classified into weak, unilateral, and strong connectivity.
Methods of representing graph structures algebraically using adjacency and incidence matrices to facilitate computer execution and path analysis.
The property of a graph allowing it to be drawn on a two-dimensional plane without intersecting edges, bounded by Euler's relationship $r = e - v + 2$.
A special class of connected, acyclic undirected graphs used for hierarchical representation, navigable via systematic preorder, inorder, and postorder algorithms.
Test your understanding with 5 questions
If a connected planar simple graph has 10 vertices and 15 edges, how many regions does its planar representation divide the plane into?
Which of the following properties guarantees that an undirected simple graph is a tree?
Under what condition does a connected multigraph contain an Euler circuit?
Which of the following is NOT a requirement for a set of vertices $S$ to be a node base of a digraph?
What is the maximum number of edges in a connected planar simple graph with $v$ vertices where $v \ge 3$?
The length of the walk is (the number of edges).
Closed Walk: A walk where the start and end vertices are identical ().
Trail: A walk in which all edges are distinct.
Simple Path (Node-Elementary Path): A walk in which all vertices are distinct.
Elementary Cycle: A closed walk of length where all intermediate vertices are distinct.
Acyclic Digraph: A directed graph containing no cycles, commonly referred to as a DAG (Directed Acyclic Graph).
6 Modules
6 Modules