FUNCTIONS
FUNCTIONS
• The function is the relation such that NO two ordered
pairs have the same first element.
• A function may be denoted as y=f(x) which is read “f of x”
𝒇 𝒙 = 𝟎, 𝟏 𝟏, 𝟐 𝟐, 𝟑 𝟐, 𝟑 𝟑, 𝟒
D = {0, 1, 2, 3}
R = {1, 2, 3, 4}.
0 1
1 2
Arrow diagram/ Mapping
2 3
3 4
Which mapping represents a function?
Example
Let f be a function from 𝑥 = 0, 1, 2, 3 𝑡𝑜 𝑦 =
𝑎, 𝑏, 𝑐 defined by 𝑓(0) = 𝑐 , 𝑓(1) = 𝑏 ,
𝑓(2) = 𝑏 and 𝑓(3) = 𝑐 . is 𝑓: 𝑥 → 𝑦 either
one to one or onto?
Example
Is the function 𝑓 𝑥 = 𝑥 2 from the set of integers
to the set of integers either one to one or onto?
Example
Show that f(x)= 5x+2 is surjective for ∀𝑥 ∈ ℝ.
What about ∀𝑥 ∈ ℤ
Example
Prove that the function 𝑓 ∶ 𝑁 → 𝑁 be defined by
𝑓(𝑛) = 𝑛 , is not surjective
2
Identify if the given relation is a function or not.
Identify if the given relation is a function or not.
Identify if the given relation is a function or not.
Function Notation
𝑓 𝑥 = 3𝑥 − 2, find: ℎ 𝑧 = 𝑧 − 4𝑧 − 9, find:
2
f(3)= 7 h(-2)= 3
f( -1)= -5 h( 0)= -9
INTRODUCTION TO
GRAPH THEORY
Graphs
Definition: A graph 𝐺 = (𝑉, 𝐸) consists of V, a non-
empty set of vertices and E a set of edges. Edges
connect either one or two vertices called endpoints
Edges
-maybe labeled by a pair of
vertices
- e is said to be incident
on v and w
Special Edges
Parallel edges
-2 or more edges joining a
pair of vertices
Loops
-an edge that starts and
ends at the same vertex
Special graphs
Simple graph
- a graph without loops or
parallel edges
Weighted graph
- graph where each edge is
assigned a numerical label or
weight
undirected graph Directed graph
Degree of graph
A vertex of degree 0 is called isolated
A vertex is pendant iff it has degree one
NOTE: A vertex with a loop has at least degree 2
Hand-shaking Theorem
Definition: Let G = (V, E) be an undirected graph
with edges e. Then
2𝑒 = σ𝑉𝐸 𝑉 deg(𝑣)
Hand-shaking Theorem
Suppose there are 6
people in a room and
each mush shake
hands with every other
person. How many
handshakes occurred?
Hand-shaking Theorem
How many edges are there if you have 10 vertices,
each of them degree 6?
𝑑𝑒𝑔− 𝑎 = 1
𝑑𝑒𝑔+ 𝑎 =2
Special types of Graphs
A complete graph denoted 𝐾𝑛 , is a simple graph
that contains exactly one edge between each pair of n
distinct vertices
Special types of Graphs
A cycle denoted 𝐶𝑛 , 𝑛 ≥ 3, consists of vertices
𝑣1 , 𝑣2 , … , 𝑣𝑛 and edges
𝑣1 , 𝑣2 , 𝑣2 , 𝑣3 … , 𝑣𝑛−1 , 𝑣𝑛
Special types of Graphs
A Wheel, 𝑤𝑛 , is obtained when we add an additional
vertex to 𝐶𝑛 and connected that vertex to each
existing vertex
Special types of Graphs
An n-dimensional hypercube or n-cube, denoted 𝑄𝑛 ,
is a graph with vertices representing the 2 bit strings
𝑛
of length n. Adjacent vertices differ exactly by one bit
position
Special types of Graphs
Bipartite Graphs
A simple graph is called bipartite if its vertex set ,
𝒗𝟏 , can be partitioned into two disjoint subsets such
that each edge connects a vertex from one subset to a
vertex of the other.
Special types of Graphs
A complete bipartite graph 𝐾𝑚,𝑛 is a bipartite with
subsets of m and n vertices, respectively with an edge
between each pair or vertices from opposite subsets.
Suppose Adam, Ben, Chris, David and are training for
tasks at work. Adam and Chris are training for task 1,
Ben, Chris and Eric are training for Task 2, David is
training for task 3, Chris and Eric are training for task
4 and Eric is training for task 5. Create a graph to
model this, then determine if a matching is possible.
Subgraph
Definition: A subgraph 𝐻 = 𝑉𝐻 , 𝐸𝐻 𝑜𝑓𝐺 = 𝑉𝐺 , 𝐸𝐺
requires that :
1. 𝑉𝐻 ⊆ 𝑉𝐺
2. 𝐸𝐻 ⊆ 𝐸𝐺 where each 𝑒 ∈ 𝐸𝐻 are incident to v ∈ 𝑉𝐻
Subgraph
Definition: Let 𝐺 = (𝑉, 𝐸) be a simple graph. The
subgraph induced by a subset W of the vertex V is the
graph (𝑊, 𝐹), where the edge set F contains an edge in E,
if and only if both endpoints of this edge are in W.
