Discrete Structures
Lecture # 23
Mr. Muhammad Adeel
Department of Computer Science
FAST -- National University of Computer and
Emerging Sciences. CFD Campus
GRAPH
A graph is a non-empty set of points called vertices
and a set of line segments joining pairs of vertices
called edges.
GRAPH
Formally, a graph G consists of two finite sets:
(1) A set V=V(G) of vertices (or points or nodes)
(2) A set E=E(G) of edges.
Where each edge corresponds to a pair of vertices.
EXAMPLE
EXAMPLE
EXAMPLE
SOME TERMINOLOGY
SOME TERMINOLOGY
SOME TERMINOLOGY
SOME TERMINOLOGY
EXAMPLE
Define the following graph formally by specifying its
vertex set, its edge set, and a table giving the edge
endpoint function.
SOLUTION
EXAMPLE
For the graph shown below:
EXAMPLE
SOLUTION
SOLUTION
SOLUTION
SOLUTION
SOLUTION
EXAMPLE
SOLUTION
SIMPLE GRAPH
DEGREE OF A
VERTEX
Let G be a graph and “v” a vertex of G. The degree
of “v”, denoted deg(v), equal the number of edges
that are incident on “v”, with an edge that is a loop
counted twice.
The total degree of G is the sum of the degrees of
all the vertices of G.
EXAMPLE
EXAMPLE
EXAMPLE
EXAMPLE
HANDSHAKING
THEOREM
EXAMPLE
SOLUTION
SOLUTION
SOLUTION
deg (a) = 1 deg (b) = 2 deg (a) = 1 deg (b) = 2
deg (c) = 3 deg (d) = 4 deg (c) = 3 deg (d) = 4
EXAMPLE
EXERCISE
In a group of 15 people, is it possible for each
person to have exactly 3 friends ?
EXERCISE
In a group of 15 people, is it possible for each
person to have exactly 3 friends ?
Answer: No because of handshaking theorem.
COMPLETE
GRAPH
EXAMPLE
EXERCISE
[Link] of each vertex is n-1
[Link](Kn) = n(n-1) =2m
[Link]. of edges = m = n(n-1)/2
REGULAR
GRAPH
i. Kn are (n-1)-regular graphs.
ii. Also, from the handshaking theorem, a regular graph
of odd degree will contain an even number of vertices.
iii. A 3-regular graph is known as a cubic graph.
EXAMPLE
BIPARTITE
GRAPH
EXAMPLE
EXAMPLE
DETERMINING
BIPARTITE GRAPH
DETERMINING
BIPARTITE GRAPH
EXAMPLE
SOLUTION
SOLUTION
SOLUTION
SOLUTION
COMPLETE
BIPARTITE GRAPH
No. of edges in Km,n is given by mn.
COMPLETE
BIPARTITE GRAPH
KONIGSBERG
BRIDGES PROBLEM
Pregel River
SOLUTION
EQUIVALENT FORM OF
BRIDGE PROBLEM
TERMINOLOGY
TERMINOLOGY
TERMINOLOGY
TERMINOLOGY
TERMINOLOGY
TERMINOLOGY
SUMMARY
no
PROBLEM
SOLUTION
SOLUTION
SOLUTION
SOLUTION
SOLUTION
SOLUTION
CONNECTEDNESS
EXAMPLE
EXAMPLE
EXAMPLE
EXAMPLE
EULER
CIRCUITS
EULER
RESULT
KONIGSBERG BRIDGES
PROBLEM
KONIGSBERG BRIDGES
PROBLEM
EXERCISE
EXERCISE
EXERCISE
Euler circuit: {a, b, c, d, f, e, d, g, f, i, h, g, c, h, b, i, a}.
EULER PATH
HAMILTONIAN
CIRCUITS
EXERCISE
SOLUTION
SOLUTION
PROPERTIES
EXAMPLE
EXAMPLE
Is the following graph a Hamiltonian
graph? Give the explicit reason.