Structures Flashcards
division theorem
backwards E unique numbers q, r such that
a = qb + r and 0 <= r < b
simple divisibility facts
c | a implies c | (sa)
if c | a and c|b then c|(a+b)
[ if a = k1c, b = k2c then a+b=(k1 + k2)c
if c | a and c | b then c | (sa+tb)
Euclidean Algorithm
the gcd of two numbers is the gcd of b and the remainder of a divided by b (provided b ≠ 0
gcd(a,b) = gdc(b, rem(a,b))
what is the relationship of gcd with respect to a and b?
gcd(a,b) is an integer linear combination of a and b.
gcd(a,b) = sa+tb
Fundamental Theorem of Arithmetic
Every integer > 1 factors uniquely into a weakly decreasing sequence of primes
Congruence (in number theory)
Congruence is a relation between two numbers, a and b. It’s determined by another parameter n, where n is considered to be greater than one. All of these, as usual, are integers.
it is defined as follow: a is congruent to b mod n if n divides a minus b or a minus b is a multiple of n.
Def : a =_ b (mod n) iff n|(a-b)
remainder lemma
a =_ b (mod n) iff rem(a,n) = rem(b,n)
when is it okay to cancel out a k within a mod equation
When k has no common factors of n
Euler’s Theorem
for k relatively prime to n:
k ^ ( phi * (n)) = _ 1 (mod n)
phi(mn) = phi(m) * phi(n) if m, n are relatively prime.
a relatively prime number
Two real numbers are relatively prime if and only if their gcd is 1
Fermat’s Little Theorem
given n is prime
a**(n-1) = 1 (Z sub(n) )
e.g. what is rem(24^78, 79) ?
Since 79 is prime and 24 is not a multiple of 79, Fermat’s Little Theorem is applicable, and it implies that is congruent to 1 modulo 79.
Walk
follow successive edges (which can repeat)
Path
a walk comprised of successive edges that do not repeats traversal of any edge
True or false - The shortest walk between two vertices is a path
True
length n walk relation
v g^n w IFF
What this means is with two vertices, v and w, there is this Gn relation between v and w if there exists a length n walk from v to w.
minimal subject (schedule)
has no prerequisites within a dag
antichain (scheduling)
A set of subjects with no indirect prerequisites among them (they can be taken in any order)
a chain (dag schedule)
The sequence of subjects that must be taken in order (subjects are comparable)
minimum # terms to graduate
minutes parallel time = max chain size
max term load
# processor for minimum time <= max antichain size
Dilworth’s Lemma
every n-vertex DAG has
a chains of size > t
or antichain of size >= n/t
every n-vertex DAG has a chain of size > and/or anti-chains of size sqrt(n)
tree
various definitions:
1) a connected graph with no cycles
2) a tree is a connect graph with every edge a cut edge
3) edge-minimal connected graph
4) an edge-maximal acyclic graph
5) graph in which there is a unique path between any 2 vertices
cycle
Cycle is a close walk of length > two that doesn’t cross itself
“pure” trees
unordered, unrooted, undirected trees
what is a cut edge
An edge is a cut edges if removing it from the graph disconnect two vertices.
an edge is not a cut dged iff it is on a cycle
spanning subgraph
a spanning subgraph of graph G is a subgraph that has all the vertices of G. A spanning tree is a spanning subgraph that is a tree.
what are the ways to grow a minimum weight spanning tree (MST’s)
- Start at any vertex, keep building one tree. (Prim)
- Keep choosing minimum weight edge between different components (Kruskal)
- grow trees in parallel (Meyer)
We can build a minimum spanning tree using the gray-edges technique, which involves coloring _____ black and white, selecting the _____ gray edge, and reiterating until we obtain a tree.
components, minimum-weight
What is the largest possible number of vertices in a tree whose vertices are all leaves?
2
What is the smallest possible number of leaves in a tree with 99 vertices?
2
What is the largest possible number of leaves in a tree with 99 vertices?
98
What is the largest possible number of leaves in a forest with 1000 vertices?
1000
t/f – An MST of a graph G is always unique.
False. This is only true when the edge weights of G are distinct. Otherwise, consider a complete graph with all edges having equal weights. This graph obviously does not have a unique MST.
