
Graph Theory
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

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

Vertices
Vertices are usually marked with solid dots and labeled

Edges
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

Graph Tracing
 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

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

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

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

Euler’s Theorem on Graph Tracing
 •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

More with Graphs
 •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

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

Non Base 10 systems
 Converting Numbers in NonBase
 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?

Converting Numbers in Base 10 to
Numbers in NonBase 10 Systems
 To convert a base 10 number such as 172 into a
 number in a nonbase 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 nonbase 10

Addition in NonBase10 Systems
 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

Subtraction in NonBase10
Systems
 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 nonbase10 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

Division in NonBase10 Systems
 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 nonbase10 system
 – Definitely construct a multiplication table for the
 nonbase10 system
 – e.g. Divide 45003 b6 / 31 b6

Multiplication in non base 10 systems
 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 twodigit 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

Product Rule
 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

Power Rule
 • 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

