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

Loading subject…

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

Question 1

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 Ω Between A and Y : 5 Ω Between Y and B : 10 Ω Between B and X : 10 Ω Additionally, a diagonal resistor connects nodes A and B with a resistance of 20 Ω . Draw on this Determine the effective resistance between terminals X and Y .

[5]

Question 2

Construct the adjacency matrix and list all edges for a complete graph K_{5} .

Construct the adjacency matrix and list all edges for the complete graph K_{5} on vertices 1 through 5.

[5]

Question 3

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.

[5]

Question 4

Six cities, A, B, C, D, E, and F, are connected by roads with the following distances: A B = 7 A C = 9 A F = 14 B C = 10 B D = 15 C D = 11 C F = 2 D E = 6 E F = 9

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

[3]

Question 5

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.

[3]

Question 6

Construct a weighted adjacency matrix for a given undirected graph where vertices represent friends and edge weights represent friendship strengths.

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.

[3]

Question 7

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.

[7]

Question 8

A network has four processors P_{1} - P_{4} connected by bidirectional links with latencies: P_{1} - P_{2} : 1 ms P_{1} - P_{3} : 4 ms P_{2} - P_{3} : 2 ms P_{2} - P_{4} : 5 ms P_{3} - P_{4} : 1 ms Draw the weighted graph and determine if there is any cycle of total latency \leq 6 ms .

[6]

Question 9

Adjacency matrices and vertex degrees in undirected graphs.

Given the adjacency matrix of an undirected graph on vertices 1, 2, 3, 4 : 0101101101001100 Find the degree of each vertex.

[2]

Question 10

Specification

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

[4]

Question 11

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.

[3]

IB Mathematics Applications & Interpretation Question Type 2: Creating Simple Graphs Given Information of Structures Exercises