MAT5164 MSc inApplied Mathematics
CHAPTER 2
Trees and
Distance
By:[Link] Munde
anjalim@[Link]
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Lecture Outline
1. Basic Graph Properties andConnectivity
2. Graph Traversal andSpecific Graph Types
3. Treesand SpanningTrees
4. Fundamental Graph Algorithms
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
2.1 Basic GraphProperties and
Connectivity
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Weighted Graphs
Graphs whereeach edge hasa numerical "weight" or "cost.”
𝐺 = 𝑉, 𝐸, 𝑤 where theset of vertices 𝑉, the set of edges𝐸, anda weight
function 𝑤: 𝐸 → ℝ.
Weights are typica ly non-negative integers.
Can be directed or undirected.
Allow for quantitativemodeling of real-world relationships.
Weights represent distance/length, time, cost, capacity etc.
Crucial for optimization problems (e.g.,finding shortest paths, minimum
cost networks).
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Weighted Graphs
A weighted graph(or network) can be representedusing a distance
matrix.
This matrix records the weights of edges between vertices.
Each row/columnrepresentsa vertex. The value at ce l (i, j) is the weight
of the edgefrom vertex 'i' to vertex 'j’.
If there's no direct edge between two vertices,we typica ly write '∞'
(infinity) or a large placeholder like '-' to indicate no direct connection.
This representation is fundamental for finding the shortest path between
vertices using various algorithms.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Weighted Graphs
Applications & examples.
Navigation (GPS):Find shortest/fastestroute.
Network Design (Cables/Pipes): Find most cost-effective way to
connect all points.
Social Networks: Identify influential users,recommend connections.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example Weighted Graphs
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Connected Graphs
A graphis connected if there's a path between everypair of distinct
vertices.
Every vertex can be reached from anyother vertex.
Path:A sequence of unique vertices linked by edges.
If you can travel fromany point to anyother point in the graph,it's
connected.
Inan undirected graph,if 'A' can reach'B', then 'B' can also reach 'A’.
For connectivity, all vertices must be mutualy reachable.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Connected Graphs
Connectivity is a graphproperty, we saythe graph is connected, not
individual vertices.
What if it's NOT Connected?
It splits into "ConnectedComponents.”
Each component is a maximalconnected subgraph:
All vertices within a component are reachable from each other.
No connections exist to other components in the graph.
Think of it as:Distinct, isolated "islands" of connection within a larger
graph.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Connected Graphs
Key facts about components:
Every vertex belongs to one component.
Connected Graph:Has one component (the graph itself).
Disconnected Graph:Has two or morecomponents.
Example: Social Network
Vertices =People, Edges =Friendships
Connected: Everyoneis linked (directly or indirectly).
Disconnected: Separate "friend groups" with no commonfriends between
[Link] groupis acomponent.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Walk
A walk is an alternating sequence of vertices andedges.
Starts andendswith a vertex.
Each edge connects the vertices before andafter it.
Vertices andedges CAN be repeated.
Length is the number of edgesin the sequence.
Example:
IngraphA-B-C-D (with edges(A,B),(B,C),(C,D),(D,B)).
A → B→ C→ D → B→ C
Here, vertex 'B' andedge'(B,C)' are repeated.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Trail
A trail is a walk whereNO edgeis repeated.
Vertices CAN be repeated.
An Eulerian Path/Circuitis a trail that visits everyedgein the graphexactly once.
Example:
IngraphA-B-C-D (edges (A,B),(B,C),(C,D),(D,B)).
A → B→ D→ C→ B
Vertex 'B' is revisited, but no edgeis repeated.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Path
A path is a walk whereNO vertex is repeated.
Since no vertex is repeated, no edgecan be repeated either.
So,everypath is also a trail anda walk.
Each vertex is visited at most once.
A Hamiltonian Path visits everyvertex in the graphexactly once.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Cycle
Cycle is a closed trail: Starts andends at the samevertex.
No repeated edges.
Only the start/end vertex is repeated (no other vertices repeated internally).
Must havea length of at least 3 in a simple graph.
A Hamiltonian Cycle visits every vertex in the graph exactly once before
returning to the start.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Summary Walk, Trail, Path, Cycle
Property Walk Trail Path Cycle
Edges Repeated? Yes No No No
Vertices Repeated? Yes Yes No Only Start/End
Starts/Ends Same? Can be Can be No (usually) Yes
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise
Find anywalk, trail, path andcycle in the graphsbelow.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
GraphMetric
Distance
Diameter
Girth
Circumference
Cliques
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Distance
Distance 𝑑(𝑢, 𝑣) is the "closeness" between two vertices 𝑢 and𝑣 .
Always defined by the shortest path connecting them.
UnweightedGraphs: Minimum number of edges in anypath.
Weighted Graphs: Minimum sumof edge weights in anypath.
We always find the shortest path (fewest edges or lowest total weight)
to determine distance.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Diameter
Diameter is the longest shortest path between any two vertices in a
graph.
Represents the maximum "distance" one might need to travel within the
graph.
How to find it:
Calculate the shortest path distance for everypair of vertices.
The largest of these shortest path distances is the diameter.
Diameter 𝐺 = max 𝑑(𝑢, 𝑣).
𝑢,𝑣∈𝑉(𝐺)
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Girth
Girth is the length of the shortest cycle in a graph.
Tels us about the "tightest" closed loops.
For unweighted graphs:It's the minimum number of edgesto form a
circuit.
For weighted graphs:It's the minimum total weight of edgesto form a
circuit.
It'sthe minimum numberof edgesto form a circuit.
How to find it:
Identify all cycles in the graph.
The cycle with the fewest edgesdefines the girth.
If no cycles exist (atree),girth is ∞.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Circumference
Circumference is the length of the longest cycle in a graph.
Te ls us about the "longest" closed loop possible.
For unweighted graphs:It's the maximumnumber of edges to form a
circuit.
For weighted graphs:It's the maximumtotal weight of edgesto form a
circuit
How to find it:
Identify all cycles in the graph.
The cycle with the most edgesdefines the circumference.
If no cycles exist (atree), circumference is usualy 0.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise
Find distance, diameter, girth and circumference for the graphsbelow.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Diameter:60
Circumference:70
Girth:45
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Diameter:30
Circumference:247
Girth:6
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
2.2 GraphTraversaland
Specific GraphTypes
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Traversability
Ability to navigate an entire graph,visiting all edges or a l vertices under
specific rules.
Types:
Eulerian: Covers all edges.
Hamiltonian: Covers all vertices.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Eulerian Graph
Traversing every edge.
Can we travel along everyedgeexactly once?
Eulerian Trail: Visits all edges exactly once, starts/ends at different
vertices.
Eulerian Circuit: Visits all edges exactly once, starts/ends at the same
vertex.
Eulerian Graph:Contains an Eulerian Circuit.
Semi-Eulerian Graph:Contains an Eulerian Trail but no Circuit.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Eulerian Graph
A graphwith an Eulerian circuit (visits everyedgeexactly once).
Circuit: Connected graphwhereeveryvertex hasan evendegree.
Trail (Semi-Eulerian): Connected graph with exactly two odd-degree
vertices.
Circuit: Strongly connected digraph where in-degree equals out-degree
for everyvertex.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example Eulerian Graph
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Hamiltonian Graph
Visiting everyvertex.
Can we visit everyvertex exactly once?
Hamiltonian Path: A path that visits all vertices exactly once.(Starts and
ends at different vertices.)
Hamiltonian Circuit (Cycle): A path that visits all vertices exactly once
andreturns to the starting vertex.
Hamiltonian Types:
Hamiltonian Graph: A graph that contains a Hamiltonian Circuit.
You can do a full "round trip" through everystop.
Semi-Hamiltonian Graph: A graph that has a Hamiltonian Path but
NO Hamiltonian Circuit.
You can visit everystop,but can't return to whereyou started.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Hamiltonian Graph
Ore's Theorem:
For a simple graph𝐺 with 𝑛 ≥ 3 vertices.
If deg 𝑣 + deg(𝑤) ≥ 𝑛 for every pair of non-adjacent vertices
𝑣, and 𝑤.
Then 𝐺 is Hamiltonian.
This is a sufficient condition. If a graph meets it, it's Hamiltonian. If not,
it might still be Hamiltonian (the theorem just can't prove it).
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Hamiltonian Graph
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example Hamiltonian Graph
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise
Describe the network below as traversable Eulerian/semi-Eulerian,
a Hamiltonian/semi-Hamiltonian network, both, or neither.
Neither Hamiltonian Eulerian Eulerian Eulerian Neither
Hamiltonian
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Chinese Postman Problem
Find the shortest route that traverses every edge at least once and
returns to the starting point.
Studied by Chinese mathematicianMei Ko Kwan (1960).
The ”easy"case: Already Eulerian.
Solution: The Eulerian Circuit is the shortest route.
Total cost =sumof all edge weights.
The ”hard" case:Odd-degree vertices.
If a graph has vertices with an odd number of edges, you can't
traverse everyedge exactly once andreturn to the start.
Solution strategy: We need to strategicaly duplicate some edges to
make the graphEulerian.
This makesall vertex degrees even.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Chinese Postman Problem
Duplication strategy:Making it Eulerian
Identify odd-degree vertices: always an evennumber of them.
Pair them up: we need to add "duplicate" paths between these odd-
degree vertices to make their degrees even.
Find shortest paths:for each pair,calculate the shortest path.
Minimum Matching: select a set of these shortest paths to
"duplicate" such that:
• Everyodd-degree vertex is covered.
• The total weight of duplicated edgesis minimized.
New Eulerian graph: add these chosen shortest paths back to the
original [Link], all degrees are even.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Chinese Postman Problem
Total route length:
Sumof weights of all original edges
PLUS
Sumof weights of all duplicated (re-traversed) edges.
Result: The shortest tour that covers everyedge at least once.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Chinese Postman Problem
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise
List the waysof pairingthe oddvertices in the fo lowing networks. For eachpairing find
the minimum connector. Find the length of anoptimal Chinesepostman [Link]
downone possibleroute
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise
List the ways of pairing the odd vertices in the
following networks. For each pairing find the minimum
[Link] the length of an optimal Chinese
postman route. Write down one possible route
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
2.3 TreesandSpanningTrees
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Trees
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Properties of Trees
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
SpanningTrees
Spanning tree of a connected graph 𝐺 is a subgraph which includes all
the vertices of 𝐺.
Everyconnected graphhasat least one spanning tree.
If𝐺 has𝑛 vertices,anyspanning tree of 𝐺 will have𝑛 − 1 edges.
Spanning trees help to understand the basic connectivity structure of a
graph without redundant cycles.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Counting Trees
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Counting Trees
Matrix Tree Theorem, a method to calculate the number of spanning trees for a
given graph.
The matrix shown is an example of a LaplacianMatrix (𝐿) for a graph.
Construction of a Laplacian Matrix (𝐿):
• Diagonal elements (𝐿𝑖𝑖): Represent the degree of vertex 𝑣𝑖.
• Off-diagonal elements (𝐿𝑖𝑗 where 𝑖 ≠ 𝑗):
• 𝐿𝑖𝑗 = −1 if there is an edge between 𝑣𝑖 and 𝑣𝑗.
• 𝐿𝑖𝑗 = 0 if there is no edge between 𝑣𝑖 and 𝑣𝑗.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Counting Trees
The theorem states that the number of spanning trees of a graph is
equal to the determinant of anycofactor of its Laplacian matrix.
A cofactor 𝐶𝑖𝑗 is calculated as −1 𝑖+𝑗 times the determinant of the
minor 𝑀𝑖𝑗 (the submatrixobtained by deleting row 𝑖 andcolumn 𝑗).
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Counting Trees
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Exercise Counting Trees
Determinant is 70
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Minimum Spanning Tree (MST)
In a weighted, connected graph, a Minimum Spanning Tree (MST) is a
spanning tree where the sum of the weights of its edges is as sma l as
possible.
An MST may not be unique if there are multiple edges with the same
weight.
MSTs are crucial for finding the cheapest way to connect all vertices in a
network.
Prim’s algorithm and Kruskal’s algorithm.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
2.4 FundamentalGraph
Algorithms
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Shortest Path Algorithms
Dijkstra's Algorithm:
Purpose: For finding the shortest paths from a single source vertex to all
other verticesin a graph with non-negativeedge weights.
Key Concept: Uses a greedy approach, iteratively expanding the set of
visited nodes with the shortest knowndistance.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Minimum Spanning Tree Algorithms
Prim's Algorithm:
Purpose: To find a minimum spanning tree for a connected,weighted undirected
graph.
Key Concept: Builds the MST by starting from an arbitrary vertex anditeratively
adding the cheapestedgethat connectsa vertex in the growing tree to a vertexnot yet
in the tree.
Kruskal's Algorithm:
Purpose: To find a minimum spanning tree for a connected, weighted undirected
graph.
Key Concept: Builds the MST by iteratively adding the cheapest available edge that
connectstwo previously unconnected components, as long as it doesnot form a cycle.
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Dijkstra’s Algorithm
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Prim’s Algorithm
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Prim’s Algorithm to a Distance Matrix
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Kruskal’s Algorithm
School of Mathematical Sciences
MAT5164 MSc inApplied Mathematics
Example
School of Mathematical Sciences