Discrete Mathematics:

Graph Theory
Presentors: Adrienne M. Medenilla &
Louielee O. Corpuz
Learning Objectives:
01 Learn the definition 03 Discover their
of Vertex, Degree, Practical uses in
& Graphs (Regular Computer Science
Graphs)

02 Examine some of
their Examples/
Illustrations
WHAT IS GRAPH is the study of the graph.
A graph is determined as a
THEORY? mathematical structure that
represents a particular
function by connecting a set
f(x) = x of points. It is used to create
a pairwise relationship
between objects.
v VERTEX (VERTICES)
Also called a NODE of a graph is one
of the objects that are connected
together. The connections between
the vertices are called EDGES or ISOLATED VERTEX
LINKS.
A vertex of a graph that has no
edges is a vertex with zero (0)
degree.
v DEGREE of a Vertex
the number of edges connected to a
vertex. It is denoted deg(v)

Here, we have:

Deg(A) = 3,
Deg(B) = 2,
Deg(C) = 3, and
Deg(D) = 2.
WHAT IS GRAPH?
A graph is a pictorial representation
of any data. BASIC TYPES OF GRAPH:

In graph theory, the graph Undirected Graph (Undirected

represents the set of objects, that are network) - a graph where the nodes
related to each other. The objects are are connected, in which all the edges
expressed by vertices or nodes and are bidirectional.
the relation between the pair of
nodes, are expressed by edges. Directed Graph - one which the
edges have a direction associated
with them.
TYPES OF GRAPHS
v Finite Graphs - A graph is said to be finite v Trivial Graph - contains only one vertex
if both the number of vertices and the and no edge. Also known as a singleton
number of edges in a finite graph are graph or a single vertex graph. The simplest
limited and can be counted. type of graph, often used as a starting
point for building more complex graphs.

v Infinite Graph - A graph is said to be v Simple Graph - does not contain more
infinite if it has an infinite number of than one edge between the pair of vertices.
vertices as well as an infinite number of A simple railway track connecting different
edges. cities is an example of a simple graph.
TYPES OF GRAPHS
v Null Graph - A graph of order n and size
v Multi Graphs - Any graph which contains zero is a graph where there are only isolated
some parallel edges but doesn’t contain any vertices with no edges. Also be referred to as
self-loop. For example a Road Map. an edgeless graph, an isolated graph, or a
discrete graph
• Parallel Edges: If two vertices are connected
with more than one edge, meaning there are
many routes but one destination.
• Loop: An edge of a graph that starts from a
vertex and ends at the same vertex.
v Complete/Full Graph - A simple graph
with n vertices is called a complete graph if
the degree of each vertex is n-1
TYPES OF GRAPHS
v Pseudo Graphs - A graph G with a self- v Bipartite Graph - is a type of graph where
loop and some multiple edges. In contrast, the vertices can be split into two separate
a simple graph is a graph that does not groups, often called "partitions" or "sets," in
allow for loops or multiple edges. such a way that all edges connect vertices
from one partition to the other and not
within the same partition.

v Regular Graph - A simple graph is

said to be regular if all vertices of graph G
are of equal degree.
TYPES OF GRAPHS
v Labeled Graphs - If the vertices and edges v SubGraph - A graph G1 = (V1, E1) is
of a graph are labeled with name, date, or called a subgraph of a graph G(V, E) if
weight then it is called a labeled graph. It is V1(G) is a subset of V(G) and E1(G) is a
also called Weighted Graph. subset of E(G) such that each edge of G1
has same end vertices as in G.

v Connected or Disconnected Graph - a

