Reading...
Play button
Play button
Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
21 Cards in this Set
- Front
- Back
|
Degrees of a vertex are
|
# of edges that hit it
|
|
|
Sum of degrees
|
2* number of edges
|
|
|
Vertex is even if
|
# of degrees hitting it is even
|
|
|
Vertexes are adjacent if
|
there is an edge connecting them
|
|
|
Bridge
|
an edge that if removed disconnects the graph
|
|
|
Optimal
|
find exact hamilton circuit
|
|
|
path
|
sequence of edges connecting one vertex with a different vertex, do not start and end at same spot
|
|
|
circuit
|
path that starts and ends at same vertex
|
|
|
euler circuit
|
0 odd vertices
|
|
|
Euler Path
|
2 odd vertices must start and end at them
|
|
|
Eulorization
|
if not path/circuit, how many times do you have to lift pencil, count all odd vertices, make it so there is only 2 odd vertices by connecting rest of odd vertices and # of connections=# of times you have to live pencil
|
|
|
Pencil Lifts
|
total odd-2/2
|
|
|
how many edges in Kn
|
n*n-1/2 where n=# of vertices
|
|
|
how many distinct hamilton circuits
|
(n-1)!
|
|
|
Brute Force Method
|
List every hamilton circuit, total= (n-1)!, compute all weights and pick smallest one
|
|
|
Nearest neighbor
|
pick starting vertex, choose edge with lowest weight
|
|
|
random experiment
|
activity/outcome whose results cant be predicted
|
|
|
sample space
|
set of all possible outcomes of a random experiment
|
|
|
multiplication rule
|
m ways to do x and n ways to do y, then theres m*n ways to do x and y (36 ways for 2 dice, 6x6)
|
|
|
Permutation
|
order matters nPr n!/(n-r)!
|
|
|
combination
|
order doesnt matter nCr n!/ (n-r)!xr!
|
