IB Mathematics Applications & Interpretation 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$.

Draw on this

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$: $$\left(\begin{array}{cccc}0& 1& 0& 1\\ 1& 0& 1& 1\\ 0& 1& 0& 0\\ 1& 1& 0& 0\end{array}\right)$$ 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\to B$)
• Task $A$ must be completed before task $C$ ($A\to C$)
• Task $B$ must be completed before task $D$ ($B\to D$)
• Task $C$ must be completed before task $D$ ($C\to D$)

Draw the directed graph that represents these task dependencies.