Math 102

Very useful to model all sorts of different problems.

–e.g. most efficient way to travel from point A to point B (MapQuest), computer networks

A graph is comprised of a finite set of points called vertices which are connected by one or more lines called edges

Vertices are usually marked with solid dots and labeled

An edge is named by referring to the two vertices it connects

•Adjust naming if two or more edges connect the same pair of vertices

• To trace a graph, we start at a vertex and traverse all edges of the graph ONCE
• –i.e. No edge can be used twice
• –Not all graphs can be traced

A graph is connected if it is possible to start from a vertex and reach any other vertex by following edges

A bridge is an edge such that if it is removed, the graph is no longer connected

An odd vertex has an odd number of edges entering into it; an even vertex has an even number of edges entering into it.

• •A graph can be traced if:
• –The graph is connected AND
• –The graph has zero OR two odd vertices
• •If the graph has two odd vertices, the tracing must start with one odd vertex and end at the other

• •Path: a traversal of edges from one vertex to another vertex WITHOUT repeating an edge
• –The number of edges in a path is called the length
• •Euler Path: a path which contains all the edges of a graph
• –i.e. Graph tracing
• •Euler Circuit: an Euler path which starts and ends at the same vertex
• •Eulerian Graph: a graph that contains ALL even vertices AND is guaranteed to have an Euler Circuit

• To Eulerize a graph, we add edges to the graph so that all vertices are even
• –Can only duplicate pre-existing edges (i.e. cannot create an edge)

• Converting Numbers in Non-Base
• 10 Systems to Base 10
• • Consider counting: 1, 2, 3, … in base 10:
• – What are some of the place names in base 10?
• – What happens when we reach 9 in the ones place?
• – What are the possible values for digits in the ones
• place?
• – How would we write 5026 in expanded form?

• To convert a base 10 number such as 172 into a
• number in a non-base 10 system such as 6:
• – Divide the base into the number and keep track of the
• quotient AND remainder
• – As long as the quotient is not 0, keep dividing the
• base into the resulting quotient, making sure to keep
• track of the remainder
• – When the quotient is equal to 0, write the last
• remainder
• • It does not matter if the remainder is equal to 0
• – Write the remainders in reverse order
• • This is the number in the non-base 10

• Consider adding 7 + 5 in base 10
• – What happens when we exceed the digit 9 when
• adding in base 10?
• • When would we have to carry when adding in base
• 4?
• – Think of counting in base 4 as 0, 1, 2, 3, (1)0, (1)1,
• (1)2, (1)3…
• – e.g. Consider adding 23 + 11 in base 4
• • Possible to convert 234 and 114 to base 10, perform
• the addition, and then reconvert to base 4
• – Much easier to do the calculations in base 4

• Consider subtracting 16 – 7 in base 10
• – What happens when we cannot do the subtraction
• (e.g. 6 – 7)?
• – What do we do when borrowing in base 10?
• – How would we borrow in a non-base-10 such as 3?
• • e.g. Consider subtracting 213 – 123
• • Recall that borrowing can propagate across several
• columns:
• – Consider subtracting 201 – 79 in base 10
• • How would we perform the borrowing?
• – Consider subtracting 2013 – 123

• Consider dividing 404 / 13 in base 10
• – What are the steps for long division?
• – A good strategy is to create a multiplication table
• for 13 in base 10
• • May take some time at the start, but will save time in
• the long run
• • Consider dividing in a non-base-10 system
• – Definitely construct a multiplication table for the
• non-base-10 system
• – e.g. Divide 45003 b6 / 31 b6

• Consider multiplying 18 x 5 in base 10
• – What happens when the product exceeds 10?
• • How would this apply when multiplying in
• base 7?
• – e.g. Consider multiplying 257 x 67
• • Consider multiplying by a two-digit number
• – e.g. Consider multiplying 18 x 15 in base 10
• • What happens when we move to the second digit?
• – e.g. Consider multiplying 257 x 267

• Consider 22 ∙ 24 How does this expand?
• • Product Rule: x
• a ∙ x
• b = x
• a+b
• – When multiplying LIKE BASES (the same variable),
• add the exponents
• – Only applies when the operation is multiplication

• • Consider (22)4 How does this expand?
• • Power Rule: (x
• a)b = x
• ab
• – When raising variables to a power, multiply the
• exponents
• – Only applies when the exponent is outside a set of
• parentheses