graph is said to be connected if there exists
at least one path between each and every
pair of vertices in graph G, otherwise, it is
disconnected. A null graph with n vertices
is a disconnected graph
TYPES OF SUBGRAPHS v Spanning Graphs - Consider the graph G(V,E)
as shown below. A spanning subgraph is a
subgraph that contains all the vertices of the
v Vertex-disjoint subgraph: a type of graph
original graph G that is G'(V’,E’) is spanning if
in which no two vertices share a common
V’=V and E’ is a subset of E.
neighbor. In other words, it's a graph
where the sets of neighbors of any two
distinct vertices are disjoint.
v Edge disjoint subgraph: no two edges of
the subgraph share a common endpoint. In
other words, it's a subgraph in which each
edge is only used once, and no two edges
overlap or share vertices.
So one of the spanning subgraph can be as shown
Note: Edge disjoint subgraph may have vertices below G'(V’,E’). It has all the vertices of the
in common but a vertex disjoint graph cannot original graph G and some of the edges of G.
have a common edge, so the vertex disjoint
subgraph will always be an edge-disjoint
subgraph.
PRACTICAL USES
IN COMPUTER
SCIENCE
1. Network Analysis:
● Vertices represent entities (e.g.,
computers, routers), edges
represent connections/links.

● Degree of a vertex can indicate the

importance or centrality of a
vertex in a network.

● Graph algorithms analyze network

topology, optimize routing, and
detect anomalies. (multi)
2. Social Network
Analysis:
● Vertices represent individuals or
entities, edges represent
relationships (e.g., friendships,
interactions).

● Degree of a vertex measures social

connectivity or influence.

● Graph algorithms identify

influential users, detect
communities, and predict
connections. (multi,labeled)
3. Database
Management:
● Vertices represent entities (e.g.,
people, products), edges represent
relationships.

● Degree of a vertex may indicate

the number of connections or
associations.

● Graph databases use vertices and

edges to model complex
relationships for efficient querying
and analysis. (sub, complete)
4. Knowledge
Representation:
● Vertices represent concepts or
ideas, edges represent relationships
(e.g., semantic connections).

● Degree of a vertex may indicate

the relevance or connectivity of a
concept.

● Graph-based knowledge graphs

organize information and support
semantic search and inference.
(undirected)
5. Recommendation
Systems:
● Vertices represent users or items,
edges represent interactions or
similarities.

● Degree of a vertex reflects user

activity or item popularity.

● Graph algorithms power

collaborative filtering, content-
based recommendation, and
personalized recommendations.
(bipartite)
6. Circuit Design:
● Vertices represent components (e.g.,
gates, transistors), edges represent
connections.

● Degree of a vertex signifies the

complexity or fanout of a
component.

● Graph algorithms optimize circuit

layouts, minimize signal delay, and
improve power efficiency. (cyclic)
7. Compiler
Optimization:
● vertices represent program points,
edges represent control flow.

● Degree of a vertex can indicate the

number of incoming or outgoing
control flow paths.

● Graph-based data flow analysis

optimizes code, detects
dependencies, and performs
program transformations. (Cyclic,
directed)
 These practical applications demonstrate
how vertices, degrees, and graph structures
play crucial roles in various areas of
computer science, aiding in modeling,
analysis, optimization, and decision-making
processes.

THANK YOU FOR LISTENING <3

QUIZ!!!
IDENTIFICATION (10 Items)
Read and Answer what is being asked in the following questions below. Good Luck!

1 it is determined as a mathematical structure that represents a

particular function by connecting a set of points.

2 This is where a vertex of a graph has no edges and with a

degree of zero.

3 it is the number of edges connected to a vertex.

4 A type of graph that has infinite number of vertices and edges.

5 This is when two vertices are connected with more than one
edge is called _____

6 A simples type of graph where all vertices of Graph (G) are of

equal degrees.

7 A graph labeled with name, date, or weight. It is also called

Weighted Graph.
8 An edge of a graph that starts from a vertex and ends at the
same vertex.

9 It is a graph that does not contain more than one edge between
the pair of vertices.

10 It is the study of Graphs.

Answers
1 Graph 6 Regular Graph
2 Isolated vertex 7 Labeled Graph
3 Degree 8 Loop
4 Infinite Graph 9 Simple Graph
5 Parallel Edges 10 Graph Theory
Resources
for more information visit: