Question Type 2: Creating simple graphs given information of structures Exercises

In the electrical circuit shown below, the nodes $X$ and $Y$ are connected by four resistors forming a loop. The resistance values are:

• Between $X$ and $A$: $5\,\Omega$
• Between $A$ and $Y$: $5\,\Omega$
• Between $Y$ and $B$: $10\,\Omega$
• Between $B$ and $X$: $10\,\Omega$

Additionally, a diagonal resistor connects nodes $A$ and $B$ with a resistance of $20\,\Omega$.

Determine the effective resistance between terminals $X$ and $Y$.

Construct the adjacency matrix and list all edges for the complete graph $K_5$ on vertices 1 through 5.

A degree sequence is given as $(3, 3, 2, 2, 2)$. Determine whether a simple graph with this sequence exists. If such a graph exists, construct one example.

Find the minimum spanning tree (MST) using Kruskal’s algorithm and list the edges included in the MST.

The following adjacency list describes a graph with vertices $V, W, X, Y, Z$:

$V$: $W, Y$ $W$: $V, X, Z$ $X$: $W, Y$ $Y$: $V, X, Z$ $Z$: $W, Y$

Convert this list into its adjacency matrix.

Given five friends A, B, C, D, and E, with friendship strengths as follows:

• A–B: 3
• A–C: 2
• B–C: 4
• C–D: 1
• D–E: 5

Construct the weighted adjacency matrix for this friendship graph.

A weighted graph has vertices $\{1, 2, 3, 4, 5\}$ and edges given by the following triples $(u, v, w)$, where $w$ is the weight of the edge between vertices $u$ and $v$: $(1, 2, 3), (1, 3, 1), (2, 3, 7), (2, 4, 5), (3, 5, 2), (4, 5, 4)$ Use Dijkstra’s algorithm to find the shortest distance and the shortest path from vertex 1 to vertex 5. Show your working clearly.

A network has four processors $P_1$–$P_4$ connected by bidirectional links with latencies:

• $P_1$–$P_2$: $1 \text{ ms}$
• $P_1$–$P_3$: $4 \text{ ms}$
• $P_2$–$P_3$: $2 \text{ ms}$
• $P_2$–$P_4$: $5 \text{ ms}$
• $P_3$–$P_4$: $1 \text{ ms}$

Draw the weighted graph and determine if there is any cycle of total latency $\le 6 \text{ ms}$.

Given the adjacency matrix of an undirected graph on vertices $1, 2, 3, 4$:

Find the degree of each vertex.

A circuit has nodes $P$, $Q$, $R$ and resistors of $2\,\Omega$ between $P$ and $Q$, $4\,\Omega$ between $Q$ and $R$, and $6\,\Omega$ directly between $P$ and $R$. Represent this as a weighted graph and list its edge set with weights.

Four tasks $A, B, C$, and $D$ must be completed subject to the following dependencies:

• Task $A$ must be completed before task $B$ ($A \rightarrow B$)
• Task $A$ must be completed before task $C$ ($A \rightarrow C$)
• Task $B$ must be completed before task $D$ ($B \rightarrow D$)
• Task $C$ must be completed before task $D$ ($C \rightarrow D$)

Draw the directed graph that represents these task dependencies.