LECTURE
Methods in Transportation Systems:
An Introduction to Graph Theory
Dr. Irfan Ahmad Rana
Assistant Professor
Department of Urban and Regional Planning
Taxonomy of Transport Geography
Methods
Transport Related Multidisciplinary
Geography Related • Network Analysis (Graph Theory). • Cartography / Geographic
• Land Use / Transportation Information Systems.
Interactions. • Descriptive Statistics, (e.g., Gini
• Flow/Location Allocation Models. Coefficient).
• The Four-Stage Urban Transportation • Questionnaires / Interviews.
Multidisciplinary
Model. • Big data.
• Travel / Traffic Surveys. • Graphs and Charts.
• Inferential Statistics.
• Impact Assessment.
• Risk Assessment.
• Policy Analysis.
Section a
Graph Theory:
Terminologies, Concepts and Properties
Graph theory
• Graph theory is a branch of mathematics concerned
with how networks can be encoded and their
properties measured.
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Graph Representation of a Real Network
Real Network Graph Representation
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Graph theory
• Graph theory is a branch of mathematics concerned with how networks
can be encoded, and their properties measured.
• Invented by Leonard Euler in 1735
• Basis of Discrete Mathematics (A branch of mathematics)
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Basics: Graphs and Links
• Graph. A graph G is a set of vertexes (nodes) v connected by edges (links)
e. Thus G = (v , e)
• Sub-graph. A subset of a graph G where p is the number of sub-graphs.
For instance G´ = (v´, e´ ) can be a distinct sub-graph of G. Unless the global transport
system is considered as a whole, every transport network is in theory a sub-graph of
another.
For instance, the road transportation network of a city is a sub-graph of a regional
transportation network, which is itself a sub-graph of a national transportation
network.
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Basics: Graphs and Links
• Edge (Link). An edge e is a link between two nodes.
The link (i , j) is between initial extremity i and terminal
extremity j.
A link is the abstraction of a transport infrastructure
supporting movements between nodes. It has a direction that
is commonly represented as an arrow. When an arrow is not
used, it is assumed the link is bi-directional.
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Basic Graph Representation of a Transport
Network
1 2
Edge (Link)
3 4
Vertex (Node)
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Length of a Link, Connection or Path
4 km
2 3
2 km 2 km
1 6 km 6
3 km
5 km 2 km
4 5
7 km
Two Common Fallacies in Transport
Geography
Access vs. Accessibility Distance vs. Time
55
50
50 30
b 25 55
35 30
35 30
40 30 40
65 35 40 45
65
c
60 65 60
a
Absolute and Relative Distance in a
Network
Absolute Distance Relative Distance
10 km 30 minutes
Topology and Network Connectivity
A
Fully Connected Network
Average Path Length
B C
D
Minimum Network
Geographic Barrier
Network Length
Network Strategies to Service a Set of
Locations
A B C
D E F
Planar and Non-Planar Graphs
A B
Planar Non-Planar
Types of Transportation Networks
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Simple and Multigraphs
Road
Road & Rail
Rail
Simple Graphs Multigraph
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Network Patterns
Mesh Hub-and-Spoke
Linear Tree
Network Patterns
Centralized Decentralized Distributed
Cost Structure of Networks
Point-to-Point Total Costs Hub-and-Spoke Total Costs
3,000
550 550
3,000
525 52
5
3,000 1,550
3,000 525 52
5
550 550
3,000
Total: 15,000 Total: 5,850
What we learned
• Graph G
• Sub-graph P
• Edges (Link) e
• Nodes (Vertices) v
• Planar and Non-Planar
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Order of a Node
2
2 1
4 3
A B
Order (o)
2 1 2 3
Perfect spoke
1 1 3
C 5 Perfect hub D 2 2 2
1 1
1 3
Diameter of a Graph
2 4 6 Shimbel Distance
v 1 2 3 4 5 6 7
1 0 1 1 2 2 1 3
2 1 0 2 1 3 2 4
3 1 2 0 3 1 2 2
1 3 5 4 2 1 3 0 2 1 3
5 2 3 1 2 0 1 1
Diameter = 4 7 6 1 2 2 1 1 0 2
7 3 4 2 3 1 2 0
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Diameter of a Graph
2 4 2 4
A B
d=? d=?
1 3 1 3 5
2 4 6 2 4 6
C D
d=? d=?
1 3 5 1 3 5
Cyclomatic Number
u = e−v+ p
A B
e v p u
A 3 5 2 0
B 5 5 1 1
C 5 4 1 2
D 7 6 1 2
C D
The maximum number of independent cycles
in a graph.
A B C D
Indices (At Network Level)
• Detour Index • Theta Index (θ)
• Network Density • Iota Index (ι)
• Pi Index (π) • Eta Index (η)
• Alpha Index (α) • Gamma Index (γ)
• Beta Index (β)
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Detour index
Ratio of displacement to actual distance
Where D(S) is the straight distance, D(T); real distance,
Detour index
relative efficiency
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Effect of Topography on Route Selection
c
b
2 a 3
Low elevation Medium elevation High elevation
Detour index
Ratio of displacement to actual distance
Where D(S) is the straight distance, D(T); real distance,
Direct Distance Transport
Route
(1-2-3) Distance
a 20 km 20 km
b 20 km 25 km
c 20 km 30 km
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Effect of Topography on Route Selection
• Route (a) is shortest in terms of distance, but not necessarily the least expensive in terms of
construction and operating costs.
• Route (b) represents an attempt to reduce costs and this at the expense of a direct path.
• Route (c) will be the one used to link locations 1 and 3. It offers a compromise between the lost
distance (a higher detour) and the supplementary construction costs imposed by higher elevations.
Direct Distance Transport
Route Detour Index
(1-2-3) Distance
a 20 km 20 km 1.0
b 20 km 25 km 0.8
c 20 km 30 km 0.666
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Network density
Measures the territorial occupation of a transport network in terms of km of
links (L) per square kilometers of surface (S).
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Eta Index
L (G )
A =
e
Average length per link
B
Eta Index
L (G )
A =
e
L(G) e Eta
A 80 km 5 16.0
B 80 km 7 11.4
B
Average length per link
Theta Index
A Q (G )
=
v
Measures the function of a node,
which is the average amount of traffic
per intersection.
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Theta Index
A Q (G )
=
v
Q(G) v Theta
A 3,500 t 6 583.3
B 3,500 t 8 437.5
B
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
Iota Index
1
A B 1
Order (o)
3 1 4 1 L(G )
=
W (G )
W (G ) = 1, o = 1
1 4 1 W (G ) = 2 * o, o 1
e
3 3
1
1 1 1 1
Iota Index
1 L(G )
A B 1 =
W (G )
Order (o) W (G ) = 1, o = 1
W (G ) = 2 * o, o 1
3 1 4 1 e
L(G) W(G) Iota
1 4 1
A 80 23 3.47
3 3
B 80 22 3.63
1
1 1 1 1
W(A) = 1+6+6+6+1+1+1+1
W(B) = 1+1+8+1+1+8+1+1
Beta Index
e
A B
=
v
e v Bet
a
A 2 4 0.5
B 3 4 0.75
C D C 4 4 1.0
D 5 4 1.25
Measures the level of connectivity in a graph and is expressed by the relationship
between the number of links (e) over the number of nodes (v).
Beta Index
e
A B
=
v
e v Beta
A 2 4 0.5
B 3 4 0.75
C 4 4 1.0
C D
D 5 4 1.25
u
Alpha Index =
2v − 5 (for planar graphs)
A B (f
(for non-planar graphs)
u= 2v-5 Alpha
(e-v+p)
A 0 3 0.0
B 1 3 0.33
C D C 2 3 0.66
D 3 3 1.0
A measure of connectivity which evaluates the number of cycles in comparison with
the maximum number of cycles.
References
• Rodrigue, J. P. (2020). The geography of
transport systems. Routledge.
• https://transportgeography.org/
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad]
URP-805 Urban and Regional Transportation Systems, Spring Semester 2023
[Dr. Irfan Ahmad Rana, Department of Urban and Regional Planning, NUST, Islamabad] 45
