MATHEMATICS IN THE MODERN WORLD

 SOURCE CODING AND

CHANNEL CODING
- In transmitting messages, coding is defined as
source coding and channel coding.
 TWO PROCESSES IN CODING
- Encoding is transforming messaged into bits
of message that is suitable in communication.
- Decoding is the opposite process of encoding
 DATA COMPREHENSION OR
CODING THEORY SOURCE ENCODING
- Defined as converting the message from the
CODING THEORY - is the study of the sender into bits suitable to the communication
properties of codes and their respective fitness for
channel.
specific applications. Codes are used for data
compression, cryptography, error detection and
BIT (BINARY DIGIT) - the smallest
correction, data transmission and data storage.
unit of measurement used to quantify computer
CODES - are studied by various scientific disciplines, data. It contains a single binary value of 0 or 1.
such as information theory, electrical engineering, Example: ASCII (AMERICAN STANDARD
mathematics, linguistics, and computer science—for the CODE) that converts each character int the
purpose of designing efficient and reliable data message to a byte of 8 bits.
transmission methods.

* This typically involves the removal of redundancy and

the correction or detection of errors in the transmitted
data.

COMMUNICATION SYSTEM - In most computer systems, a byte is a unit of

- composed of sender (or message source), data that is eight binary digits long. A byte is
communication channel, and the receiver. the unit most computers use to represent a
 COMMUNICATION CHANNEL character such as a letter, number or
- Is the physical medium through which typographic symbol.
information is transmitted. Example: Consider the source encoding
- Ex: telephone lines, internet cables, fiber-optic of four directions as follows:
lines, and air. Some storage data can be NORTH - 00
considered channels (CD-ROMS, hard drives). SOUTH - 01
EAST - 10
 NOISES WEST – 11
- It alters the message in the channel that will *Suppose the message “NORTH”, which is encoded as 00, is
cause disruption and error in the messages. transmitted over a noisy channel. The message may encounter
errors and may be received as 01. The receiver will get the
message 01 and decode it as “SOUTH” without realizing that the
message is corrupted

1|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD
With this problem at hand, additional process of REPITITION CODE: ENCODING
encoding is required known as Channel Coding . - In coding theory, the repetition code is one of the
most basic error-correcting codes.
- In order to transmit a message over a noisy
channel that may corrupt the transmission in a
few places, the idea of the repetition code is to
just repeat the message several times.
CHANNEL CODING - Is defined as adding
- Suppose that the source encoding is already
some form of redundancy to the source encoded
done and that the encoded message is of fix
message so that the errors can be detected or even
length k. The channel encoding by repetition is
corrected.
performed by taking the k bits then repeating it
PARITY CHECK - Parity check is also called 2r + 1, where r is greater than or equal to 1 is
as “Vertical Redundancy Check (VRC)” a fixed integer.
- Where in single bit is added to the message as Example:
redundancy bit. Suppose that the source encoded message is
- A bit string is said to have an odd parity if 110 where k=3. If you choose r= 2 , the message
there is an odd number of 1s. must be repeated 2r +1 = 2(2) + 1 or 5 times.
- Even parity if there is an even number of 1s. This will result to 110110110110110
We add redundancy bit to message such that it REPITITION CODE: DECODING
will become an even parity Example:
Assume that the message transmitted through
a noisy channel and distorted. The received
message is 111001101110010 .The channel
encoding uses repetition code where k= 3.
Decode the received message.
Solution: 111 001 101 110 010
FIRST BIT- Consider the most frequent bit in positions
1,4,7,10, and 13
SECOND BIT- Consider the most frequent bit in
*There is two types of parity bits in error detection, positions 2,5,8,11,and 14
they are: THIRD BIT- Consider the most frequents bit in positions
ODD PARITY - If the data has even number of 3, 6, 9, 12, and 15
1’s, the parity bit is 0.
111/001/101/110/010
- Odd number of 1’s, the parity bit is 1.
1 2 3 / 4 5 6/7 8 9 /10 11 12 /13 14 15
Example:
Decoded Message : 111
Data is 10010001 -> parity bit 1
EVEN PARITY - If the data has odd number of
MODULAR ARITHMETIC
1’s, the parity bit is 0.
- Is a system of arithmetic for integers, which
- Even number of 1’s, the parity bit is 1. considers the remainder.
Example: - In modular arithmetic, numbers "wrap around"
upon reaching a given fixed quantity (this given
data is 10010101 -> parity bit 1

2|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD
quantity is known as the modulus) to leave a
remainder.

