Matn

Graph Theory
QCPP010 - Discrete mathematics

WHAT IS GRAPH?
A
• A graph G = ( V , E) consists of V, a
nonempty set of vertices (or nodes)

B
and E, a set of edges. Each edge has
either one or two vertices associated D
with it, called its endpoints.
C
EXAMPLE#01
• 𝐺 = (𝑉, 𝐸) where 𝑉 = {𝑎, 𝑏, 𝑐, 𝑑} and 𝐸 = { {𝑎, 𝑏}, {𝑎, 𝑐}, {𝑏, 𝑐}, {𝑐, 𝑑}}
a
d
c
b
DEGREE OF A VERTEX
• The degree of a vertex V of a graph G denoted by d(V) is the number of

edges incident with the vertex V.
a d The degree of each vertex is as follows:
𝑑 𝑎 =1
𝑑 𝑏 =3
𝑑 𝑐 =4
b c 𝑑 𝑑 =2
EXAMPLE#02
• Determine the sum of the degrees of all the vertices of the graph
V1
V2 Solution:
= 𝑑(𝑉1)+ 𝑑(𝑉2)+ 𝑑(𝑉3)+ 𝑑(𝑉4)+ 𝑑(𝑉5)

V5 = 3+ 4+ 5+ 3+ 3
= 𝟏𝟖
V3
V4
EXAMPLE#03
• Determine the sum of the degrees of all the vertices of the graph
V1
Solution:
V2 V4 V6 = 𝑑(𝑉1)+ 𝑑(𝑉2)+ 𝑑(𝑉3)+ 𝑑(𝑉4)+ 𝑑 𝑉5 + 𝑑(𝑉6)

= 1+ 2+ 4+ 2+ 3 + 2
= 𝟏𝟒
V3
V5
TERMINOLOGY
• Pendant Vertex - A vertex with degree one.
• Pendant Edge - The only edge which is an incident with a pendant vertex.
• Odd Vertex: - A vertex having degree odd number.
• Even Vertex - A vertex having a degree even number.
• Incident Edge - An edge is called incident with the vertices is connects.
• Adjacent Vertices - Two vertices are called adjacent if an edge links them. If there is an edge
(u, v), then we can say vertex u is adjacent to vertex v, and vertex v is adjacent to
vertex u.
EXAMPLE#04
• Consider the graph as shown in figure and determine the following: Pendant vertices,
Pendant edges, Odd vertices, Even vertices, Incident edges, and Adjacent vertices.
Solution:
V1 Pendant Vertices: V5
V3
Pendant Edges: (V4,V5) or e5
e1
Odd vertices: V2 and V5
e2 V5
e3 Even Vertices: V1, V3, and V4
e5 Incident Edges: The edge e1 is an incident on V1 and V3.

e4 (e2 , e3 , e4 , e5 )
V2 V4 Adjacent Vertices: The vertex V1 is adjacent to V2 and V3.
(V2 , V3 , V4 , V5 )
EXAMPLE#05
• Consider the graph as shown in figure and determine the following: Pendant
vertices, Pendant edges, Odd vertices, and Even vertices
Solution:
V1 V2
Pendant Vertices: V5 and V6
V4 Pendant Edges: (V1,V5) and (V3,V6)
V3
Odd vertices: V1, V3 ,V5 ,and V6
Even Vertices: V2 and V4
V5 V6
TYPES OF GRAPHS
Null Graph
• A null graph has no edges. The null graph of 𝑛 vertices is denoted by 𝑁𝑛.
b
a d
c
TYPES OF GRAPHS
Simple Graph
• A graph is called simple graph/strict graph if the graph is undirected and does not
contain any loops or multiple edges.
b c
TYPES OF GRAPHS
Multi-Graph
• If in a graph multiple edges between the same set of vertices are allowed, it is called
Multigraph.
b c
TYPES OF GRAPHS
Undirected Graphs
• An Undirected graph 𝐺 consists of a set of vertices, 𝑉 and a set of edge 𝐸. The edge
set contains the unordered pair of vertices.
Example: Let V = {a, b, c, d} and a b a b

E = {(a, b), (a, d), (c, d), (b, c)}.
Draw the graph.
d c c d
TYPES OF GRAPHS
Directed Graphs
• A directed graph is defined as an unordered pair (𝑉, 𝐸), where 𝑉 is the set of points
called vertices and 𝐸 is the set of edges. Each edge in the graph 𝐺 is assigned a
direction and is identified with an ordered pair (𝑢, 𝑣), where 𝑢 is the initial vertex,
and 𝑣 is the end vertex..
Solution
Example: Consider the graph a b G = { {a,b,c},
G = (V, E) as shown in fig. {(a,b), (b,a),
Determine the vertex set
and edge set of graph G. (b,b), (b,c),
c (a,c)}
}.
TYPES OF GRAPHS
Connected and Disconnected Graph

• A graph is called connected if there is a path from any vertex 𝑢 to 𝑣 or vice-versa
while a graph is called disconnected if there is no path between any two of its
vertices.
a
c a b
b c
d d
Connected Graph Disconnected Graph
TYPES OF GRAPHS
Complete Graph
• A graph in which every pair of vertices is joined by exactly one edge is called
complete graph.
a b
d c
TYPES OF GRAPHS
Regular Graph
• A graph is regular if all the vertices of the graph have the same degree. If the degree
of all the vertices is k, then it is called k-regular graph.
a a b
b c
d c
Thank You!
Any Questions?

Matn

Uploaded by

Copyright:

Available Formats

Matn

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Matn

Uploaded by

Copyright:

Available Formats

Graph Theory

QCPP010 - Discrete mathematics

nonempty set of vertices (or nodes)

• The degree of a vertex V of a graph G denoted by d(V) is the number of

= 𝑑(𝑉1)+ 𝑑(𝑉2)+ 𝑑(𝑉3)+ 𝑑(𝑉4)+ 𝑑(𝑉5)

V2 V4 V6 = 𝑑(𝑉1)+ 𝑑(𝑉2)+ 𝑑(𝑉3)+ 𝑑(𝑉4)+ 𝑑 𝑉5 + 𝑑(𝑉6)

• Pendant Vertex - A vertex with degree one.

• Odd Vertex: - A vertex having degree odd number.

• Even Vertex - A vertex having a degree even number.

• Incident Edge - An edge is called incident with the vertices is connects.

e5 Incident Edges: The edge e1 is an incident on V1 and V3.

Example: Let V = {a, b, c, d} and a b a b

Connected and Disconnected Graph

You might also like