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

A set of tasks A→B, A→C, B→D, C→D must be completed in this order. Draw the directed graph showing these task dependencies.

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

Given five friends A, B, C, D and E, with friendship strengths: A–B: 3, A–C: 2, B–C: 4, C–D: 1 and D–E: 5. Construct the weighted adjacency matrix for this friendship graph.

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

Find the degree of each vertex.

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.

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

A network has four processors P1–P4 connected by bidirectional links with latencies: P1–P2:1 ms, P1–P3:4 ms, P2–P3:2 ms, P2–P4:5 ms, P3–P4:1 ms. Draw the weighted graph and determine if there is any cycle of total latency ≤6 ms.

Given six cities A–F with road 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 a minimum spanning tree (MST) using Kruskal’s algorithm and list its edges.

Given a weighted graph with vertices {1,2,3,4,5} and edges: (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 path from 1 to 5.

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

For the circuit graph with nodes X and Y connected by four resistors in a square: X–A: 5 Ω, A–Y: 5 Ω, Y–B: 10 Ω, B–X: 10 Ω, and a diagonal A–B: 20 Ω. Compute the effective resistance between X and Y.