CONGRUENCE - Let a and b are integers and

m is a natural counting number.
- a IS CONGUENT TO b MODULO m” a ≡ b
(mod m), IF m DIVIDES a - b OR b – a
Example:
1. Verify if the congruence is true 4 ≡ 9 (mod
2)
2. 3 ≡ 9 (mod 2) It is true since 9 – 3 = 6,
which is divisible by 2.
LEAST RESIDUE - To determine the least
residue is to simply get the remainder when b is divided
by m.
- b(mod m) means b divided by m. m is referred
to as the modulus (divisor)
- Find the least residue, r r= 54(mod 7)
Example:
29 (mod 3) Answer is 2, since 2 is the
remainder of 29/3.
25 (mod 5) Answer is 0, since there is no
remainder of 25/5.

OPERATIONS IN MODULAR
ARITHMETIC
 Modulo addition is defined as (a+b)mod m
 Modulo subtraction is defined as (a-b)mod m
 Modulo multiplication is defined as (a*b) mod m
 Modulo division is defined as (a/b) mod m

Example:
1. 10 - 4 (mod 5) = 1
2. 11 + 7 (mod 3) = 0
3. 8 + 7 (mod 7) = 1
4. 20 - 7 (mod 5) = 3
5. 31 - 6 (mod 4) = 1

3|Nell Laminero
MATHEMATICS IN THE MODERN WORLD

 UNITED STATES POSTAL

SERVICE (USPS) - is consisting of
11 digits, while the Credit Card uses 16
digits where both of them uses their
last digits as the check digits.

CHECK CODE AND CHECK

DIGITS
- There are several methods in producing
identification numbers which are unique.
- In the following methods, modular arithmetic is
used to produce and verify identification
numbers. Formulas for the Check Digits
EXAMPLES:
1. UNIVERSAL PRODUCT CODE (UPC)-
- Each examples uses their last digit as the
CHECK DIGIT : d12
check digits to verify the identification number
d12= 10 – (3d1 +d2 + 3d3 + d4 +3d5
 UNIVERSAL PRODUCT CODE +d6 + 3d7 + d8 + 3d9 + d10 + 3d11)(mod10)
(UPC) - is mainly used in products 2. INTERNATIONAL STANDARD BOOK
sold in department stores and NUMBER (ISBN-10)-
groceries. The UPC consists of CHECK DIGIT : d10
barcodes with 12 digits where the last d10 = 11- (10d1 + 9d2 + 8d3 + 7d4 +
one is the check digit. 6d5 + 5d6 + 4d7 +3d8 +2d9 )(mod 11)
3. INTERNATIONAL STANDARD BOOK
NUMBER (ISBN- 13)-
CHECK DIGIT : d13
d13= 10 – (d1 + 3d2 + d3 + 3d4 + d5 +
3d6 + d7 +3d8 + d9 + 3d10 + d11 + 3d12
)(mod10)
 INTERNATIONAL 4. UNITED STATES POSTL SERVICES
STANDARD BOOK NUMBER
(UPS)-
(ISBN) - is used on books where
CHECK DIGIT : d11
usually found at the last page of the
d11 = 9 – (d1 +d2 + d3 + d4 + d5 +
book. ISBN can be ISBN-10 or ISBN-13
d6 + d7 + d8 + d9 + d10 )(mod 9)
where they used 10 digits or 13 digits
5. CREDIT CARD-
string of number respectively with the
CHECK DIGIT : d16
last digit as the check digit.
d16 = 10 – (2d1 +d2 +2d3 +d4 +2d5
+d6 + 2d7 +d8 +2d9 +d10 +2d11 +d12
+2d13 +d14 +2d15 )(mod10)
4|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD
*ADD ALL THE DIGITS, TREATING THE TWO-DIGIT
NUMBERS AS TWO SINGLE DIGITS.

