İnteraktif Dersler

Networks: parts, routes and weights

Lecture notes

Definition

A network: vertices and edges

A network is a picture made of dots and lines. The dots are the vertices and a line between two vertices is an edge. A network can show a metro map, friends, roads or the corridors of a school. In Parts you type the edges, like A-B, B-C, or choose a situation, and the application counts the vertices and the edges.
Example
The network A-B, A-C, B-C, C-D, D-E has 5 vertices (A, B, C, D and E) and 5 edges.
ABCDE5 vertices, 5 edges
Rule

The degrees add up to twice the number of edges

The degree of a vertex is the number of edges at it. Every edge has two ends, so it is counted twice when you add all the degrees. So the sum of the degrees is always twice the number of edges, and it is always even. Parts shows the degrees and their sum.
Example
The degrees are 2, 2, 3, 2 and 1 → , and edges. A sum of 13 is impossible, because it is odd.
A2B2C3D2E1Degrees: 2, 2, 3, 2, 1
Definition

Parts and cycles

A network is in one part when you can get from every vertex to every other vertex along edges. If not, it has separate parts. A cycle is a way round that comes back to its start without using a vertex twice. Parts says how many parts there are and whether there is a cycle.
Example
A-B, B-C, A-C, D-E and a lone vertex F make 3 parts: A, B, C; then D, E; and F alone. A, B and C form a cycle: A − B − C − A.
ABCDEF3 separate parts
Definition

Routes: a path visits no vertex twice

A route (a path) goes from one vertex to another along edges and visits no vertex twice. To count the routes from A to F, follow every first step from A and never visit a vertex twice. In Routes you choose From and To, see how many routes there are and step through them with Route; the list shows the routes with the fewest edges first.
Example
In the network A-B, A-C, B-C, C-D, D-E, E-F, D-F there are 4 routes from A to F: 2 start with A − B and 2 start with A − C. The shortest is A − C − D − F with 3 edges; the longest is A − B − C − D − E − F with 5 edges.
ABCDEFA − C − D − F: 3 edges
Definition

A weighted network and the total weight

In a weighted network every edge has a weight: a distance, a time or a cost. You type it after a colon: A-B:4. The total weight of a route is the sum of the weights of its edges. In Weights the weights are drawn in small boxes on the edges.
Example
In the metro network A-B:4, B-C:3, C-D:5, B-E:6, E-F:2, D-F:4, C-E:7 the route A − B − C − D − F has the total . The route A − B − C − E − F has as well.
4356247ABCDEFA − B − C − D − F: 4 + 3 + 5 + 4 = 16
Rule

The least total, step by step

You do not have to list every route to find the least total. Start at the first vertex with the total 0. The vertex with the smallest total that is not final yet becomes final. Update the totals of its neighbours: a smaller total replaces a bigger one. Repeat. In Weights the table with Best total and State (final or open) shows this step by step.
Example
From A in the metro network: A 0; B 4; C 7 ; E 10 (, better than by way of C); D 12 ; F 12 . The least total from A to F is 12, on A − B − E − F.
4356247ABCDEFA − B − E − F: 4 + 6 + 2 = 12
Watch out!

The fewest edges is not always the cheapest

The route with the fewest edges can have a bigger total than a longer route. Do not stop at the shortest looking route: add the weights of the routes and compare. Weights shows the total of the route with the fewest edges and says how much more it costs than the least total.
Example
In A-B:2, B-C:2, A-C:7, C-D:1, from A to D: A − C − D has 2 edges and the total . A − B − C − D has 3 edges and the total , which is 3 less.
2271ABCDA − B − C − D: 2 + 2 + 1 = 5
Tip

Typing a network and the keys

Type the edges with commas between them, like A-B, B-C. A letter alone is a vertex with no edge. Use the letters A to H, with at most 12 edges. A weight comes after a colon, like A-B:4, and every edge needs one or none does. There are 4 ready-made situations. Nothing you type is stored or sent anywhere. Every stepper, choice and button works by keyboard.
Example
A-B:4, B-C:3, C-D is not allowed, because C-D has no weight. A-B:4, B-C:3, C-D:5 is allowed.

Exercises

