MATH 2320

Walk from V to W

Finite alternating sequence of adjacent vertices and edges

Trail

it is a walk from V to W that DOES NOT contain repeated edges

Path

it is a trail that DOES NOT contain a repeated vertex

• No repeated edges

• No repeated vertices

Closed Walk

A walk that starts and ends at the same vertex

Circuit

A closed walk that contains at least one edge and does not contain a repeated edge

• It is also a trail

Simple circuit

A circuit that does not have any other repeated vertices except the first and the last

One to one function F

if for ALL elements x1 and x2 in F’s domain, then if F(x1) = F(x2) then x1 = x2

• If two different inputs have the same output (co-domain) it is NOT one to one

onto function F

given any element y in F’s codomain (output) it is possible to find an element x in F’s domain (input) with the property y = F(x)

A is a subset of B

if and only if for ALL x if x is in set A, then x is also in sub set B

What is a proper subset A of B

there exists an element in set B that is not in A

A (intersection) B

is the set of all elements that exist in BOTH sets, for all X , x is in A, AND x is in B

• The middle part of a venn-diagram

A U B (union)

is the complete set of all elements in either set,

for all x, x is in A, OR x is in B.

• Join the two sets together, the entire venn-diagram of both sets

B - A sets

Set of elements that are in B only, and not in A

• If there are any elements in B that are also in A, those elements are subtracted and taken out

A^c (complement)

Is the set of all elements that are NOT in A

Power set of A P(A)

set of all subsets of set A

if A = {x,y} then

P(A) = { 0, {x}, {y}, {x,y}}

• 0 is the empty set

De Morgans law

(A intersection B)^c = A^c U B^c

reflexive property of relations

every element in a set should be related to itself with relation R, so x R x, then y R y

Symmetric property of relations

given 2 elements in a set and relation R, if x R y, then y R x,

• if a R b, then b R a

Transitive property of sets

if a R b, and b R c, then a R c.

• if you cannot find a counter example then it is transitive by default

Given an array a[1] , a[2], a[3], a[n]… how many elements does the subarray a[65] , a[66],…. a[101] have

Take the last element - first element number then + 1

so 101 - 65 + 1 = 37

n choose k

n!/k!(n-k)!

quotient reminder theorem

Given any integers n and p, and p > 1, then there exists a unique pair (q, r) such that n = p*q + r

where O <= r <= P

N mod P is the reminader R

Inclusion- exclusion principle for counting the number of elements in A U B

| A U B | = | A | + | B | - | A intersection B|

• Count of elements in A and B, subtracted by the count of elements in A intersection B