Example:
1. Determine the check digit for a new product if
the first 11 digits are 8-21345- 67132.
SOLUTION: Let d1 =8, d2 =2, d3 =1, d4 = 3, d5
=4, d6 = 5, d7 = 6, d8 =7, d9 = 1, d10 =3, d11 = 2
d12= 10 – (3d1 +d2 + 3d3 + d4 +3d5 +d6 + 3d7
+ d8 + 3d9 + d10 + 3d11)(mod10
2. Determine the check digit for USPS if the first
10 digits are 12-2133-1321.
SOLUTION: Let d1 =1, d2 =2, d3 =2, d4 = 1, d5
=3, d6 = 3, d7 = 1, d8 =3, d9 = 2, d10 =1 d11 = 9
– (d1 +d2 + d3 + d4 + d5 + d6 + d7 + d8 + d9 +
d10) (mod 9)
3. Verify if the given Credit Card identification
number 4301-1234-8888-3751 is valid.
SOLUTION: Let d1 = 4, d2 = 3, d3 = 0, d4 = 1,
d5 = 1, d6 = 2, d7 = 3, d8 = 4, d9 = 8, d10 = 8,
d11 = 8, d12 = 8, d13 = 3, d14 = 7,and d15 = 5.
d16 = 10 – (2d1 +d2 +2d3 +d4 +2d5 +d6 +2d7
+d8 +2d9 +d10 +2d11 +d12 +2d13 +d14 +2d15
)(mod10)

5|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD

Simple Method
SHIFT CIPHER (CEASAR CIPHER)
- it is the simple type of substitution cipher
- it uses shift in forming the key of cryptography

CRYPTOGRAPHY
- It is a science of protecting information by
encoding it into unreadable format.
- Originated from two Greek words such as
“KRYPTO” which means hidden and
“GRAPHENE” which means writing.
- It is a method of making and breaking of secret
codes

CRYPTOGRAPHY- is a science of encrypting MODULO OPERATOR

and decrypting written communication. - the sender of the uses the key K to encrypt and
to decrypt the secret message.
Steps to Encrypt:
1. Express the letters of the alphabet from 0-25
2. Calculate Y=(C+K) mod 26
3. Convert the number Y into a letter following the
ENCRYPTION order of the letter of the alphabet
- Is the process of transforming plain text into Example:
codes form using a certain algorithm. “MMW is fun to learn” let k = 5
DECRYPTION A B C D E F G H I J K L M
- The process of returning/converting back the 0 1 2 3 4 5 6 7 8 9 10 11 12
coded message into plain text. N O P Q R S T U V W X Y Z
PLAIN TEXT 13 14 15 16 17 18 19 20 21 22 23 24 25
- original text
CIPHER TEXT M M W I S F U N T O L E A R N

- coded text 12 12 22 8 18 5 20 13 19 14 11 4 0 17 13
KEY Add 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
- the strings of information that is used to reveal
Ans 17 17 27 13 23 10 25 18 24 19 16 9 5 22 18
the encrypted message into readable form

6|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD
Y = (17 17 27 13 23 10 25 18 24 19 16 9 5 22 18)mod26
Y = (17 17 1 13 23 10 25 18 24 19 16 9 5 22 18)
Ans: R R B N X K Z S Y T Q J F W S
Steps to Decrypt:
1. Express the letters of the alphabet from 0-25
2. Calculate C=(Y-K) mod 26
3. Convert the number C into a letter following the
order of the letter of the alphabet
Example:
“RRBNXKZSYTQJFWS” let k = 5
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Y = (12 12 -4 8 18 5 20 13 19 14 11 4 0 17 13)mod26
Y = (12 12 22 8 18 5 20 13 19 14 11 4 0 17 13)
ANS: MMW IS FUN TO LEARN

7|Nell Laminero
MATHEMATICS IN THE MODERN WORLD
representative with the highest
decimal value until the
representatives are complete.
Example:
A new school offering the complete six
grades in high school has the following
enrolment in the different grades below.
The administrations are to apportion
the 20 teachers for each grade.
Calculate
a. The standard divisor
b. The standard quota
Solution:
APPORTIONMENT
- the equal proportion
- Is a method of dividing a whole into various
parts.
- It means that the numbers of representative
(the seat) is proportion to the population size
being represented.
Methods of Apportionment
 HAMILTON PLAN Completed Table:
Standard divisor (D) –the number of
voters represented by each
representative.
Formula:
D= Total Population =N
No. of representative R
Standard quota (Q) – the whole part of
the quotient when the population of the
sub – group is divided by the standard
divisor.
Formula:
Q= Sub-group population = n  JEFFERSON PLAN
Standard Divisor D - This method uses a modified standard divisor
NOTE: that arrives at the correct or exact numbers
1. Standard quota , Q must be an of representative using trial and error.
integer. In case of decimals, just - The modified uses an assume value always
drop the decimal values . smaller than the standard divisor
2. When the total standard quota is
 APPORTIONMENT
not equal to given total apportioned
or the number of representative ,
PRINCIPLE
place an additional representative - A new representative is added to a sub – group
to the next the sub – group due to an increase in population.

8|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD
- The representative is assigned to the group in additional agent. Use the Huntington –Hill
such a way it gives the smallest relative apportionment to justify your answer.
unfairness of apportionment.

Solution:
𝟐
𝑨 𝑷
Solution: Formula, H=𝒂(𝒂+𝟏)
Example:
RBSN company wants to add a new call centre agent
in one of its office. Report indicates an increase in the
daily calls of the offices in the past month. Determine
which office should get the additional agent. Use the
apportionment principle to justify your answer.

Since H = 421.77 has the highest Huntington – Hill

number, So that the Ortigas office will get the new
agent

Answer:
R = 0.30 (the lowest ) means the new agent or
representative will goes to Ortigas office.
 HUNTINGTON- HILL
APPORTIONED METHOD
- The method that make use of equal proportion.
- The new additional representative to a sub –
group must have the highest Huntington number.

Example:
RBSN company wants to add a new call center
agent in one of its office. Report indicate an
increase in the daily calls of the offices in the past
month. Determine which office should get the

9|Nell Laminero
 MATHEMATICS IN THE MODERN WORLD

BORDA COUNT
- Award points to candidates based on
preference schedule, then declare the winner to
be the candidate with the most points.

BALLOT
ST POINTS
1 B B gets 3 points
ND
2 D D gets 2 points
VOTING 3
RD
A
A gets 1 point

- Voting is a powerful tool in decision making.

- It is a method that uses votes to determine the In general, if Nis the number of candidates
winner. - Each first-place vote is worth N points.
Methods of Voting - Each second-place vote is worth N –1points
MAJORITY VOTING - Each third-place vote is worth N –2points.
- Majority Vote: over 50 % of the people voting - Each Nth-place (i.e., last place) vote is worth 1
must vote for the candidate point.
Example:
A corporation would like to invite a new investor. The
PLURALITY METHOD possibilities are Ayala (A), Bonifacio (B), Calixto (C),
- Each voter votes for one candidates, and the and Dancel (D). Who is the winner under the Borda
candidate with the most votes wins. Count?
- In-case of ties, voting should be done using the
run-off election.
Example of Majority and Plurality Method:
Which among the four candidates won
(a) By Majority (b) by Plurality

Ayala (A): 70 + 90 + 60 + 30 = 250 points

Bonifacio (B): 140 + 60 + 40 + 15 = 255 points
Calixto (C): 105 + 30 + 80 + 45 = 260 points
Dancel (D): 35 + 120 + 20 + 60 = 235 points
CALIXTO wins.
PLURALITY BY ELIMINATION
- The plurality with elimination voting method is
also known as an instant run-off voting and
sequential run-off voting.

10 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
- It is a preferential voting method and
candidates that have the least first place votes Step 3: Eliminate again candidate with the
get eliminated until one candidate has majority
of first place votes.
fewest 1st Place
Example:

A = 5+2+4 = 11
B = 6 + 3 =9
The winner is candidate A
PAIRWISE COMPARISON VOTING
- Compare each two candidate’s head-tohead.
- Award each candidate one point for each head-
to-head victory.
Step 1: Eliminate candidate with the fewest - The candidate with the most points wins.
1st Place Example:

Step 2: Adjust the ranking of the remaining

candidates
Then…

Compare A to B.
 5+ 2+4 =11 voters prefer A.
 6+ 3= 9 voters prefer to B.

11 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
 A wins the pairwise comparison and
gets 1 point.

Compare A to C.
 5+3 =8 voters prefer A.
 6 + 2+ 4 = 12 voters prefer to C.
 C wins the pairwise comparison and
gets 1 point.
Compare A to D.
 5+ 2 =7 voters prefer A.
 6+ 3+4= 13 voters prefer to D.
 D wins the pairwise comparison and
gets 1 point.
Compare B to C.
 6+3 =9 voters prefer B.
 5+ 2+ 4 = 11 voters prefer to C.
 C wins the pairwise comparison and
gets 1 point.
Compare B to D.
 6+3 =9 voters prefer B.
 5 + 2+ 4 = 11 voters prefer to D.
 D wins the pairwise comparison and
gets 1 point.
Compare C to D.
 6+2 =8 voters prefer C.
 5 + 3+ 4 = 12 voters prefer to D.
 D wins the pairwise comparison and
gets 1 point.
A = 1, B = 0, C= 2, D = 3
Winner is D = 3

12 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD

NOTE: From example 3;

1. Edge e4 is known as Loop. Loop is an edge that
connects a vertex to its self.
2. Edges e7 and e8 are called multiple edges or parallel
edges.
Parallel Edges – are edges that connect the same
vertices.

PATH
- A path in graph theory is a sequence of edges.
GRAPH THEORY Example:
GRAPH Consider the following graphs below.
- A diagram that contains information and
depicts connection and relationship between the
various parts of the diagram.
Example:
1.) Road Map
2.) Circuit Diagram
3.) Flow Chart
4.) Transportation Route
5.) Tree Diagram Paths Length
Essentials Features of a Graph Ade 3
Adc 3
THE OBJECTS – referred to as the nodes or
vertices Bce 3
Abced 5
EDGES – the connecting lines
adecb 5
Example: Consider the following graphs. Note:
1. A path can repeat edges.
1. The graph has 4 vertices and 4 edges 2. The length of a path refers to the number of edges
connected.
3. If the direction is not indicated in the graph by an
arrow, the movement is can be in any direction to find a
path (you can move backward and forward). However if
2. The graph has 4 vertices and 3 edges there is an arrow indicating direction the movement in
finding a path is in accordance with the indicated arrow

