Real-World Adjacency Analysis in Sensor Networks
A research team is deploying a network of 5 sensors in a forest to detect fires. These sensors record communication events with each other, including signal strengths, every minute. The data is time-stamped and collected over 24 hours. (a) Describe the process of integrating this real-world data set into a mathematical format suitable for constructing […]
Maximum Throughput in a Transportation Network using an Adjacency Matrix
A city’s transportation network is modeled by a directed graph with 5 intersections (nodes), where each directed edge represents a road with a specified capacity in vehicles per hour. The network is represented by the following adjacency matrix: Row 1: [0, 30, 0, 10, 0] Row 2: [0, 0, 25, 0, 0] Row 3: [0, […]
Matrix-Based Graph Analysis for Connectivity
Consider a directed graph representing a network of 5 cities. The connections between the cities are recorded in an adjacency matrix A where the entry \(a_{ij}\) is 1 if there is a direct route from city i to city j, and 0 otherwise. The adjacency matrix A is given as follows: \( A = \begin{bmatrix} […]
Cycle Detection in an Adjacency Matrix
Consider the following adjacency matrix representing an undirected graph with 4 vertices: Row 1: [0, 1, 1, 0] Row 2: [1, 0, 1, 0] Row 3: [1, 1, 0, 0] Row 4: [0, 0, 0, 0] (a) Reconstruct the graph from the given adjacency matrix and identify any cycle(s) present. (b) Determine whether the graph […]
Determining Bipartiteness from an Adjacency Matrix
Consider the following adjacency matrix representing an undirected graph with 4 vertices: Row 1: 0, 1, 1, 0 Row 2: 1, 0, 0, 1 Row 3: 1, 0, 0, 1 Row 4: 0, 1, 1, 0 Using a 2-coloring approach, determine whether the graph is bipartite. In your answer, first verify the symmetry of the […]
Connectivity Analysis in Directed Networks
Consider a directed network represented by the following adjacency matrix: Row 1: 0 1 0 0 Row 2: 0 0 1 0 Row 3: 1 0 0 0 Row 4: 0 0 0 0 (a) Identify the strongly connected components of the network. (b) Explain the implication of a row in the adjacency matrix consisting […]
Network Path Analysis Using Matrix Powers
A transportation network is modeled using an adjacency matrix \(A\) that represents the direct connectivity between intersections. Given the matrix \(A\) for a network of 4 intersections, perform the following tasks: (a) Compute \(A^3\) to determine the number of three-step paths between intersections. (b) Explain what the entries in \(A^3\) signify regarding network connectivity. (c) […]
Multi-Step Route Analysis Using Matrix Powers
Consider the following 3×3 adjacency matrix \(A\) representing a directed network where the entry \(a_{ij}=1\) indicates a direct route from node \(i\) to node \(j\), and 0 indicates no direct route. \(A = \begin{pmatrix}0 & 1 & 1\\ 1 & 0 & 1\\ 0 & 1 & 0\end{pmatrix}\). Determine the number of distinct routes of […]
Basic Path Counting with Adjacency Matrix Squaring
Let \(A\) be the adjacency matrix of a simple undirected graph with three nodes given by: \(A = \begin{pmatrix}0 & 1 & 1\\1 & 0 & 1\\1 & 1 & 0\end{pmatrix}\). (a) Compute \(A^2\). (b) Explain what the entries of \(A^2\) represent in terms of 2-step paths between nodes.
Matrix Sum in Graph Analysis
Given two directed graphs with adjacency matrices \( A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} \) and \( B = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix} \), compute the matrix sum \( C = A + B \). Explain how the resulting matrix represents the connectivity of the […]