krit.club logo

Algebra - Weighted networks-extended

Grade 10IB

Review the key concepts, formulae, and examples before starting your quiz.

🔑Concepts

•

A weighted network is a graph where each edge is assigned a numerical value called a weight. These weights can represent distances, costs, time, or capacities.

•

A path in a weighted network is a sequence of edges connecting two vertices. The weight of the path is the sum of the weights of the edges in that path: W=∑wiW = \sum w_i.

•

An adjacency matrix for a weighted network uses the weights of the edges as entries. If no edge exists between two vertices ii and jj, the entry aija_{ij} is typically represented as 00 or ∞\infty depending on the context (e.g., 00 for flow, ∞\infty for distance).

•

The Shortest Path Problem involves finding a path between two vertices such that the sum of the weights of its constituent edges is minimized.

•

A Minimum Spanning Tree (MST) is a subgraph that connects all vertices together, without any cycles, and with the minimum possible total edge weight. Common algorithms to find this include Kruskal's and Prim's algorithms.

•

The degree of a vertex in a weighted graph is still the number of edges incident to it, but the strength of a vertex is the sum of the weights of all edges connected to it: s(i)=∑jwijs(i) = \sum_{j} w_{ij}.

📐Formulae

W(P)=w(e1)+w(e2)+⋯+w(ek)W(P) = w(e_1) + w(e_2) + \dots + w(e_k) tokens of a path PP

A=(w1,1w1,2⋯w1,nw2,1w2,2⋯w2,n⋮⋮⋱⋮wn,1wn,2⋯wn,n)A = \begin{pmatrix} w_{1,1} & w_{1,2} & \cdots & w_{1,n} \\ w_{2,1} & w_{2,2} & \cdots & w_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ w_{n,1} & w_{n,2} & \cdots & w_{n,n} \end{pmatrix}

si=∑j=1nwijs_i = \sum_{j=1}^{n} w_{ij}

💡Examples

Problem 1:

Given a network with vertices A,B,A, B, and CC. The weights are: AB=5AB = 5, BC=8BC = 8, and AC=10AC = 10. Find the shortest path from AA to CC and calculate its total weight.

Solution:

There are two possible paths from AA to CC:

  1. Direct path: A→CA \rightarrow C with weight 1010.
  2. Indirect path: A→B→CA \rightarrow B \rightarrow C with weight 5+8=135 + 8 = 13.

Since 10<1310 < 13, the shortest path is the direct edge ACAC with a total weight of 1010.

Explanation:

To find the shortest path, we compare the sum of weights of all possible routes between the starting and ending vertices.

Problem 2:

Construct the adjacency matrix for a weighted graph with 3 vertices (V1,V2,V3V_1, V_2, V_3) where the weights are: w(V1,V2)=4w(V_1, V_2) = 4, w(V2,V3)=7w(V_2, V_3) = 7, and w(V1,V3)=2w(V_1, V_3) = 2. Assume the graph is undirected and no self-loops exist.

Solution:

M=(042407270)M = \begin{pmatrix} 0 & 4 & 2 \\ 4 & 0 & 7 \\ 2 & 7 & 0 \end{pmatrix}

Explanation:

In an undirected weighted adjacency matrix, the entry in row ii and column jj is the weight of the edge between ViV_i and VjV_j. Since there are no self-loops, the diagonal elements are 00.

Problem 3:

Calculate the total weight of a cycle in a network where the edges are E1(A,B)=12E_1(A,B) = 12, E2(B,C)=15E_2(B,C) = 15, and E3(C,A)=9E_3(C,A) = 9.

Solution:

Total Weight=12+15+9=36\text{Total Weight} = 12 + 15 + 9 = 36

Explanation:

The total weight of a cycle is the sum of the weights of all edges forming the closed loop.