3. The graph has 5 vertices and 8 edges

13 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
Paths Length Path Vertex
e4 e3 2 Sequence
e3 e2 e4 3 Acef LMNOP Not closed
e1 e5 e4 3 Acb LMNL Closed
e1 e5 e4 e3 e2 5 Fed PONO Not closed
e1 e5 e5 e4 4 ecabd ONMLNO Closed
VERTEX SEQUENCE OF A CYCLE
PATH - a path is called a cycle if the following
- a path is written in terms of edges. A path conditions are satisfied:
determines a sequence of vertices. a.) the path is closed,
b.) the path repeat no edges,
c.) the vertices of the vertex sequence of the
path are all distinct except for the 1st and last
vertices which are the same vertices.
Example:

Path Len Vertex No. No.

gth Sequence of of
Edg Ver
es tex
adeecbd 7 XYZZZWYZ 7 8
Cbdec 5 ZWYZZW 5 6
eecbdecc 8 ZZZWYZZWZ 8 9
Path Vertex
Note:
1.) The number of vertices in vertex sequence is always Sequence
one larger than the number of edges in the path. e1 e2 e5 e3 ABDCB Not closed, not a
2. ) If a path passes through a loop, the vertex of the cycle
loop is repeated in the vertex sequence. e4 e5 e2 e3 CCDBC Closed, not a
CLOSED PATH cycle
- A closed path is said to be closed path if the e2 e3 e5 DBCD Closed, cycle
first and the last vertices of its vertex CONNECTED GRAPH
sequence are the same. - a graph is called connected graph if for any
Example: two given vertices there is a path connecting
them.
Example: Consider the following graphs;
Not connected