In the network A-B, A-C, B-C, C-D, D-E, what is the degree of vertex C? Easy
ABCDEThe network of the question
Show solution
The degree is the number of edges at C. Count the edges that end in C: A-C, B-C and C-D.
That is 3 edges.
3
Count every edge of the vertex once. An edge A-B counts for A and for B.
A network has 6 vertices with the degrees 3, 3, 2, 2, 2 and 2. How many edges does it have? Easy
Show solution
Add the degrees → .
Every edge has two ends, so it is counted twice → edges.
7 edges
Do not answer 14: that is the sum of the degrees, which counts every edge twice.
Which of these is a route in the network A-B, A-C, B-C, C-D, D-E: A − C − D − E, A − B − D − E or A − C − B − C? Easy
Show solution
Check every step: is there an edge between the two letters, and does a letter come twice?
A − B − D − E: B-D is not an edge. A − C − B − C: C comes twice. A − C − D − E: A-C, C-D and D-E are edges and no vertex comes twice.
A − C − D − E
A route uses only edges of the network and never visits a vertex twice.
How many routes are there from A to F in the network A-B, A-C, B-C, C-D, D-E, E-F, D-F? Medium
ABCDEFFrom A to F
Show solution
Follow the first step from A. Via B: A − B − C and then on to D. Via C: A − C and then on to D. Never visit a vertex twice.
From D you reach F directly (D-F) or by way of E (D − E − F). Via B there are 2 routes and via C there are 2 routes: A − C − D − F, A − B − C − D − F, A − C − D − E − F and A − B − C − D − E − F.
routes.
4 routes
Sort the search by the first step: that way you cannot forget a route or count one twice.
In the metro network A-B:4, B-C:3, C-D:5, B-E:6, E-F:2, D-F:4, C-E:7, what is the total weight of the route A − B − C − E − F? Medium
4356247ABCDEFThe metro: weights in minutes
Show solution
Read the weight of every edge of the route: A-B is 4, B-C is 3, C-E is 7 and E-F is 2.
Add them → .
16
A route with a different last step can have the same total: A − B − C − D − F is also 16.
In the same metro network, what is the least total weight of a route from A to F, and which route is it? Medium
4356247ABCDEFA − B − E − F: 4 + 6 + 2 = 12
Show solution
Start at A with 0. B gets 4. C gets . E gets , better than by way of C.
D gets . F gets by way of E; by way of D it would be .
The least total is 12, on A − B − E − F → .
12, on A − B − E − F
The route with the fewest edges here (3 edges) is also the cheapest, but that is luck, not a rule.
In the network A-B:2, B-C:2, A-C:7, C-D:1, how much more does the route with the fewest edges from A to D cost than the route with the least total weight? Hard
2271ABCDFrom A to D
Show solution
Fewest edges: A − C − D with 2 edges. Its total is .
The other route is A − B − C − D with 3 edges and the total .
The difference is .
3
Only two routes exist here, so you can compare them directly. With more routes, work step by step from A.
A network has 6 vertices and every vertex has degree 3. How many edges does it have? Can a network have 5 vertices that all have degree 3? Hard
Show solution
The degrees add up to . That is twice the number of edges, so there are edges.
With 5 vertices the sum would be . The sum of the degrees must be twice the number of edges, so it must be even, and 15 is odd.
9 edges; no, it is impossible
An odd sum of degrees never happens: the number of vertices with an odd degree is always even.
In the school corridors A-B:20, B-C:35, A-D:30, B-D:15, D-E:25, C-E:10, find the least total from B to E and the route that has the second least total. Hard
203530152510ABCDEB − D − E: 15 + 25 = 40
Show solution
List the routes from B to E: B − D − E, B − C − E and B − A − D − E.
Their totals → , and .
The least total is 40, on B − D − E; the second is 45, on B − C − E
Check that you have found every route: starting with B-A, B-C or B-D covers all of them here.

Interactive applications for this topic

Free applications open with a free student account. Teachers can use all applications in a live lesson.

About the free account and Plus

Are you a teacher?

Start live lessons with these applications for your whole class. Free to try for one month.

Try it free

Fits these school years

IB (MYP, Diploma): MYP 4, MYP 5, Diploma, year 1, Diploma, year 2

Cambridge International: AS Level, A Level

England (GCSE, A Level): Year 12 (A Level), Year 13 (A Level)

What the applications of this topic teach 1 application

Networks: parts, routes and weights

  • Typing a network and reading its vertices, edges and degrees
  • Counting routes between two vertices and finding the shortest in edges
  • Finding the route of least total weight