QUESTION 25

Why is the supplied flight network directed?

2 marks

Answer

Each flight has an origin and destination. A reverse connection exists only when another supplied flight provides it.

Represent the supplied five-city flight network as a directed graph, matrix and lists.

5 marks

Answer in brief

Use vertices 1 New Delhi, 2 Mumbai, 3 Chennai, 4 Bangalore and 5 Kolkata. The ten supplied flights determine ten directed edges.

Edges from the source table

2→3, 3→2, 5→3, 3→4, 2→5, 5→2, 5→1, 1→4, 5→4 and 4→5. Flight numbers distinguish the source rows; the unweighted graph records the stated endpoint relationships.

Adjacency lists

1: [4]
2: [3, 5]
3: [2, 4]
4: [5]
5: [1, 2, 3, 4]

Matrix interpretation

Use rows as origins and columns as destinations in city-index order 1 through 5. A 1 records an outgoing connection; zero means that directed edge was not supplied. The table below is intentionally not made symmetric unless reverse flights actually appear.

Checks

There are ten 1 entries, matching the ten distinct supplied directed edges. Row 5 has four outgoing flights. Column 5 has incoming edges from cities 2 and 4. No self-flight is present, so the diagonal entries are zero.

Representation cost

A matrix stores 25 entries for these five cities. The adjacency lists store five vertex headers plus ten outgoing neighbour entries. General matrix space is O(V²); list space is O(V + E). No distance or fare is provided, so adding weights would invent information not present in the paper.

Reference table

↔ Scroll horizontally on a small screen

Directed flight adjacency matrix
Origin / destination	1	2	3	4	5
1	0	0	0	1	0
2	0	0	1	0	1
3	0	1	0	1	0
4	0	0	0	0	1
5	1	1	1	1	0