Connected

14 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
COMPLETE GRAPH ACYCLIC GRAPH
- is a connected graph where every pair of - A graph is called acyclic graph if it has no
vertices is joined by an edge. cycle
Example: Example:
No Cycle, Acyclic

SIMPLE GRAPH
- a graph is simple if it has neither loop nor
parallel edges Cycle, CDHG- wsrv. Not Acyclic
Example:
Simple Graph

Not a Simple Graph

WEIGHTED GRAPH
- A graph whose edges are assigned with
weights. Weight may represent mileage, time,
cost, or some other quantities.
DEGREE OF A VERTEX Example: Consider the transportation route of
- The degree of a vertex is defined as the
a salesman;
number of edges connected to the vertex.
- If a graph contains a loop, the loop contributes
2 to the degree of the vertex
Example:

Note: The vertices correspond to the different

cities while edges represent the distances in
kilometers.
TREE
- An acyclic connected graph.

Vertex Degree - Properties:

a.) acyclic graph
A 3
b.) no cycle path
B 6
c.) connected graph
C 4
Forest -refers to several trees
D 5

15 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
Example: Example:
Acyclic, Connected tree

the minimal spanning tree of G14,i.e., 5+8+10

(23 total weights)
SPANNING TREE
- a sub-graph tree of a graph that contains all
the vertices of the graph.
Example:

