-
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 pre-existing edges (i.e. cannot create an edge)
-
Non Base 10 systems
- 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?
-
Converting Numbers in Base 10 to
Numbers in Non-Base 10 Systems
- 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
-
Addition in Non-Base-10 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 Non-Base-10
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 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
-
Division in Non-Base-10 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 non-base-10 system
- – Definitely construct a multiplication table for the
- non-base-10 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 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
-
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
|
|