Graph Theory: The Basics
Paths & Cycles
DISCUSSANT: VICTOR RUSSEL G. MACABUHAY
Definition
A graph is depicted diagrammatically as a set of dots depicting vertices
connected by lines or curves depicting edges.
A graph is a structure amounting to a set of objects in which some pairs of
the objects are in some sense “related”.
Two Components
A node or a vertex
An edge E or ordered pair is a connection
between two nodes u,v that is identified by
unique pair(u,v). The pair (u,v) is ordered
because (u,v) is not same as (v,u) in case of
directed graph.The edge may have a weight or
is set to one in case of unweighted graph.
Sample Graph
Characteristics of graphs
Adjacent node: A node ‘v’ is said to be adjacent node of
node ‘u’ if and only if there exists an edge between ‘u’ and
‘v’. Nodes are adjacent if they are the endpoint of the edge.
Degree of a node: In an undirected graph the number of
nodes incident on a node is the degree of the node.
In case of directed graph ,Indegree of the node is the number
of arriving edges to a node.
Outdegree of the node is the number of departing edges to a
node.
Paths
It is a trail in which neither nodes nor edges are repeated.
Path: A path of length ‘n’ from node ‘u’ to node ‘v’ is defined as
sequence of n+1 nodes.
Cycles
Traversing a graph such that we do not repeat a vertex nor we repeat a
edge but the starting and ending vertex must be the same i.e we can
repeat starting and ending vertex only then we get a cycle. 𝑛 ≥ 3
Isolated node: A node with degree 0 is known as isolated node. It
finds its application in LAN network in finding whether a system is
connected or not.
1
Types of graphs
Directed graph:
A graph in which the direction of the edge is defined to a particular node
is a directed graph
a. Directed Acyclic graph: It is a directed graph with no cycle.For a vertex ‘v’
in DAG there is no directed edge starting and ending with vertex ‘v’.
Undirected graph
A graph in which the direction of the edge is not defined.So if an edge
exists between node ‘u’ and ‘v’,then there is a path from node ‘u’
to ‘v’ and vice versa.
a. Connected graph: A graph is connected when there is a path between
every pair of vertices.
B. Biconnected graph: A connected graph which cannot be broken down
into any further pieces by deletion of any.
C. Complete graph: A graph in which each pair of graph vertices is
connected by an edge.In other words,every node ‘u’ is adjacent to every
other node ‘v’ in graph ‘G’.A complete graph would have n(n-1)/2
edges.
For example
A. N𝑜𝑑𝑒𝑠 = 5
𝑛(𝑛 − 1)
𝐸=
2
5(5−1)
𝐸= 2
5(4)
𝐸= 2
20
𝐸= 2
𝐸 = 10 𝑒𝑑𝑔𝑒𝑠
B. N𝑜𝑑𝑒𝑠 = 10
𝑛(𝑛 − 1)
𝐸=
2
10(10−1)
𝐸= 2
10(9)
𝐸= 2
90
𝐸= 2
𝐸 = 45 𝑒𝑑𝑔𝑒𝑠
C. N𝑜𝑑𝑒𝑠 = 13
𝑛(𝑛 − 1)
𝐸=
2
13(13−1)
𝐸= 2
13(12)
𝐸= 2
156
𝐸= 2
𝐸 = 78 𝑒𝑑𝑔𝑒𝑠
Applications
Graph is a data structure which is used extensively in our real-life.
Social Network: Each user is represented as a node and all their
activities,suggestion and friend list are represented as an edge between
the nodes.
Google Maps: Various locations are represented as vertices or nodes and
the roads are represented as edges and graph theory is used to find
shortest path between two nodes.
Recommendations on e-commerce websites: The “Recommendations for
you” section on various e-commerce websites uses graph theory to
recommend items of similar type to user’s choice.
Graph theory is also used to study molecules in chemistry and physics.
EXERCISES
Find the number of edges given the nodes of the following
N = 20
N = 24
N = 50
N = 51
N = 100