Two Special Circuits

EULER CIRCUIT
- A closed path in a graph which uses each of
Here is the spanning tree of the graph above the edges exactly once,
- Named after Leonard Euler(April 15, 1707 –
September 18, 1783), a Swiss Mathematician
and Physicist. He started working on graphs
from year 1736.

Note: If a graph has an n-edges then there are EULER THEOREM

n! Spanning tree in the graph. - The graph has an Euler Circuit if the graph is
Example:
connected and the degree of the vertices must
be even.
EULER PATH
- a path that uses each edge of a graph exactly
once.
EULER PATH THEOREM
5 edges
- a connected graph has an Euler path if and
5! = 120 spanning tree
only if the graph has two vertices of odd degree
MINIMAL SPANNING TREE with all other vertices of even degree
- the minimal spanning tree of a graph is a Example:
spanning tree of the graph with a minimum The graph is connected, Contains Euler path, Two of
total weights the vertices have odd degree, By Euler Theorem, the
- a connected graph has always at least one graph has no Euler Circuit
minimal spanning tree.

16 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
Not connected, Does not contain Euler path and - Also known as Hamiltonian Circuit.
Euler circuit. - Named after Sir William Rowan Hamilton
(1805-1865) He marketed a puzzle in the mid
1800 in the form of a dodecahedron that
contains the name of a city in each corner. The
Connected, contains Euler path, All vertices has an problem is to visit each city exactly once by
even degree, Contains Euler Circuit. travelling along the edges and be able to return
to the starting city. (D.S. Malik and M.K. Sen)

FLEURY’S ALGORITHM
- Is used to find an Euler Circuit in a graph if the
graph has one.
STEPS:
1. Select any of the vertices in the graph as the Example:
starting point. The graph has Hamilton circuit: V1V2V3V4V5
2. Select any edge connected to the vertex
selected in step 1. Remove the edge. (The
removal of the edge must not disconnect the
starting vertex or the starting point). After the
removal of the edge a new vertex is reach. The graph has no Hamilton circuit, since it will
3. Select an edge connected to the new vertex make use of the middle vertex (V) twice.
and repeat step 2.
4. Repeat step 3 until the starting vertex is
reach.
Example:

DIRAC’S THEOREM
- Consider a connected graph with at least 3
vertices and no multiple edges. Let n be the
Let Vertex X be the starting point. number of vertices in the graph. If every vertex
- remove edge f has degree of at least n/2, then the graph must
- remove edge e be HAMILTONIAN.
- remove edge c Example:
- remove edge b
- remove edge a
therefore, the Euler Circuit is – fdecba (with a
vertex sequence: XYZZWYX)
HAMILTON CIRCUIT
- A closed path which uses each vertex of the
graph exactly once, except for the last vertex
which duplicate the 1st vertex.
17 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD
Algorithm used to find a The Edge-Picking Algorithm
Hamiltonian Circuit Steps:
1. Mark the edge of the smallest weight in the graph.(if
GREEDY ALGORITHM two or more edges have the same weight, pick only
- Also known as shortest path algorithm one)
STEPS: 2. Mark the edge of next smallest weight in the graph,
1. Choose a vertex to start at, then travel as long as it does not complete a circuit does not add a
along the connected edge that has the smallest third marked edge to a single vertex.
weight.( if two or more vertices have the same 3. Continue this process until you can no longer mark
weight, pick any one) any edges. Then mark the final edge that completes the
2. After arriving at the next vertex, travel Hamiltonian circuit.
along the edge of smallest weight that connects PLANAR GRAPH
to a vertex not yet visited. Continue this
- is a graph that can be drawn so that no edge
process until you have visited all vertices.
intersects each other (except at vertices)
3. Return to the starting vertex
Example:
Example:

G20 is a planar graph since it can be re-

