CO2412: Computational Thinking
Lecture 10
Introduction to Graph Theory
1. What is a Graph?
o A Graph is a collection of nodes, called vertices, and edges that
connect pairs of vertices.
o Vertices: The points or nodes of the graph.
o Edges: The connections between vertices.
2. Applications of Graph Theory
o Graph theory has a wide range of applications including social
networks, computer networks, logistics, and scheduling problems.
Types of Graphs
1. Undirected vs. Directed Graphs
o Undirected Graph: A graph where the edges have no direction.
The edge (u, v) is identical to (v, u).
o Directed Graph (Digraph): A graph where each edge has a
direction, going from one vertex to another. The edge (u, v) is
different from (v, u).
2. Weighted vs. Unweighted Graphs
o Weighted Graph: A graph where each edge has an associated
weight or cost.
o Unweighted Graph: A graph where all edges are treated equally,
with no weights assigned.
3. Simple Graph vs. Multigraph
o Simple Graph: A graph with no loops (edges connected at both
ends to the same vertex) and no more than one edge between any
pair of vertices.
o Multigraph: A graph that may have multiple edges between the
same set of vertices.
4. Connected vs. Disconnected Graphs
o Connected Graph: A graph in which there is a path between every
pair of vertices.
o Disconnected Graph: A graph where some vertices are not
connected by paths.
Lecture 10
Introduction to Graph Theory
1. What is a Graph?
o A Graph is a collection of nodes, called vertices, and edges that
connect pairs of vertices.
o Vertices: The points or nodes of the graph.
o Edges: The connections between vertices.
2. Applications of Graph Theory
o Graph theory has a wide range of applications including social
networks, computer networks, logistics, and scheduling problems.
Types of Graphs
1. Undirected vs. Directed Graphs
o Undirected Graph: A graph where the edges have no direction.
The edge (u, v) is identical to (v, u).
o Directed Graph (Digraph): A graph where each edge has a
direction, going from one vertex to another. The edge (u, v) is
different from (v, u).
2. Weighted vs. Unweighted Graphs
o Weighted Graph: A graph where each edge has an associated
weight or cost.
o Unweighted Graph: A graph where all edges are treated equally,
with no weights assigned.
3. Simple Graph vs. Multigraph
o Simple Graph: A graph with no loops (edges connected at both
ends to the same vertex) and no more than one edge between any
pair of vertices.
o Multigraph: A graph that may have multiple edges between the
same set of vertices.
4. Connected vs. Disconnected Graphs
o Connected Graph: A graph in which there is a path between every
pair of vertices.
o Disconnected Graph: A graph where some vertices are not
connected by paths.
