Math 102
Card Set Information
Author:
oksana
ID:
41387
Filename:
Math 102
Updated:
2010-10-11 14:51:07
Tags:
Math
Folders:
Description:
Study cards for math
Show Answers:
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