- Let C1 be the starting point, choose edge 80, drawn (G20.1) without any intersecting edges.
- From C2, choose edge 90,
- From C4, choose edge 160 (in this case edge
80 is not advisable since we will cross C3
twice)
- From C7, choose edge 110 instead of edge 70
(since we will cross C5 twice if we choose edge G20.2 is NOT a planar graph since it cannot
70), be re-drawn (G20.3) without any intersecting
- From C8, choose edge 105, edges.
- From C5 choose edge 60, MATRIX REPRESENTATION
- From C6, choose edge 200 OF A GRAPH
- From C3, choose edge 90, Rule: If a graph has N vertices its matrix
The Hamilton Circuit is now completed, with a representation has NxN shape, denoted by M.
vertex sequence: C1C2C4C7C8C5C6C3C1 Example: Write the matrix representation of the
total weight : graph below.
80+90+160+110+105+60+200+90=835.

18 | N e l l L a m i n e r o
MATHEMATICS IN THE MODERN WORLD
W X Y Z
W 0 2 1 1
X 2 0 0 0
Y 1 0 0 1
Z 1 0 1 2
Note:
1.) The entries indicate the edges between the
vertices. M(W,X) = 2 means that there are 2
edges that connects W & X. M(X,Y) = 0 means - M2 (W,W)= 3, means there 3 paths of length 2
that there is no edge that connects X & Y. that connects vertex W to itself. That is; e1e1,
2.The diagonal indicates the loop/s in the e6e6, e4e4.
graphs. M(Z,Z) =2 means that there is a loop - M2 (X,Z)=2 means there are 2 paths of length
that is connected to vertex Z 2 that connects vertex x to vertex Z, that is;
3.)The degree of the vertex is equal to the sum e1e4 and e2e3.
of the entries in its row or column.
4.) The matrix is symmetric with respect to its - Since the Matrix is symmetric, we can consider
diagonal. the upper diagonal or the lower diagonal.
Therefore the total number of paths of length
Deg(W) = 4 (sum of its column entry or of its is 3+3+3+3+2+2+2+2+2+2 =24 paths.
row entries) Note: Paths of length 3 is M3 of length 4 is M4 .
ADJACENCY MATRIX OF
SIMPLE GRAPH LESSON 2
Theorem: If M is the adjacency of a Application of Graph
simple graph, then the row* column entry of Mn
is equal to the number of length n from vertex THEORY OF THE PIPELINE
from row to the vertex in column, n=1,2,3… PROBLEM
Example: Consider the Graph - The MAYNILAD is considering 8 cities to be
connected by a pipeline. The distances (in km)
between cities are given in the graph below:

How many paths of length 2 can be used to

reach a vertex from another?
Determine the minimum length of pipe that
Solution: Path of Length 2 = M2 = MxM The MAYNILAD is needed to connect the 8 cities.
Matrix (M) of the is; Use the minimal spanning tree.
M= Solution:
W X Y Z
W 0 1 1 1
X 1 0 1 1
Y 1 1 0 1
Z 1 1 1 0

19 | N e l l L a m i n e r o
MATHEMATICS IN THE MODERN WORLD
Total weight of the minimal spanning tree = 80 - Use 4 colors to be assigned to its vertices.
+ 90+ 80+150 +60+70+105 = 635 - Assigned 2 different colors to any 2 adjacent
vertices.
Therefore, Maynilad needs 635km length of
pipeline to connect the 8 cities.

THE MAP COLORING

PROBLEM
The Four Color Theorem
- Every map in the plane consisting of connected
region without a hole can be colored with four
different colors without coloring two adjacent
regions with the same color TRAVELLING SALESMAN
Example: Consider the Map that shows some of PROBLEM (HAMILTON
the states of US.
PROBLEM)
Example:
In 1859, Sir William Rowan Hamilton marketed
a game called Around the World. The game
consisted of a regular dodecahedron made of
wood. Each corner bore the name of a famous
city of the world. The game was to find a path
starting at any city, travelling along the edges
of the dodecahedron, visiting each city exactly
once and returning to the starting city. The
How the map should be colored with 4 colors if diagram below represents the game. (Source:
no two adjacent states should have with the D.S. Malik and M.K. Sen)
same color?
Soulution:
Draw the graph representation of the map.
a.) Vertices are the regions or states
b.) Edges –to connect two vertices if the states
or regions corresponding to these vertices are
adjacent.

Around the World

Solution:
Using the Hamiltonian Circuit:

20 | N e l l L a m i n e r o
 MATHEMATICS IN THE MODERN WORLD

Therefore, one of the Hamiltonian Circuit that can be

an answer to the puzzle is the path with vertex
sequence of

V1V2V3V4V5V14V13V12V11V10V9V8V7V17V18V19V
20V16V15V6V1.

21 | N e l l L a m i n e r o